Mengapa perbandingan begitu mahal pada GPU?

Ketika mencoba untuk meningkatkan kinerja kelas deteksi tabrakan saya, saya menemukan bahwa ~ 80% dari waktu yang dihabiskan di GPU, dihabiskan untuk jika kondisi lain hanya mencoba mencari batas untuk ember yang harus dilingkari.

Lebih tepatnya:

1. setiap utas mendapat ID, dengan ID itu ia mengambil segitiga dari memori (masing-masing 3 bilangan bulat) dan oleh mereka 3 ia mengambil simpulnya (masing-masing 3 mengapung).

2. Kemudian mengubah simpul menjadi titik-titik kotak integer (saat ini 8x8x8) dan mengubahnya menjadi batas segitiga pada kotak itu

3. Untuk mengubah 3 titik menjadi batas, ia menemukan min / maks dari setiap dimensi di antara masing-masing titik

Karena bahasa pemrograman yang saya gunakan tidak memiliki intrinsik minmax, saya membuatnya sendiri, terlihat seperti ini:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

Jadi rata-rata seharusnya perbandingan 2,5 * 3 * 3 = 22,5 yang berakhir memakan waktu jauh lebih banyak daripada tes persimpangan segitiga-tepi yang sebenarnya (sekitar 100 * 11-50 instruksi).

Bahkan, saya menemukan bahwa pre-menghitung ember yang diperlukan pada cpu (berulir tunggal, tidak ada vektorisasi), menumpuknya dalam tampilan gpu bersama dengan definisi bucket dan membuat gpu melakukan ~ 4 pembacaan tambahan per thread adalah 6 kali lebih cepat daripada mencoba untuk mencari tahu batas di tempat. (perhatikan bahwa mereka akan dihitung ulang sebelum setiap eksekusi karena saya berurusan dengan jaring dinamis)

Jadi mengapa perbandingannya begitu lambat pada GPU?

GPU adalah arsitektur SIMD. Dalam arsitektur SIMD, setiap instruksi perlu dijalankan untuk setiap elemen yang Anda proses. (Ada pengecualian untuk aturan ini, tetapi jarang membantu).

Jadi dalam MinMaxrutinitas Anda, tidak hanya setiap panggilan perlu mengambil ketiga instruksi cabang, (bahkan jika rata-rata hanya 2,5 dievaluasi), tetapi setiap pernyataan penugasan mengambil siklus juga (bahkan jika itu tidak benar-benar "dieksekusi" ).

Masalah ini kadang-kadang disebut divergence thread . Jika mesin Anda memiliki sesuatu seperti 32 jalur eksekusi SIMD, ia hanya akan memiliki satu unit pengambilan tunggal. (Di sini istilah "utas" pada dasarnya berarti "jalur eksekusi SIMD".) Jadi secara internal setiap jalur eksekusi SIMD memiliki bit "Saya diaktifkan / dinonaktifkan", dan cabang-cabang sebenarnya hanya memanipulasi bit itu. (Pengecualian adalah pada titik di mana setiap jalur SIMD dinonaktifkan, unit pengambilan umumnya akan langsung melompat ke klausul "lain".)

Jadi dalam kode Anda, setiap jalur eksekusi SIMD melakukan:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

Mungkin pada beberapa GPU konversi persyaratan untuk predikasi ini lebih lambat jika GPU melakukannya sendiri. Seperti yang ditunjukkan oleh @ PaulA.Clayton, jika bahasa pemrograman dan arsitektur Anda memiliki operasi pemindahan bersyarat yang telah ditentukan (terutama salah satu formulir if (c) x = y else x = z), Anda mungkin dapat melakukan yang lebih baik. (Tapi mungkin tidak jauh lebih baik).

Juga, menempatkan c < mindalam bersyarat elsedari c > maxtidak diperlukan. Ini tentu saja tidak menyelamatkan Anda apa pun, dan (mengingat bahwa GPU harus secara otomatis mengubahnya menjadi predikasi) sebenarnya mungkin menyakitkan untuk membuatnya bersarang dalam dua kondisi yang berbeda.