Berikut ini sekilas kemampuan vektorisasi algoritma dalam .NET Framework dan .NET Core. Artikel ini ditujukan bagi mereka yang tidak tahu apa-apa tentang teknik ini. Saya juga akan menunjukkan bahwa .NET tidak benar-benar ketinggalan bahasa "dikompilasi nyata" untuk pengembangan asli.
Saya baru mulai belajar teknik vektorisasi. Jadi, saya akan menghargai jika anggota masyarakat menemukan kesalahan yang jelas atau menyarankan perbaikan pada algoritma yang dijelaskan.
Beberapa sejarah
SIMD muncul di .NET Framework 4.6 pada 2015. Saat itulah tipe Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3, dan Vector4 ditambahkan. Mereka memungkinkan perhitungan vektor. Berikutnya adalah tipe Vector <T> yang memberi lebih banyak peluang untuk membuat vektor algoritma. Namun, banyak programmer masih tidak puas karena jenis ini membatasi aliran ide coders dan tidak membiarkan penggunaan kapasitas penuh instruksi SIMD dalam prosesor modern. Sekarang di .NET Core 3.0 Preview, kami memiliki System.Runtime.Intrinsics namespace yang memberikan banyak kebebasan dalam pilihan instruksi. Untuk mendapatkan kecepatan maksimal, Anda perlu menggunakan RyuJit dan menggunakan rakitan x64 atau mematikan Prefer 32-bit dan memilih rakitan AnyCPU. Saya menjalankan semua tolok ukur pada komputer CPU Intel Core i7-6700 3,40 GHz (Skylake).
Menjumlahkan elemen array
Saya memutuskan untuk memulai dengan tugas klasik yang biasanya didahulukan jika ada vektorisasi yang terlibat. Ini berkaitan dengan menemukan jumlah elemen array. Mari kita menulis empat implementasi dari tugas ini untuk menjumlahkan elemen-elemen dari Array.
Implementasi yang paling jelas:
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Implementasi berbasis LINQ:
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
Implementasi berdasarkan vektor dari System.Numerics:
public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
Implementasi berdasarkan kode dari namespace System.Runtime.Intrinsics:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Saya membandingkan 4 metode tersebut di komputer saya dan mendapatkan hasil sebagai berikut:
Sudah jelas bahwa solusi dengan Vektor dan Intrinsik jauh lebih cepat daripada solusi yang jelas dan berbasis LINQ. Sekarang kita perlu mencari tahu apa yang terjadi dalam kedua metode ini.
Mari kita pertimbangkan metode Vektor lebih dekat:
Vektor public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
- int vectorSize = Vektor <int> .Count; - jumlah angka 4-byte yang dapat kita tempatkan dalam vektor. Jika akselerasi perangkat keras digunakan, nilai ini menunjukkan berapa banyak angka 4-byte yang dapat kita masukkan dalam satu register SIMD. Bahkan, ini menunjukkan berapa banyak elemen jenis ini dapat ditangani secara bersamaan;
- accVector adalah vektor yang mengakumulasikan hasil fungsi;
- var v = Vector baru <int> (array, i); - data dari array dimuat ke vektor v baru, mulai dari indeks i. Ukuran vektor data akan dimuat dengan tepat;
- accVector = Vector.Add (accVector, v); - dua vektor dijumlahkan.
Misalnya, ada 8 angka dalam Array: {0, 1, 2, 3, 4, 5, 6, 7} dan vectorSize == 4.
Kemudian selama iterasi siklus pertama, accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} dan setelah penambahan accVector akan menampung: {0, 0, 0, 0} 0 {0, 1 , 2, 3} = {0, 1, 2, 3}.
Selama iterasi kedua v = {4, 5, 6, 7} dan setelah penambahan accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Sekarang kita hanya perlu mendapatkan jumlah semua elemen vektor. Untuk melakukan ini kita dapat menggunakan perkalian skalar dengan vektor yang diisi dengan yang: int result = Vector.Dot (accVector, Vector <int> .One);
Maka kita mendapatkan: {4, 6, 8, 10} * {1, 1, 1, 1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28. - Jika perlu, angka-angka yang tidak sesuai dengan vektor terakhir akan dijumlahkan di akhir.
Mari kita lihat kode intrinsik:
Intrinsik public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Kita dapat melihat bahwa itu seperti Vektor dengan satu pengecualian:
Membandingkan dua array
Kita perlu membandingkan dua array byte. Persis tugas inilah yang membuat saya mempelajari SIMD di .NET. Sekali lagi, mari kita menulis beberapa metode untuk pembandingan dan membandingkan dua array: ArrayA dan ArrayB.
Solusi paling jelas:
public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Solusi berbasis LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
Solusi berdasarkan fungsi MemCmp:
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;
Solusi berdasarkan vektor dari System.Numerics:
public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Solusi berbasis intrinsik:
public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } }
Hasil menjalankan patokan di komputer saya:
Saya kira kode metode ini jelas, kecuali untuk dua baris dalam Intrinsik:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
Pada baris pertama dua vektor dibandingkan untuk kesetaraan dan hasilnya disimpan dalam vektor areEqual di mana semua bit dalam elemen pada posisi tertentu diatur ke 1 jika elemen yang sesuai dalam va dan vb sama. Jadi, ternyata jika byte vektor va dan vb sama, semua elemen di areEqual harus sama dengan 255 (11111111b). Karena Avx2.CompareEqual adalah pembungkus di atas _mm256_cmpeq_epi8, kita dapat pergi ke situs web Intel dan melihat pseudocode dari operasi ini:
Metode MoveMask membuat angka 32-bit dari vektor. Bit teratas dari masing-masing 32 elemen onebyte dalam vektor adalah nilai bit dalam hasil MoveMask. Kodesemu tersedia di sini .
Jadi, jika beberapa byte dalam va dan vb tidak cocok, byte yang sesuai di areEqual akan menjadi 0. Oleh karena itu, bit teratas dari byte ini akan menjadi 0 juga. Ini berarti bit terkait dalam respons Avx2.MoveMask juga akan 0 dan areEqual tidak akan sama dengan equalsMask.
Mari kita lihat satu contoh dengan asumsi bahwa panjang vektor adalah 8 byte (untuk menulis lebih sedikit):
- Misalkan va = {100, 10, 20, 30, 100, 40, 50, 100} dan vb = {100, 20, 10, 30, 100, 40, 80, 90}.
- Maka areEquals akan menjadi {255, 0, 0, 255, 255, 255, 0, 0}.
- Metode MoveMask akan mengembalikan 10011100b yang harus dibandingkan dengan topeng 11111111b. Karena topeng ini tidak sama, vektor va dan vb juga tidak sama.
Menghitung berapa kali suatu elemen muncul dalam koleksi.
Terkadang Anda perlu menghitung kemunculan elemen tertentu, misalnya bilangan bulat, dalam koleksi. Kami dapat mempercepat algoritme ini juga. Sebagai perbandingan, mari kita menulis beberapa metode untuk mencari elemen Item di Array.
Yang paling jelas:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
Menggunakan LINQ:
public int LINQ() => Array.Count(i => i == Item);
Menggunakan vektor dari System.Numerics.Vectors:
public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; }
Menggunakan Intrinsik:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; }
Hasil menjalankan patokan di komputer saya:
Metode Vektor dan Intrinsik sepenuhnya bertepatan dalam logika tetapi berbeda dalam implementasi operasi tertentu. Idenya adalah sebagai berikut:
- membuat vektor topeng di mana nomor yang diperlukan disimpan di setiap elemen;
- muat bagian array dalam vektor v dan bandingkan bagian ini dengan mask. Akibatnya, semua bit akan disetel dalam elemen sama dengan areEqual. Karena areEqual adalah array bilangan bulat, maka jika kita mengatur semua bit dari satu elemen, kita akan mendapatkan -1 pada elemen ini ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- kurangi areEqual vector dari accVector. Kemudian, accVector akan menahan hitungan berapa kali elemen item terjadi di semua vektor untuk setiap posisi (dikurangi dengan minus adalah plus).
Seluruh kode dari artikel ini ada di GitHub .
Kesimpulan
Saya menjelaskan hanya sebagian kecil dari kemampuan .NET untuk vektorisasi perhitungan. Untuk melihat daftar lengkap semua intrinsik yang tersedia di .NET Core di bawah x86, buka kode sumber . Lebih mudah bahwa ringkasan setiap intrinsik dalam file C # berisi namanya di dunia C. Ini membantu memahami tujuan intrinsik ini dan transfer algoritma C ++ / C yang ada ke .NET. Dokumentasi System.Numerics.Vector tersedia di msdn .
Saya pikir .NET memiliki keunggulan dibandingkan C ++. Karena kompilasi JIT sudah terjadi pada mesin klien, kompiler dapat mengoptimalkan kode untuk prosesor klien tertentu, memberikan kinerja maksimum. Pada saat yang sama, seorang programmer dapat tetap berada dalam satu bahasa dan teknologi yang sama untuk menulis kode cepat.