Mengapa efisiensi kerja diinginkan dalam pemrograman GPU?

Saya telah membaca artikel berikut tentang cara melakukan pemindaian paralel di CUDA:

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html

Dalam artikel tersebut, ada penekanan untuk membuat pemindaian "bekerja efisien". Dengan kata lain, algoritma GPU tidak boleh melakukan penambahan lebih dari algoritma CPU, O (n). Para penulis menyajikan dua algoritma, satu "naif" yang melakukan penambahan O (nlogn), dan satu yang mereka anggap "bekerja efisien". Namun, algoritma kerja efisien melakukan iterasi loop dua kali lebih banyak.

Dari pemahaman saya, GPU hanyalah prosesor SIMD raksasa dan harus beroperasi pada langkah-kunci. Melakukan loop dua kali lebih banyak dalam algoritma "bekerja efisien" tampaknya menyiratkan bahwa banyak utas akan menganggur dan menurunkan kinerja dalam jangka panjang. Apa yang saya lewatkan?

Pertama-tama, ulang: "GPU hanyalah prosesor SIMD raksasa dan harus beroperasi dalam kunci-langkah", ini sedikit lebih rumit dari itu. The seluruh GPU tidak berjalan berbaris. Thread shader diorganisasikan ke dalam kelompok 32 yang disebut "warps" (di NVIDIA; di AMD mereka adalah kelompok 64 yang disebut "wavefronts", tetapi konsep yang sama). Dalam sebuah warp, semua utas berjalan berbaris sebagai array SIMD. Namun, warp yang berbeda tidak saling berhadapan. Selain itu, beberapa warps mungkin aktif berjalan sementara yang lain mungkin ditangguhkan, mirip seperti utas CPU. Warps dapat ditunda karena mereka sedang menunggu sesuatu (seperti transaksi memori untuk kembali atau hambatan untuk dihapus), atau karena tidak ada

Sekarang, kembali ke pertanyaan Anda. Saya dapat melihat dua cara bahwa algoritma "bekerja efisien" dari makalah itu tampaknya akan lebih efisien daripada algoritma "naif".

1. Versi yang efisien untuk pekerjaan membutuhkan setengah utas untuk memulai. Dalam algoritma naif, mereka memiliki satu utas per elemen array; tetapi dalam versi yang efisien-kerja, setiap utas beroperasi pada dua elemen yang berdekatan dari array dan karenanya mereka hanya membutuhkan setengah dari jumlah utas sebagai elemen array. Semakin sedikit utas berarti semakin sedikit warps, sehingga sebagian kecil dari warps dapat aktif berjalan.

2. Meskipun versi yang efisien untuk pekerjaan membutuhkan lebih banyak langkah, ini diimbangi oleh fakta bahwa jumlah utas aktif berkurang lebih cepat, dan jumlah total utas aktif di semua iterasi jauh lebih kecil. Jika sebuah lungsin tidak memiliki utas aktif selama iterasi, lungsin itu hanya akan melompat ke penghalang berikut dan ditangguhkan, yang memungkinkan lungsin lain untuk berjalan. Jadi, memiliki warps aktif yang lebih sedikit sering dapat membayar dalam waktu eksekusi. (Secara implisit dalam hal ini adalah bahwa kode GPU perlu dirancang sedemikian rupa sehingga utas aktif dipersatukan menjadi beberapa warps mungkin — Anda tidak ingin mereka tersebar jarang, karena bahkan satu utas aktif akan memaksa seluruh lungsin untuk tetap aktif.)

   Pertimbangkan jumlah utas aktif dalam algoritma naif. Melihat Gambar 2 dalam artikel, Anda dapat melihat bahwa semua utas aktif kecuali untuk 2 ^k pertama pada iterasi k . Jadi dengan N utas, jumlah utas aktif seperti N - 2 ^k . Misalnya, dengan N = 1024, jumlah utas aktif per iterasi adalah:

   1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
   

   Jika saya mengonversikan ini ke jumlah warps aktif (dengan membaginya menjadi 32 dan mengumpulkannya), saya mendapatkan:

   32, 32, 32, 32, 32, 31, 30, 28, 24, 16
   

   untuk jumlah 289. Di sisi lain, algoritma kerja-efisien dimulai dengan setengah utas, kemudian membagi dua jumlah yang aktif pada setiap iterasi sampai turun ke 1, kemudian mulai dua kali lipat hingga kembali ke setengah ukuran array lagi:

    512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
   

   Konversi ini ke warps aktif:

   16, 8, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16
   

   Jumlahnya 71, yang hanya seperempat. Jadi Anda dapat melihat bahwa selama seluruh operasi, jumlah warps aktif jauh lebih kecil dengan algoritma yang efisien kerja. (Bahkan, untuk jangka panjang di tengah hanya ada beberapa warp aktif, yang berarti sebagian besar chip tidak ditempati. Jika ada tugas komputasi tambahan yang berjalan, misalnya dari aliran CUDA lain, mereka dapat memperluas untuk mengisi itu ruang kosong.)

Semua yang dikatakan, sangat disayangkan bahwa artikel Permata GPU tidak jelas menjelaskan semua ini, melainkan berfokus pada analisis "jumlah penambahan" besar-O yang, meskipun tidak sepenuhnya tidak relevan, melewatkan banyak detail tentang mengapa algoritma ini lebih cepat.