Hilangkan Divergensi Warp

Sebuah warp terdiri atas 32 utas yang menjalankan instruksi yang sama secara bersamaan. Saat jalurnya sama, perangkat keras berjalan dengan kecepatan penuh.

Jika utas dalam sebuah warp mengambil cabang yang berbeda, itulah divergensi. Perangkat keras menjalankan setiap jalur secara berurutan, sehingga beberapa lajur menganggur dan siklus terbuang.

Versi sederhana menggunakan tid % (2*s) untuk memilih utas aktif. Utas aktif dan menganggur berselang-seling di dalam setiap warp, sehingga setiap warp mengalami divergensi parah.

Meskipun separuh utas tidak melakukan apa-apa, utas-utas tersebut tetap menempati warp. Warp tidak dapat selesai sampai jalur aktif dan jalur menganggur sama-sama ditangani.

Perbaikannya adalah memetakan pekerjaan aktif ke ID utas terendah, bukan ke ID yang tersebar. Hitung indeks dari tid dan stride.

Sekarang utas yang sibuk menjadi berurutan: tid 0,1,2,... semuanya bekerja, sedangkan sisanya beristirahat. Warp secara keseluruhan menjadi aktif penuh atau menganggur penuh.

Warp yang setiap lajurnya menganggur akan selesai tanpa pekerjaan. Tidak ada serialisasi per lajur, sehingga biaya divergensi sebagian besar hilang.

Penyebab tersembunyinya adalah kondisi modulo. Kondisi tersebut menyebarkan utas aktif di setiap warp, yang persis menyebabkan divergensi.

Anda tidak mengubah matematika atau jumlah penjumlahan. Anda hanya memetakan ulang utas mana yang melakukan setiap penjumlahan, dan warp pun diuntungkan.

Di ribuan blok dan banyak langkah, menghilangkan divergensi menghasilkan percepatan nyata, sering kali dua kali lebih cepat daripada kernel naif.

Versi ini membaca tetangga yang berselang-seling di memori bersama, yang dapat menyebabkan konflik bank. Pelajaran berikutnya juga akan memperbaikinya.

Anda menghilangkan divergensi dengan memberikan pekerjaan kepada ID thread terendah, sehingga semua warp aktif atau semuanya tidak aktif. Perhitungannya sama, tetapi reduksinya lebih cepat. Berikutnya: konflik bank. 🚀