Tentang artikel

Posting ini adalah catatan singkat untuk programmer yang ingin mempelajari lebih lanjut tentang bagaimana GPU menangani percabangan. Anda bisa menganggapnya sebagai pengantar topik ini. Saya sarankan mulai dengan [ 1 ], [ 2 ] dan [ 8 ] untuk mendapatkan gambaran tentang bagaimana model pelaksanaan GPU secara umum, karena kami hanya akan mempertimbangkan satu detail terpisah. Untuk pembaca yang ingin tahu, ada semua tautan di akhir posting. Jika Anda menemukan kesalahan, maka hubungi saya.

Isi

• Tentang artikel
• Isi
• Kosakata
• Apa perbedaan inti GPU dari inti CPU?
• Apa itu konsistensi / perbedaan?
• Contoh pemrosesan topeng eksekusi
  • ISA fiksi
  • AMD GCN ISA
  • AVX512
• Bagaimana cara mengatasi ketidaksesuaian?
• Referensi

Kosakata

• GPU - Unit pemrosesan grafik, GPU
• Klasifikasi Flynn
  
  • SIMD - Instruksi tunggal beberapa data, aliran instruksi tunggal, banyak aliran data
  • SIMT - Instruksi tunggal beberapa utas, aliran instruksi tunggal, banyak utas
• Wave (SIM) - aliran yang dijalankan dalam mode SIMD
• Line (lane) - aliran data terpisah dalam model SIMD
• SMT - Multithreading simultan, multithreading simultan (Intel Hyper-threading) [ 2 ]
  
  • Beberapa utas berbagi sumber daya komputasi inti
• IMT - Interleaved multi-threading, bolak-balik multithreading [ 2 ]
  
  • Beberapa utas membagikan total sumber daya komputasi kernel, tetapi hanya satu
• BB - Blok Dasar, blok dasar - urutan instruksi linear dengan satu lompatan di akhir
• ILP - Instruction Level Parallelism, parallelism di level instruksi [ 3 ]
• ISA - Arsitektur Set Instruksi, arsitektur set instruksi

Dalam posting saya, saya akan mematuhi klasifikasi yang ditemukan ini. Ini kira-kira menyerupai bagaimana GPU modern diatur.

:
GPU -+
|- 0 -+
| |- 0 +
| | |- 0
| | |- 1
| | |- ...
| | +- Q-1
| |
| |- ...
| +- M-1
|
|- ...
+- N-1

* - SIMD

:
+
|- 0
|- ...
+- N-1

Nama lain:

• Inti dapat disebut CU, SM, EU
• Gelombang dapat disebut gelombang muka, utas perangkat keras (utas HW), warp, konteks
• Garis dapat disebut utas program (utas SW)

Apa perbedaan inti GPU dari inti CPU?

Setiap core GPU saat ini kurang kuat dari prosesor sentral: ILP sederhana / multi-masalah [ 6 ] dan prefetch [ 5 ], tidak ada prakiraan atau prediksi transisi / pengembalian. Semua ini, bersama dengan cache kecil, membebaskan area yang cukup besar pada chip, yang diisi dengan banyak core. Mekanisme pemuatan / penyimpanan memori mampu mengatasi lebar saluran dengan urutan yang lebih besar (ini tidak berlaku untuk GPU terintegrasi / seluler) daripada CPU konvensional, tetapi Anda harus membayar untuk ini dengan latensi tinggi. Untuk menyembunyikan latensi, GPU menggunakan SMT [ 2 ] - saat satu gelombang menganggur, yang lain menggunakan sumber daya komputasi gratis dari kernel. Biasanya jumlah gelombang yang diproses oleh satu inti tergantung pada register yang digunakan dan ditentukan secara dinamis dengan mengalokasikan file register tetap [ 8 ]. Perencanaan untuk pelaksanaan instruksi adalah hybrid - dynamic-static [ 6 ] [ 11 4.4]. Kernel SMT yang dieksekusi dalam mode SIMD mencapai nilai FLOPS yang tinggi (Operasi titik-Mengapung Per Detik, jepit, jumlah operasi titik apung per detik).



Bagan legenda. Hitam - tidak aktif, putih - aktif, abu - abu, biru - siaga, merah - tertunda


Gambar 1. 4: 2 riwayat eksekusi

Gambar menunjukkan sejarah topeng eksekusi, di mana sumbu x menunjukkan waktu dari kiri ke kanan, dan sumbu y menunjukkan pengidentifikasi garis dari atas ke bawah. Jika Anda masih tidak mengerti ini, maka kembali ke gambar setelah membaca bagian berikut.

Ini adalah ilustrasi bagaimana sejarah eksekusi inti GPU dapat terlihat dalam konfigurasi fiktif: empat gelombang berbagi satu sampler dan dua ALU. Perencana gelombang dalam setiap siklus mengeluarkan dua instruksi dari dua gelombang. Ketika gelombang menganggur saat melakukan akses ke memori atau operasi ALU yang panjang, penjadwal beralih ke pasangan gelombang lainnya, karena itu ALU terus-menerus ditempati oleh hampir 100%.


Gambar 2. Sejarah eksekusi 4: 1

Contoh dengan beban yang sama, tetapi kali ini dalam setiap siklus instruksi hanya satu masalah gelombang. Perhatikan bahwa ALU kedua adalah kelaparan.


Gambar 3. Sejarah eksekusi 4: 4

Kali ini, empat instruksi dikeluarkan dalam setiap siklus. Perhatikan bahwa ada terlalu banyak permintaan untuk ALU, sehingga dua gelombang hampir selalu menunggu (pada kenyataannya, ini adalah kesalahan dari algoritma perencanaan).

Pembaruan Untuk informasi lebih lanjut tentang kesulitan merencanakan pelaksanaan instruksi, lihat [ 12 ].

Di dunia nyata, GPU memiliki konfigurasi inti yang berbeda: beberapa dapat memiliki hingga 40 gelombang per inti dan 4 ALU, yang lain memiliki 7 gelombang tetap dan 2 ALU. Semua ini tergantung pada banyak faktor dan ditentukan berkat proses simulasi arsitektur yang melelahkan.

Selain itu, ALU SIMD nyata mungkin memiliki lebar lebih sempit daripada gelombang yang mereka layani, dan kemudian dibutuhkan beberapa siklus untuk memproses satu instruksi yang dikeluarkan; faktornya disebut panjang "chime" [ 3 ].

Apa itu konsistensi / perbedaan?

Mari kita lihat cuplikan kode berikut:

Contoh 1

 uint lane_id = get_lane_id(); if (lane_id & 1) { // Do smth } // Do some more 

Di sini kita melihat aliran instruksi di mana jalur eksekusi tergantung pada pengidentifikasi baris yang dieksekusi. Jelas, garis yang berbeda memiliki arti yang berbeda. Apa yang akan terjadi? Ada beberapa pendekatan berbeda untuk menyelesaikan masalah ini [ 4 ], tetapi pada akhirnya mereka semua melakukan hal yang sama. Salah satu pendekatan tersebut adalah topeng eksekusi, yang akan saya bahas. Pendekatan ini digunakan di GPU Nvidia sebelum Volta dan di AMD GCN GPU. Poin utama dari topeng eksekusi adalah bahwa kami menyimpan sedikit untuk setiap baris dalam wave. Jika bit eksekusi baris yang sesuai adalah 0, maka register tidak akan terpengaruh untuk instruksi berikutnya yang dikeluarkan. Bahkan, garis seharusnya tidak merasakan pengaruh dari seluruh instruksi yang dieksekusi, karena bit eksekusi adalah 0. Ini berfungsi sebagai berikut: gelombang bergerak di sepanjang grafik aliran kontrol dalam urutan pencarian mendalam, menyimpan sejarah transisi yang dipilih sampai bit ditetapkan. Saya pikir lebih baik menunjukkannya dengan contoh.

Misalkan kita memiliki gelombang dengan lebar 8. Berikut ini adalah topeng eksekusi untuk fragmen kode:

Contoh 1. Sejarah topeng eksekusi

  // execution mask uint lane_id = get_lane_id(); // 11111111 if (lane_id & 1) { // 11111111 // Do smth // 01010101 } // Do some more // 11111111 

Sekarang perhatikan contoh yang lebih kompleks:

Contoh 2

 uint lane_id = get_lane_id(); for (uint i = lane_id; i < 16; i++) { // Do smth } 

Contoh 3

 uint lane_id = get_lane_id(); if (lane_id < 16) { // Do smth } else { // Do smth else } 

Anda mungkin memperhatikan bahwa sejarah diperlukan. Saat menggunakan pendekatan topeng eksekusi, peralatan biasanya menggunakan semacam tumpukan. Pendekatan naif adalah untuk menyimpan setumpuk tupel (exec_mask, alamat) dan menambahkan instruksi konvergensi yang mengambil topeng dari tumpukan dan mengubah pointer instruksi untuk gelombang. Dalam hal ini, wave akan memiliki informasi yang cukup untuk mem-bypass seluruh CFG untuk setiap baris.

Dalam hal kinerja, hanya diperlukan beberapa putaran untuk memproses instruksi aliran kontrol karena semua penyimpanan data ini. Dan jangan lupa bahwa stack memiliki kedalaman yang terbatas.

Perbarui. Berkat @craigkolb, saya membaca sebuah artikel [ 13 ], yang mencatat bahwa fork / gabung AMD GCN pertama-tama memilih jalur dari lebih sedikit utas [ 11 4.6], yang menjamin bahwa kedalaman tumpukan masker sama dengan log2.

Perbarui. Jelas, hampir selalu mungkin untuk menanamkan semuanya dalam shader / struktur CFG dalam shader, dan oleh karena itu menyimpan seluruh sejarah topeng eksekusi dalam register dan merencanakan bypass / konvergen CFG secara statis [ 15 ]. Setelah melihat backend LLVM untuk AMDGPU, saya tidak menemukan bukti penanganan tumpukan yang terus-menerus dikeluarkan oleh kompiler.

Dukungan perangkat keras Runtime mask

Sekarang lihat grafik aliran kontrol ini dari Wikipedia:


Gambar 4. Beberapa jenis grafik aliran kontrol

Apa set minimum instruksi kontrol topeng yang kita butuhkan untuk menangani semua kasus? Inilah yang terlihat dalam ISA buatan saya dengan paralelisasi implisit, kontrol topeng eksplisit, dan sinkronisasi dinamis penuh konflik data:

 push_mask BRANCH_END ; Push current mask and reconvergence pointer pop_mask ; Pop mask and jump to reconvergence instruction mask_nz r0.x ; Set execution bit, pop mask if all bits are zero ; Branch instruction is more complicated ; Push current mask for reconvergence ; Push mask for (r0.x == 0) for else block, if any lane takes the path ; Set mask with (r0.x != 0), fallback to else in case no bit is 1 br_push r0.x, ELSE, CONVERGE 

Mari kita lihat kasus d).

 A: br_push r0.x, C, D B: C: mask_nz r0.y jmp B D: ret 

Saya bukan spesialis dalam menganalisis aliran kontrol atau merancang ISA, jadi saya yakin ada kasus bahwa ISA buatan saya tidak akan mampu mengatasinya, tetapi ini tidak penting, karena CFG terstruktur harus cukup untuk semua orang.

Perbarui. Baca lebih lanjut tentang dukungan GCN untuk instruksi aliran kontrol di sini: [ 11 ] bab.4, dan tentang implementasi LLVM di sini: [ 15 ].

Kesimpulan:

• Divergence - perbedaan yang dihasilkan pada jalur yang dipilih oleh garis berbeda dari gelombang yang sama
• Konsistensi - tidak ada perbedaan.

Contoh pemrosesan topeng eksekusi

ISA fiksi

Saya mengkompilasi cuplikan kode sebelumnya di ISA buatan saya dan menjalankannya di simulator di SIMD32. Lihat bagaimana menangani topeng eksekusi.

Perbarui. Perhatikan bahwa simulator buatan selalu memilih jalur yang benar, dan ini bukan cara terbaik.

Contoh 1

 ; uint lane_id = get_lane_id(); mov r0.x, lane_id ; if (lane_id & 1) { push_mask BRANCH_END and r0.y, r0.x, u(1) mask_nz r0.y LOOP_BEGIN: ; // Do smth pop_mask ; pop mask and reconverge BRANCH_END: ; // Do some more ret 

Gambar 5. Sejarah contoh 1

Apakah Anda memperhatikan area hitam? Kali ini sia-sia. Beberapa baris menunggu yang lain untuk menyelesaikan iterasi.

Contoh 2

 ; uint lane_id = get_lane_id(); mov r0.x, lane_id ; for (uint i = lane_id; i < 16; i++) { push_mask LOOP_END ; Push the current mask and the pointer to reconvergence instruction LOOP_PROLOG: lt.u32 r0.y, r0.x, u(16) ; r0.y <- r0.x < 16 add.u32 r0.x, r0.x, u(1) ; r0.x <- r0.x + 1 mask_nz r0.y ; exec bit <- r0.y != 0 - when all bits are zero next mask is popped LOOP_BEGIN: ; // Do smth jmp LOOP_PROLOG LOOP_END: ; // } ret 

Gambar 6. Sejarah contoh 2

Contoh 3

  mov r0.x, lane_id lt.u32 r0.y, r0.x, u(16) ; if (lane_id < 16) { ; Push (current mask, CONVERGE) and (else mask, ELSE) ; Also set current execution bit to r0.y != 0 br_push r0.y, ELSE, CONVERGE THEN: ; // Do smth pop_mask ; } else { ELSE: ; // Do smth else pop_mask ; } CONVERGE: ret 

Gambar 7. Sejarah contoh 3

AMD GCN ISA

Perbarui. GCN juga menggunakan pemrosesan topeng eksplisit, lebih lanjut tentang ini dapat ditemukan di sini: [ 11 4.x]. Saya memutuskan untuk menunjukkan beberapa contoh dari ISA mereka, berkat shader-playground, ini mudah dilakukan. Mungkin suatu hari nanti saya akan menemukan simulator dan berhasil mendapatkan diagram.

Ingatlah bahwa kompiler cerdas, sehingga Anda bisa mendapatkan hasil lainnya. Saya mencoba mengelabui kompiler sehingga tidak akan mengoptimalkan cabang saya dengan meletakkan loop pointer di sana dan kemudian membersihkan kode assembler; Saya bukan spesialis GCN, jadi beberapa nop penting mungkin dilewati.

Juga perhatikan bahwa instruksi S_CBRANCH_I / G_FORK dan S_CBRANCH_JOIN tidak digunakan dalam fragmen ini karena mereka sederhana dan kompiler tidak mendukungnya. Karena itu, sayangnya, tidak mungkin untuk mempertimbangkan tumpukan topeng. Jika Anda tahu cara membuat pemrosesan tumpukan masalah kompiler, tolong beri tahu saya.

Perbarui. Lihat ini @ SiNGUL4RiTY bicara tentang menerapkan aliran kontrol vektor di backend LLVM yang digunakan oleh AMD.

Contoh 1

 ; uint lane_id = get_lane_id(); ; GCN uses 64 wave width, so lane_id = thread_id & 63 ; There are scalar s* and vector v* registers ; Executon mask does not affect scalar or branch instructions v_mov_b32 v1, 0x00000400 ; 1024 - group size v_mad_u32_u24 v0, s12, v1, v0 ; thread_id calculation v_and_b32 v1, 63, v0 ; if (lane_id & 1) { v_and_b32 v2, 1, v0 s_mov_b64 s[0:1], exec ; Save the execution mask v_cmpx_ne_u32 exec, v2, 0 ; Set the execution bit s_cbranch_execz ELSE ; Jmp if all exec bits are zero ; // Do smth ELSE: ; } ; // Do some more s_mov_b64 exec, s[0:1] ; Restore the execution mask s_endpgm 

Contoh 2

 ; uint lane_id = get_lane_id(); v_mov_b32 v1, 0x00000400 v_mad_u32_u24 v0, s8, v1, v0 ; Not sure why s8 this time and not s12 v_and_b32 v1, 63, v0 ; LOOP PROLOG s_mov_b64 s[0:1], exec ; Save the execution mask v_mov_b32 v2, v1 v_cmp_le_u32 vcc, 16, v1 s_andn2_b64 exec, exec, vcc ; Set the execution bit s_cbranch_execz LOOP_END ; Jmp if all exec bits are zero ; for (uint i = lane_id; i < 16; i++) { LOOP_BEGIN: ; // Do smth v_add_u32 v2, 1, v2 v_cmp_le_u32 vcc, 16, v2 s_andn2_b64 exec, exec, vcc ; Mask out lanes which are beyond loop limit s_cbranch_execnz LOOP_BEGIN ; Jmp if non zero exec mask LOOP_END: ; // } s_mov_b64 exec, s[0:1] ; Restore the execution mask s_endpgm 

Contoh 3

 ; uint lane_id = get_lane_id(); v_mov_b32 v1, 0x00000400 v_mad_u32_u24 v0, s12, v1, v0 v_and_b32 v1, 63, v0 v_and_b32 v2, 1, v0 s_mov_b64 s[0:1], exec ; Save the execution mask ; if (lane_id < 16) { v_cmpx_lt_u32 exec, v1, 16 ; Set the execution bit s_cbranch_execz ELSE ; Jmp if all exec bits are zero ; // Do smth ; } else { ELSE: s_andn2_b64 exec, s[0:1], exec ; Inverse the mask and & with previous s_cbranch_execz CONVERGE ; Jmp if all exec bits are zero ; // Do smth else ; } CONVERGE: s_mov_b64 exec, s[0:1] ; Restore the execution mask ; // Do some more s_endpgm 

AVX512

Perbarui. @tom_forsyth menunjukkan kepada saya bahwa ekstensi AVX512 juga memiliki pemrosesan topeng eksplisit, jadi di sini adalah beberapa contoh. Rincian lebih lanjut tentang ini dapat ditemukan di [ 14 ], 15.x dan 15.6.1. Ini bukan GPU, tetapi masih memiliki SIMD16 nyata dengan 32 bit. Cuplikan kode dibuat menggunakan godbolt ISPC (–target = avx512knl-i32x16) dan didesain ulang secara ketat, sehingga mungkin tidak 100% benar.

Contoh 1

  ; Imagine zmm0 contains 16 lane_ids ; AVXZ512 comes with k0-k7 mask registers ; Usage: ; op reg1 {k[7:0]}, reg2, reg3 ; k0 can not be used as a predicate operand, only k1-k7 ; if (lane_id & 1) { vpslld zmm0 {k1}, zmm0, 31 ; zmm0[i] = zmm0[i] << 31 kmovw eax, k1 ; Save the execution mask vptestmd k1 {k1}, zmm0, zmm0 ; k1[i] = zmm0[i] != 0 kortestw k1, k1 je ELSE ; Jmp if all exec bits are zero ; // Do smth ; Now k1 contains the execution mask ; We can use it like this: ; vmovdqa32 zmm1 {k1}, zmm0 ELSE: ; } kmovw k1, eax ; Restore the execution mask ; // Do some more ret 

Contoh 2

  ; Imagine zmm0 contains 16 lane_ids kmovw eax, k1 ; Save the execution mask vpcmpltud k1 {k1}, zmm0, 16 ; k1[i] = zmm0[i] < 16 kortestw k1, k1 je LOOP_END ; Jmp if all exec bits are zero vpternlogd zmm1 {k1}, zmm1, zmm1, 255 ; zmm1[i] = -1 ; for (uint i = lane_id; i < 16; i++) { LOOP_BEGIN: ; // Do smth vpsubd zmm0 {k1}, zmm0, zmm1 ; zmm0[i] = zmm0[i] + 1 vpcmpltud k1 {k1}, zmm0, 16 ; masked k1[i] = zmm0[i] < 16 kortestw k1, k1 jne LOOP_BEGIN ; Break if all exec bits are zero LOOP_END: ; // } kmovw k1, eax ; Restore the execution mask ; // Do some more ret 

Contoh 3

  ; Imagine zmm0 contains 16 lane_ids ; if (lane_id & 1) { vpslld zmm0 {k1}, zmm0, 31 ; zmm0[i] = zmm0[i] << 31 kmovw eax, k1 ; Save the execution mask vptestmd k1 {k1}, zmm0, zmm0 ; k1[i] = zmm0[i] != 0 kortestw k1, k1 je ELSE ; Jmp if all exec bits are zero THEN: ; // Do smth ; } else { ELSE: kmovw ebx, k1 andn ebx, eax, ebx kmovw k1, ebx ; mask = ~mask & old_mask kortestw k1, k1 je CONVERGE ; Jmp if all exec bits are zero ; // Do smth else ; } CONVERGE: kmovw k1, eax ; Restore the execution mask ; // Do some more ret 

Bagaimana cara mengatasi ketidaksesuaian?

Saya mencoba membuat ilustrasi sederhana namun lengkap tentang bagaimana inefisiensi muncul dari penggabungan garis yang berbeda.

Bayangkan sepotong kode sederhana:

 uint thread_id = get_thread_id(); uint iter_count = memory[thread_id]; for (uint i = 0; i < iter_count; i++) { // Do smth } 

Mari buat 256 utas dan ukur waktu eksekusi mereka:


Gambar 8. Durasi utas yang berbeda

Sumbu x adalah pengidentifikasi aliran program, sumbu y adalah siklus jam; kolom yang berbeda menunjukkan berapa banyak waktu yang terbuang ketika pengelompokan mengalir dengan panjang gelombang yang berbeda dibandingkan dengan eksekusi single-threaded.

Gelombang waktu berjalan sama dengan waktu lari maksimum di antara garis yang terkandung di dalamnya. Anda dapat melihat bahwa kinerja turun secara dramatis dengan SIMD8, dan ekspansi lebih lanjut hanya membuatnya sedikit lebih buruk.


Gambar 9. Runtime dari utas yang konsisten

Kolom yang sama ditunjukkan pada gambar ini, tetapi kali ini jumlah iterasi diurutkan berdasarkan pengidentifikasi aliran, yaitu, stream dengan jumlah iterasi yang sama ditransmisikan ke satu gelombang.

Untuk contoh ini, eksekusi berpotensi dipercepat sekitar setengahnya.

Tentu saja, contohnya terlalu sederhana, tetapi saya harap Anda mengerti intinya: perbedaan pada eksekusi berasal dari perbedaan data, jadi CFG harus sederhana dan datanya konsisten.

Misalnya, jika Anda menulis pelacak sinar, Anda dapat mengambil manfaat dari pengelompokan sinar dengan arah dan posisi yang sama, karena mereka kemungkinan besar akan melalui node yang sama di BVH. Lihat [ 10 ] dan artikel terkait lainnya untuk lebih jelasnya.

Perlu juga disebutkan bahwa ada teknik untuk berurusan dengan perbedaan pada tingkat perangkat keras, misalnya, Dynamic Warp Formation [ 7 ] dan prediksi eksekusi untuk cabang-cabang kecil.

Referensi

[1] Perjalanan melalui Graphics Pipeline

[2] Kayvon Fatahalian: COMPUTING PARALLEL

[3] Arsitektur Komputer Suatu Pendekatan Kuantitatif

[4] Konvergensi SIMT tanpa tumpukan dengan biaya rendah

[5] Membedah hierarki memori GPU melalui microbenchmarking

[6] Membedah Arsitektur GPU NVIDIA Volta melalui Microbenchmarking

[7] Formasi dan Penjadwalan Warp Dinamis untuk Aliran Kontrol GPU yang Efisien

[8] Maurizio Cerrato: Arsitektur GPU

[9] Toy GPU simulator

[10] Mengurangi Branch Divergence dalam Program GPU

[11] Arsitektur “Instruksi Set“ Vega ”

[12] Joshua Barczak: Mensimulasikan Eksekusi Shader untuk GCN

[13] Tangent Vector: A Digression on Divergence

[14] Manual Pengembang Intel 64 dan IA-32 ArchitecturesSoftware

[15] Aliran Kontrol Divergen Variasi untuk Aplikasi SIMD