Perhatian Anda diundang ke ikhtisar kecil tentang kapabilitas vektorisasi algoritma di .NET Framework dan .NETCORE. Tujuan artikel ini adalah untuk memperkenalkan teknik-teknik ini kepada mereka yang tidak mengetahuinya sama sekali dan untuk menunjukkan bahwa .NET tidak ketinggalan jauh di belakang bahasa "nyata, dikompilasi" untuk penduduk asli
pengembangan.
Saya baru mulai mempelajari teknik-teknik vektorisasi, jadi jika seseorang dari komunitas mengarahkan saya ke cant eksplisit, atau menawarkan versi peningkatan dari algoritma yang dijelaskan di bawah ini, saya akan sangat senang.
Sedikit sejarah
Di .NET, SIMD pertama kali muncul pada 2015 dengan dirilisnya .NET Framework 4.6. Kemudian jenis Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3, dan Vector4 ditambahkan, yang memungkinkan pembangunan perhitungan vektor. Kemudian, tipe Vector <T> ditambahkan, yang memberikan lebih banyak peluang untuk algoritma vektorisasi. Tetapi banyak programmer masih tidak senang karena tipe-tipe di atas membatasi aliran pikiran programmer dan tidak memungkinkan kekuatan penuh dari instruksi SIMD dari prosesor modern untuk digunakan. Sudah saat ini, dalam .NET Core 3.0 Preview, System.Runtime.Names intrinsik telah muncul, yang memberikan kebebasan yang jauh lebih besar dalam memilih instruksi. Untuk mendapatkan hasil terbaik dalam kecepatan, Anda harus menggunakan RyuJit dan Anda harus membangun di bawah x64 atau menonaktifkan Prefer 32-bit dan membangun di bawah AnyCPU. Semua tolok ukur yang saya jalankan di komputer dengan prosesor Intel Core i7-6700 3.40GHz (Skylake).
Ringkas elemen-elemen dari array
Saya memutuskan untuk memulai dengan masalah klasik, yang sering ditulis pertama kali tentang vektorisasi. Ini adalah tugas untuk menemukan jumlah elemen array. Kami akan menulis empat implementasi dari tugas ini, kami akan merangkum elemen-elemen dari array Array:
Paling jelas
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Menggunakan LINQ
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
Menggunakan 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; }
Menggunakan kode dari ruang 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 meluncurkan patokan pada 4 metode ini di komputer saya dan mendapatkan hasil ini:
Dapat dilihat bahwa solusi dengan Vektor dan Intrinsik jauh lebih cepat daripada solusi yang jelas dan dengan LINQ. Sekarang kita perlu mencari tahu apa yang terjadi dalam kedua metode ini.
Pertimbangkan metode Vektor secara lebih rinci:
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; - ini adalah berapa banyak angka 4 byte yang dapat kita masukkan ke dalam vektor. Jika akselerasi perangkat keras digunakan, nilai ini menunjukkan berapa banyak angka 4-byte dapat ditempatkan dalam satu register SIMD. Bahkan, ini menunjukkan berapa banyak elemen jenis ini dapat dioperasikan secara paralel;
- accVector - vektor di mana hasil fungsi akan terakumulasi;
var v = Vector baru <int> (array, i); - data dimuat ke dalam vektor v baru, dari array, mulai dari indeks i. Data vectorSize akan memuat. - accVector = Vector.Add (accVector, v); - dua vektor ditambahkan.
Misalnya, 8 angka disimpan dalam Array: {0, 1, 2, 3, 4, 5, 6, 7} dan vectorSize == 4, lalu:
Dalam iterasi pertama dari loop accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3}, setelah penambahan dalam accVector akan menjadi: {0, 0, 0, 0} + {0, 1, 2 , 3} = {0, 1, 2, 3}.
Dalam iterasi kedua, v = {4, 5, 6, 7} dan setelah penambahan accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Tetap hanya untuk entah bagaimana mendapatkan jumlah semua elemen vektor, untuk ini kita dapat menerapkan perkalian skalar dengan vektor yang diisi dengan unit: int result = Vector.Dot (accVector, Vector <int> .One);
Kemudian hasilnya: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28. - Pada akhirnya, jika diperlukan, maka angka ditambahkan yang tidak sesuai dengan vektor terakhir.
Jika Anda melihat kode metode Intrinsics:
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; }
Anda dapat melihat bahwa ini sangat mirip dengan Vektor dengan beberapa pengecualian:
Bandingkan dua array
Perlu untuk membandingkan dua array byte. Sebenarnya ini adalah masalah karena itu saya mulai belajar SIMD di .NET. Sekali lagi, kami akan menulis beberapa metode untuk benchmark, kami akan 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 melalui LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
Solusi melalui 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;
Menggunakan 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; }
Menggunakan 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 patokan di komputer saya:
Semua kode untuk metode ini, saya pikir, jelas, dengan pengecualian dua baris dalam Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
Dalam yang pertama, dua vektor dibandingkan untuk kesetaraan dan hasilnya disimpan dalam vektor areEqual, di mana semua bit diatur ke 1 dalam elemen pada posisi tertentu jika elemen yang sesuai dalam va dan vb sama. Ternyata jika vektor dari byte va dan vb benar-benar sama, maka dalam areEquals semua elemen harus sama dengan 255 (11111111b). Karena Avx2.CompareEqual adalah pembungkus di atas _mm256_cmpeq_epi8, maka di situs web Intel Anda dapat melihat kode semu dari operasi ini:
Metode MoveMask dari vektor menghasilkan angka 32-bit. Nilai bit adalah bit tinggi dari masing-masing 32 elemen byte tunggal dari vektor. Kodesemu dapat ditemukan di sini .
Jadi, jika beberapa byte dalam va dan vb tidak cocok, maka dalam areEqual byte yang sesuai akan menjadi 0, oleh karena itu bit yang paling signifikan dari byte ini juga akan 0, yang berarti bahwa bit yang sesuai dalam respons Avx2.MoveMask juga akan 0 dan perbandingan dengan equalsMask tidak akan berfungsi.
Mari kita menganalisis contoh kecil, dengan asumsi bahwa panjang vektor adalah 8 byte (untuk menulis itu kurang):
- Misalkan va = {100, 10, 20, 30, 100, 40, 50, 100}, dan vb = {100, 20, 10, 30, 100, 40, 80, 90};
- Maka areEqual akan sama dengan {255, 0, 0, 255, 255, 255, 0, 0};
- Metode MoveMask akan mengembalikan 10011100b, yang perlu dibandingkan dengan mask 11111111b, karena Karena topeng ini tidak sama, ternyata vektor va dan vb tidak sama.
Hitung berapa kali suatu elemen muncul dalam koleksi
Terkadang perlu untuk menghitung berapa kali elemen tertentu ditemukan dalam koleksi, misalnya int, algoritma ini juga dapat dipercepat. Mari kita menulis beberapa metode untuk perbandingan, kita akan mencari elemen Item dalam array 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;
Hasil patokan di komputer saya:
Metode Vektor dan Intrinsik sepenuhnya identik dalam logika, perbedaannya hanya dalam pelaksanaan operasi tertentu. Idenya secara keseluruhan adalah:
- vektor topeng dibuat di mana nomor yang diperlukan disimpan di setiap elemen;
- Bagian array dimasukkan ke dalam vektor v dan dibandingkan dengan mask, maka semua bit akan diatur dalam elemen yang sama di areEqual, karena areEqual adalah vektor dari ints, maka jika Anda mengatur semua bit dari satu elemen, kita mendapatkan -1 pada elemen ini ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- vektor areEqual dikurangi dari accVector dan kemudian accVector akan menjadi jumlah berapa kali elemen item terjadi di semua vektor v untuk setiap posisi (minus min memberi nilai tambah).
Semua kode dari artikel dapat ditemukan di GitHub
Kesimpulan
Saya memeriksa hanya sebagian kecil dari kemungkinan yang disediakan oleh .NET untuk perhitungan vektorisasi. Untuk daftar intrinsik yang lengkap dan terkini di .NETCORE di bawah x86, Anda dapat merujuk ke kode sumber . Sangat nyaman bahwa dalam file C # dalam ringkasan masing-masing intrinsik ada namanya sendiri dari dunia C, yang menyederhanakan pemahaman tentang tujuan intrinsik ini dan terjemahan dari algoritma C ++ / C yang ada ke .NET. Dokumentasi System.Numerics.Vector tersedia di msdn .
Menurut pendapat saya, .NET memiliki keunggulan besar dibandingkan C ++, karena .NET Kompilasi JIT sudah terjadi pada mesin klien, kompiler dapat mengoptimalkan kode untuk prosesor klien tertentu, memberikan kinerja maksimum. Pada saat yang sama, seorang programmer untuk menulis kode cepat dapat tetap berada dalam kerangka satu bahasa dan teknologi.
UPD (15/9/2019):
Ada patokan di tolok ukurDalam benchmark, saya menggunakan IterationSetup, yang, ternyata, dapat sangat mempengaruhi kinerja benchmark yang bekerja dalam waktu kurang dari 100 ms. Jika Anda mengulanginya di GlobalSetup, maka hasilnya akan seperti ini.
Jumlah elemen array:
Membandingkan dua array:
Jumlah kemunculan elemen dalam array: