Mengapa rekursi dilarang di OpenCL?

19

Saya ingin menggunakan OpenCL untuk mempercepat rendering gambar raytraced, tapi saya perhatikan bahwa halaman Wikipedia mengklaim bahwa rekursi dilarang di Open CL. Apakah ini benar? Saat saya menggunakan rekursi secara ekstensif saat melakukan raytracing, ini akan membutuhkan sejumlah perancangan ulang yang besar untuk mendapatkan manfaat dari mempercepat. Apa batasan mendasar yang mencegah rekursi? Apakah ada jalan lain?

trichoplax
sumber
2
GPU bekerja dengan cara yang berbeda. (Beberapa arsitektur) tidak memiliki konsep "tumpukan program" global, jadi pemanggilan fungsi rekursif tidak mungkin dilakukan pada mereka. OpenCL mungkin mengadopsi common denominator terendah, sehingga tidak mengizinkannya sepenuhnya portabel di seluruh GPU. Perangkat keras CUDA yang lebih baru tampaknya telah memperkenalkan dukungan untuk rekursi di beberapa titik: stackoverflow.com/q/3644809/1198654
glampert

Jawaban:

27

Ini pada dasarnya karena tidak semua GPU dapat mendukung panggilan fungsi - dan bahkan jika mereka bisa, panggilan fungsi mungkin sangat lambat atau memiliki keterbatasan seperti kedalaman tumpukan yang sangat kecil.

Kode shader dan kode komputasi GPU mungkin tampak memiliki panggilan fungsi di semua tempat, tetapi dalam keadaan normal semuanya 100% digarisbawahi oleh kompiler. Kode mesin yang dijalankan oleh GPU berisi cabang dan loop, tetapi tidak ada panggilan fungsi. Namun, panggilan fungsi rekursif tidak dapat diuraikan karena alasan yang jelas. (Kecuali beberapa argumen adalah konstanta waktu kompilasi, sedemikian rupa sehingga kompiler dapat melipatnya dan menyejajarkan seluruh pohon panggilan.)

Untuk mengimplementasikan panggilan fungsi yang sebenarnya, Anda perlu tumpukan. Sebagian besar waktu, kode shader tidak menggunakan tumpukan sama sekali — GPU memiliki file register besar dan shader dapat menyimpan semua data mereka dalam register sepanjang waktu. Sulit untuk membuat stack bekerja karena (a) Anda akan membutuhkan banyak ruang stack untuk menyediakan semua warps yang dapat terbang dalam satu waktu, dan (b) sistem memori GPU dioptimalkan untuk batching bersama banyak. transaksi memori untuk mencapai throughput yang tinggi, tetapi ini datang dengan biaya latensi, jadi dugaan saya adalah operasi tumpukan seperti menyimpan / mengembalikan variabel lokal akan sangat lambat.

Secara historis, panggilan fungsi tingkat perangkat keras tidak terlalu berguna pada GPU, karena lebih masuk akal untuk memasukkan semua yang ada di kompiler. Jadi arsitek GPU belum fokus untuk membuatnya cepat. Mungkin beberapa tradeoff yang berbeda dapat dibuat, jika ada permintaan untuk panggilan tingkat perangkat keras yang efisien di masa depan, tetapi (seperti halnya semua hal dalam rekayasa) akan dikenakan biaya di tempat lain.

Sejauh menyangkut raytracing, cara orang biasanya menangani hal semacam ini adalah dengan membuat antrian sinar yang sedang dalam proses dilacak. Alih-alih berulang, Anda menambahkan ray ke antrian, dan pada tingkat tinggi di suatu tempat Anda memiliki loop yang terus memproses sampai semua antrian kosong. Itu memang membutuhkan reorganisasi yang signifikan dari kode rendering Anda jika Anda mulai dari raytracer rekursif klasik. Untuk info lebih lanjut, makalah yang bagus untuk dibaca tentang ini adalah Wavefront Path Tracing .

Nathan Reed
sumber
6
Saya enggan membagikan saus rahasia ini, tetapi saya cukup beruntung memiliki jumlah bouncing maksimum yang tetap dan memiliki setumpuk ukuran tetap (dan loop dengan jumlah iterasi yang tetap) untuk menangani hal ini. Juga (dan ini adalah imo saus rahasia yang sebenarnya!) Bahan saya bisa reflektif atau bias tetapi tidak pernah keduanya, yang membuatnya jadi sinar tidak terbelah saat mereka memantul. Hasil akhir dari semua ini adalah rendering raytraced tipe rekursif, tetapi melalui iterasi ukuran tetap, bukan rekursi.
Alan Wolfe
Seperti rekursi ekor?
Tanmay Patil
Anda tidak perlu tumpukan untuk melakukan rekursi ekor, karena fungsi rekursif ekor dapat dikonversi menjadi fungsi berulang. Apakah kompiler OpenCL tidak melakukan ini secara otomatis?
Anderson Green