Umut Özel    About    Archive    Feed

SIMD'i Onlar Düşünsün - .Net Core ile Hardware Intrinsics

Bir programlama dili kullanarak yazdığımız kodları (genelde) işlemciler çalıştırıyor. Peki biz işlemcileri ne kadar tanıyoruz? Yeteneklerini ne kadar kullanıyoruz?

Cpu from Sand

Konuların derinlerine inmeyi, bir şeyi kullanmaktan öte nasıl çalıştığını anlamaya çalışmayı çok severim. İtiraf edeyim, bazen mikro optimizasyon da yapıyorum, sınırları zorlamak için ve genellikle hobi projelerimde. Bildiğiniz kumdan yapılan işlemciler hakkında ne zaman bir yazı okusam aklıma programlama dillerinin neden bize bu yetenekleri sunmadığı düşüncesi geliyor. Yakın bir zamanda gördüğüm bu makaleden sonra ben de bu konuda biraz karalamak istedim.

Intel’in işlemci üretimi bayağı geçmişe dayanıyor. Ancak x86 mimarisini başlatan 8086 esas devrimin temelini attı. Özellikle VME ile modern işletim sistemlerinin doğmasını sağladı.

8086

Peki biz kodlama yaparken bu işlemcilerin hangi özelliklerini kullanıyoruz? Şöyle bir düşünelim, herhangi bir programlama dilinin dokümantasyonunu hatırlayın. Değişken tanımlama, döngüler, structlar, (varsa) sınıflar, matematiksel işlemler vs.. Hep aynı konular, birisinde interface varken diğerinde trait oluşturuyoruz. Birisinde async varken diğerinde callback ile çalışıyoruz. Birinde pointer var diğerinde referanslar var. Bazıları belleği bizim için yönetiyor, diğerlerinde referans takip etmek üzere bize büyük iş düşüyor.

Keywords

Ancak işlemciler bir çoğumuzun bilmediği ya da hiç kullanmadığı çok daha fazlasını yapabilen eklentilere sahipler, tam liste burada. Hem de bildiğim en eskisi olan MMX ile 1996 yılından beri. MMX bir SIMD (Single Instruction, Multiple Data) yani tek komut-çok işlem eklentisi.

MMX

Bu eklentiler genelde kendi register‘larına sahipler. Genelde işlemci register’ları işlemcinin çalışma bit genişliği ile aynı olur, 16 bit için 16 bit gibi. Ancak MMX 64 bitlik kendi register’larına sahip. Yani 4 adet 16 bitlik sayı tutabiliyor. İki tane 4 elemanlık dizideki elemanları karşılıklı toplayıp yeni bir dizi oluşturabiliyor.

const a1 = [1, 3, 5, 7]
const a2 = [2, 4, 6, 8]
const a3 = []
for (let i = 0; i < 4; i++) {
    a3.push(a1[i] + a2[i])
}

Yukarıdaki kodda bilerek imperatif bir yol izledim, map gibi bir fonksiyon kullansam tam anlatmak istediğimi vurgulayamayacaktım

Toplama işlemimizi bir döngü içinde yaptık, büyük ihtimalle kodumuz her döngü adımında klasik register’lara (EAX gibi) verileri yükleyecek ve ADD komutu ile verileri toplayacak. Sonuçları da EBX ev ECX kullanarak hesapladığı hedef bellek adresine yazacak. Bildiğiniz bir sürü iş var burada.

SIMD Example http://mirror.as43289.net/kernel/people/geoff/cell/ps3-linux-docs/CellProgrammingTutorial/BasicsOfSIMDProgramming.html

SIMD kullanarak bu işi tek bir komuta indirebiliyoruz.

Tabii ne gerek var diyebilirsiniz, bu konuda kimseyi ikna edebileceğimi sanmıyorum çünkü günlük geliştirmelerimizde büyük oranda bu seviyede optimizasyona ihtiyacımız olmuyor. Genelde oyun geliştiricileri (uzun yıllardır bu işleri de GPU devraldı), görüntü işleme, karışık matematiksel işlemler gibi işlerle uğraşanlar zaten biliyordur.

Compiling https://xkcd.com/303/

Tam burada önemli bir noktaya değinmek lazım. Günümüzde derleyiciler çok akıllandı. Recursive fonksiyonlarda Tail Call Optimizasyonu‘nu otomatik yapanlar, veri komşuluğunu ve önbellek kullanım oranını arttırmak için kod sıralamamızı yeniden düzenleyenler bulunmakta. Genelde uygulanan optimizasyonlar için şu listeye bakabilirsiniz. Bu yazıda değindiğim SIMD çağrılarının sizin için otomatik yapılmadığını garanti edemem, belki onu da yapanlar vardır. Özellikle C#, Java gibi yönetilen (managed) dillerden şüpheleniyorum. Tam zamanında derleme (JIT Compilation) statik kod üretimine göre büyük avantajlara sahip, ellerindeki çalışma zamanı verileri bu optimizasyonu yapmalarını sağlayabilir.

Arm

Şunu da eklemek lazım, her işlemci bu eklentilerin her birini desteklemiyor. Dolayısı ile bu özellikleri biraz zorlayarak da olsa kullanabildiğimiz dillerde platform kontrolü yapmamız gerekiyor. Genellikle bu derece optimize edilen fonksiyonlar bir kontrol yapıp ortam uygun değilse SIMD kullanmak yerine klasik x86 komutlarını çağırıyorlar. Yani bir if kontrolü başarısız olursa yukarıdaki gibi bir döngü çalışıyor.

Belki de bu sorun çoklu platform destekleyen dillerin SIMD kullanımını standart kütüphanelere eklememe sebepleri olabilir.

Dotnet Core ve SIMD

Net Core

Daha fazla uzatmadan konumuza gelelim. .Net Core 3.0 ile bu özellikleri nasıl kullanabilceğimizi görelim. Aslında .Net ve SIMD konusu pek yeni sayılmaz, 2014 yılında devrimsel RyuJIT derleyicisi ile bu yeteneği eklemişlerdi.

// Dizi yerine Vector

Vector<float> values = GetValues();
Vector<float> increment = GetIncrement();

// İki vektörü SIMD ile topluyoruz

Vector<float> result = values + increment;

.Net ile gelen SIMD yenilikleri mümkün olduğunda donanım özelliklerini kullanırken işlemci desteği olmayan ortamlarda çalışabilecek kodları da içeriyor (Software Fallback).

.Net Core 3.0 ile eklenenler ise yazılım desteği içermiyor, bir fallback olmadığı için çağıracağımız komutların işlemci tarafından desteklendiğini bizim kontrol etmemiz gerekiyor. Tabii çalışma ortamı tamamen bizim kontrolümüzdeyse ve zaten bu özellikleri içerdiğinden eminsek kontrol etmeden de kullanabiliriz.

İlk adımımız System.Runtime.Intrinsics altından ortamımıza uygun olanı eklemek, ben x86 üzerinde çalışan bir Mac kullanıyorum, yani System.Runtime.Intrinsics.X86 namespace ekliyorum.

Platforma özel namespace’ler altında işlemci eklentileri komut setleri (Instruction Set Architecture - ISA) şeklinde gruplanmış durumda. Her sınıf da IsSupported property’si ile desteklenme durumunu kontrol edebilmemizi sağlıyor. Bu sınıfların altında da X64 isimli subclass bulunduğunu görebilirsiniz. Yani sınıflar varsayılan olarak 32 bit işlemciler için yazılmışken 64 bit işlemciler için ayrı sınıf kullanmak gerekiyor. 64 bit işlemciler 32 bit işlemleri geri uyumluluk adına destekliyor ancak 64 bit ile çalışmanın performansa etkisi olacaktır.

64 Bit https://www.statista.com/statistics/265033/proportion-of-operating-systems-used-on-the-online-gaming-platform-steam/

Kullanıcıların donanım özelliklerini takip eden Steam platformunun verilerine bakarsak çok büyük oranda 64 bit sistemlerin kullanıldığını görebiliriz.

Bu durumda 64 bit SSE2 için System.Runtime.Intrinsics.X86.Sse2.X64 sınıfını kullanmamız gerekiyor. Ortam desteğini de System.Runtime.Intrinsics.X86.Sse2.X64.IsSupported statik değişkeni ile kontrol edebiliriz.

Örnek Yapalım

En basit örnek bir dizi elemanlarını toplamak, gerçek dünya kullanımları hayal gücümüze bağlı.

static int Sum (ReadOnlySpan<int> source) {
    var result = 0;

    for (var i = 0; i < source.Length; i++) {
        result += source[i];
    }

    return result;
}
Method Count Mean Error StdDev
Sum 1 2.477 ns 0.0192 ns 0.0179 ns
Sum 2 2.164 ns 0.0265 ns 0.0235 ns
Sum 4 3.224 ns 0.0302 ns 0.0267 ns
Sum 8 4.347 ns 0.0665 ns 0.0622 ns
Sum 16 8.444 ns 0.2042 ns 0.3734 ns
Sum 32 13.963 ns 0.2182 ns 0.2041 ns
Sum 64 50.374 ns 0.2955 ns 0.2620 ns
Sum 128 60.139 ns 0.3890 ns 0.3639 ns
Sum 256 106.416 ns 0.6404 ns 0.5990 ns
Sum 512 291.450 ns 3.5148 ns 3.2878 ns
Sum 1024 574.243 ns 9.5851 ns 8.4970 ns
Sum 2048 1,137.819 ns 5.9363 ns 5.5529 ns
Sum 4096 2,228.341 ns 22.8882 ns 21.4097 ns
Sum 8192 2,973.040 ns 14.2863 ns 12.6644 ns
Sum 16384 5,883.504 ns 15.9619 ns 14.9308 ns
Sum 32768 11,699.237 ns 104.0970 ns 97.3724 ns

Benchmark projesi ile uğraşmak yerine hazır yapılmışları paylaşacağım.

Modern işlemciler tek bir thread üzerinde bile olsa Instruction Pipelining sayesinde tek bir cycle içinde birden fazla işlem yapabiliyorlar.

Bu işi JIT derleyici de yapabilir, ama garantiye almak için kendimiz yapabiliriz. Loop Unrolling denilen bu yaklaşım ile işlemleri 4’erli gruplar ile yaparak Instruction Pipelining optimizasyonu yapmış oluyoruz.

static unsafe int SumUnrolled (ReadOnlySpan<int> source) {
    var result = 0;
    var i = 0;
    var lastBlockIndex = source.Length - (source.Length % 4);

    // Pin source so we can elide the bounds checks
    fixed (int * pSource = source) {
        while (i < lastBlockIndex) {
            result += pSource[i + 0];
            result += pSource[i + 1];
            result += pSource[i + 2];
            result += pSource[i + 3];

            i += 4;
        }

        while (i < source.Length) {
            result += pSource[i];
            i += 1;
        }
    }

    return result;
}
Method Count Mean Error StdDev
SumUnrolled 1 2.922 ns 0.0651 ns 0.0609 ns
SumUnrolled 2 3.576 ns 0.0116 ns 0.0109 ns
SumUnrolled 4 3.708 ns 0.0157 ns 0.0139 ns
SumUnrolled 8 4.832 ns 0.0486 ns 0.0454 ns
SumUnrolled 16 7.490 ns 0.1131 ns 0.1058 ns
SumUnrolled 32 11.277 ns 0.0910 ns 0.0851 ns
SumUnrolled 64 19.761 ns 0.2016 ns 0.1885 ns
SumUnrolled 128 36.639 ns 0.3043 ns 0.2847 ns
SumUnrolled 256 77.969 ns 0.8409 ns 0.7866 ns
SumUnrolled 512 146.357 ns 1.3209 ns 1.2356 ns
SumUnrolled 1024 287.354 ns 0.9223 ns 0.8627 ns
SumUnrolled 2048 566.405 ns 4.0155 ns 3.5596 ns
SumUnrolled 4096 1,131.016 ns 7.3601 ns 6.5246 ns
SumUnrolled 8192 2,259.836 ns 8.6539 ns 8.0949 ns
SumUnrolled 16384 4,501.295 ns 6.4186 ns 6.0040 ns
SumUnrolled 32768 8,979.690 ns 19.5265 ns 18.2651 ns

Küçük dizilerde biraz daha yavaş çalışan yeni kod 16 ve daha fazla kayıt olduğunda yavaş yavaş daha iyi sonuçlar üretiyor.

Vektörü Görelim

Yaklaşımı comment’ler ile açıklamaya çalıştım.

static int SumVectorT (ReadOnlySpan<int> source) {
    var result = 0;
    var vresult = Vector<int>.Zero;
    var i = 0;

    // vektör kaç adet int alabiliyor?
    // vektöre gruplu sığdırdığımız son eleman kim?
    var lastBlockIndex = source.Length - (source.Length % Vector<int>.Count);

    // gruplu halde vektörlere yerleştiriyoruz
    while (i < lastBlockIndex) {
        vresult += new Vector<int> (source.Slice (i));
        i += Vector<int>.Count;
    }

    // vektör gruplarını topluyoruz
    for (var j = 0; j < Vector<int>.Count; j++) {
        result += vresult[j];
    }

    // geri kalan elemanları da ekliyoruz
    while (i < source.Length) {
        result += source[i];
        i += 1;
    }

    return result;
}

Sonuçlar aşağıdaki gibi:

Method Count Mean Error StdDev
SumVectorT 1 4.517 ns 0.0752 ns 0.0703 ns
SumVectorT 2 4.853 ns 0.0609 ns 0.0570 ns
SumVectorT 4 5.047 ns 0.0909 ns 0.0850 ns
SumVectorT 8 5.671 ns 0.0251 ns 0.0223 ns
SumVectorT 16 6.579 ns 0.0330 ns 0.0276 ns
SumVectorT 32 10.460 ns 0.0241 ns 0.0226 ns
SumVectorT 64 17.148 ns 0.0407 ns 0.0381 ns
SumVectorT 128 23.239 ns 0.0853 ns 0.0756 ns
SumVectorT 256 62.146 ns 0.8319 ns 0.7782 ns
SumVectorT 512 114.863 ns 0.4175 ns 0.3906 ns
SumVectorT 1024 172.129 ns 1.8673 ns 1.7467 ns
SumVectorT 2048 429.722 ns 1.0461 ns 0.9786 ns
SumVectorT 4096 654.209 ns 3.6215 ns 3.0241 ns
SumVectorT 8192 1,675.046 ns 14.5231 ns 13.5849 ns
SumVectorT 16384 2,514.778 ns 5.3369 ns 4.9921 ns
SumVectorT 32768 6,689.829 ns 13.9947 ns 13.0906 ns

Yukarıdaki kodda 16 baytlık vektörler kullanılıyor. Bir de Vector128 ile görelim.

static unsafe int SumVectorizedSse2 (ReadOnlySpan<int> source) {
    int result;

    fixed (int * pSource = source) {
        var vresult = Vector128<int>.Zero;

        var i = 0;
        var lastBlockIndex = source.Length - (source.Length % 4);

        while (i < lastBlockIndex) {
            vresult = Sse2.Add (vresult, Sse2.LoadVector128 (pSource + i));
            i += 4;
        }

        // eğer SSE3 destekleniyorsa daha da hızlı versiyonu kullanalım
        if (Ssse3.IsSupported) {
            vresult = Ssse3.HorizontalAdd (vresult, vresult);
            vresult = Ssse3.HorizontalAdd (vresult, vresult);
        } else {
            vresult = Sse2.Add (vresult, Sse2.Shuffle (vresult, 0x4E));
            vresult = Sse2.Add (vresult, Sse2.Shuffle (vresult, 0xB1));
        }
        result = vresult.ToScalar ();

        while (i < source.Length) {
            result += pSource[i];
            i += 1;
        }
    }

    return result;
}
Method Count Mean Error StdDev
SumVectorized 1 4.555 ns 0.0192 ns 0.0179 ns
SumVectorized 2 4.848 ns 0.0147 ns 0.0137 ns
SumVectorized 4 5.381 ns 0.0210 ns 0.0186 ns
SumVectorized 8 4.838 ns 0.0209 ns 0.0186 ns
SumVectorized 16 5.107 ns 0.0175 ns 0.0146 ns
SumVectorized 32 5.646 ns 0.0230 ns 0.0204 ns
SumVectorized 64 6.763 ns 0.0338 ns 0.0316 ns
SumVectorized 128 9.308 ns 0.1041 ns 0.0870 ns
SumVectorized 256 15.634 ns 0.0927 ns 0.0821 ns
SumVectorized 512 34.706 ns 0.2851 ns 0.2381 ns
SumVectorized 1024 68.110 ns 0.4016 ns 0.3756 ns
SumVectorized 2048 136.533 ns 1.3104 ns 1.2257 ns
SumVectorized 4096 277.930 ns 0.5913 ns 0.5531 ns
SumVectorized 8192 554.720 ns 3.5133 ns 3.2864 ns
SumVectorized 16384 1,110.730 ns 3.3043 ns 3.0909 ns
SumVectorized 32768 2,200.996 ns 21.0538 ns 19.6938 ns

Bu sefer çok iyi sonuçlar aldık, SSE3 destekli sistemlerde neredeyse 6 kat daha hızlı!


Amacım biraz merakları gıdıklamak, aklımızın ucunda neler yapabileceğimize dair bir iz bırakmak. İnternette bu konuda çok daha detaylı bilgilere ulaşabilirsiniz, ben kesinlikle işlemci mimarisinde bir uzman olduğumu iddia etmiyorum, öğrenilecek çok şey var!

Tanner Gooding’e yazısı ve sonuçları kullanmama izin verdiği için teşekkürler.

Mutlu kodlamalar.