Kayan nokta üs alanları, CLZ ve CTZ'yi vektörize etmek için logaritma olarak kullanılıyor

Kayan nokta donanımı bit tarayıcı olarak

Count-leading-zeros (clz) ve count-trailing-zeros (ctz), sabit genişlikli bir tam sayının en üstünde veya en altında kaç sıfır bit olduğunu bildirir. Modern CPU'lar bunları komut olarak sunar, ancak her yerde aynı maliyette değillerdir: Hacker News ana sayfasına ulaşan bir blog yazısında purplesyringa'nın belirttiği gibi, Intel'in Arrow Lake'inde tzcnt üç çevrim gecikmeye sahip. Yazar, bir FPU emülatörü geliştirirken bir ctz'yi kayan nokta aritmetiğiyle değiştirmenin yolunu buldu, sonra fikrin tamsayı vektör karşılıkları bulunmayan AVX2 sınıfı donanımda her iki işlem için de vektörize edilebilir bir yedek olarak genelleştiğini fark etti.\n

Üsleri logaritmaya çevirmek

Temel gözlem, bir IEEE-754 üs alanının özünde bedavaya elde edilen bir sapmalı 2 tabanlı logaritma olmasıdır. clz için, yazıdaki Rust parçası 2^-970'e eşit bir double alır, 32 bitlik girdiyi alt mantissa bitlerine OR'lar — 2^k(1 + x·2^-52) üreterek — ve 2^k'yi geri çıkarır. Kalanın üs alanı en yüksek set bitinin konumunu kodlar ve clz tek bir tamsayı çıkarmasıyla elde edilir. Bu özel üs ayrıca x = 0'ın makul davranmasını sağlar.

Yapısal bir sınır vardır: bir double 52 mantissa biti taşır, dolayısıyla düzen yalnızca 52 bite kadar girdileri kapsar. 32 bitlik değerler sığar; rastgele 64 bitlik değerler sığmaz.

Dört lane üzerinde vektörize edildiğinde işlevin tamamı beş komuttur: bir sapma sabitinin broadcast'i, bir sabite karşı OR, bir vektör çıkarması, 52 bitlik sağa kaydırma ve son bir çıkarma. Lookup tablosu yok, lane geçişi yapan shuffle yok.

ctz: en düşük set biti yalıtarak

ctz için yazı, yalnızca en düşük set bitini koruyan klasik x ^ (x - 1) özdeşliğine dayanır; ctz bu değerin 2 tabanlı logaritmasıdır ve aynı üs hilesiyle okunabilir. Zor kısım sabit mühendisliğidir. x'ten 1 çıkarmak yerine x'e 2^32 - 1 eklemek, sabitin mantissasına 2^32 önceden karıştırıldığında x = 0'ın 32 döndürmesini sağlar; tek bir önceden ayarlanmış mantissa biti, yalıtılmış desenleri sıfır olan tek sayı girdilerin yavaş bir subnormal sonuca düşmesini engeller. Yazar bu bitleri yerleştirmenin epey iterasyon aldığını kabul ediyor.

Bu varyant clz'den bir komut daha gerektirir. AVX-512'nin vpternlogq'yu bir adımı katlayabilir, ancak yazıya göre AVX-512 mevcutsa (x - 1) & ~x üzerinden vpopcntd çalıştırmak daha iyi.

Okuyucu katkılı alternatifler

Yazı iki güncellemeyle büyüdü. Nikolay Malkovsky, de Bruijn dizilerinin de vektörize edilebildiğini belirtti: yalıtılmış biti bir magic constant ile çarpın, kaydırın ve yanıtı vpshufb ile lookup yapın. vpshufb 16 baytlık lane'leri geçemediğinden gerçek bir 32 baytlık tablo imkânsızdır, bu yüzden yazar 16 bitlik bir de Bruijn dizisini iki kez tekrarlar, ctz'nin düşük dört bitini lookup'tan türetir ve hangi yarım kelimelerin tamamen sıfır olduğuna bağlı olarak 16 veya 32 ekler. 0xf0a6f0a7 sabitinin çalışan sadece dört sabitten biri olduğu bildiriliyor. Haswell'de iterasyon başına 1 ns (Alder Lake'te 0.7 ns) sürer ama geçiş başına iki kat verime sahiptir, dolayısıyla shuffle'lardan kaçındığında hâlâ öne geçebilir; x = 0 işlemesini gevşetmek onu 0.82 ns'ye indirir.

arya dradjica ile birlikte geliştirilen ikinci güncelleme 64 bitlik girdilere odaklanır: pshufb güdümlü bir tablo her baytın iki nibble'ının ters çevrilmiş popcount'unu üretir ve tam sekiz baytlık grupları toplayan vpsadbw, bunları tek adımda hem toplar hem tersine çevirir ve ctz(0) = 64'ü Haswell'de 0.63 ns'de doğru şekilde döndürür. Bu biçim 64 bitlik lane'lere özgüdür; 32 bitlik girdiler için de Bruijn sürümü en hızlısı olmaya devam eder.

Sayılar ne gösteriyor

Yazarın Haswell'inde clz, skaler sürüm için olan 1 ns'ye karşı iterasyon başına 0.45 ns'de, ctz ise 0.49 ns'de (gecikmeye bağlıysa 2.3 ns) çalışır. Ian Qvist, Alder Lake'te clz için skaler 0.85 ns'ye karşı 0.29 ns ve ctz için 0.35 ns ölçtü. Gecikmeye bağlı koşullarda skaler sürüm kazanabilir ve AMD'de ucuz lzcnt, skaler kodun muhtemelen baskın olduğu anlamına gelir — yine de Zen'in AVX-512 desteği vplzcntd'yi doğrudan sunar.

Neden önemli

AVX2'nin vektör clz veya ctz'si yoktur, dolayısıyla bitleri yoğun tarayan verim odaklı kod — yazarın FPU projesi gibi emülatörler somut bir örnektir — skaler çıkarma veya beceriksiz shuffle tabanlı geçici çözümlere mahkûm olmuştur. Yazı üçüncü bir yol gösteriyor: kayan nokta veri yolu toplu bir logaritma motoru olarak ikiye katlanıyor ve üssü yalnızca bir OR, bir çıkarma ve bir kaydırma ile hasat edilebiliyor. Daha geniş ders şu: yavaş komut sorununun bazen yazılımsal bir yanıtı vardır — ama yazıdaki gecikme zincirlerinden AMD'nin ucuz skaler yollarına kadar ölçüm uyarıları, böyle bir hilenin yaşayıp yaşamayacağının tam hedef CPU üzerindeki ölçüme bağlı olduğunun hatırlatıcısıdır.