Algoritma Pelacakan GPU Baru: Wavefront Path Tracing

Dalam artikel ini, kami mengeksplorasi konsep penting yang digunakan dalam platform Mercusuar yang baru dirilis 2. Jalur lintasan gelombang , seperti yang disebut Lane, Karras dan Aila dari NVIDIA, atau streaming jalur lacak, seperti yang awalnya disebut dalam tesis master Van Antwerp, memainkan peran penting dalam pengembangan pelacak jalur efisien pada GPU, dan berpotensi pelacak jalur pada CPU. Namun, itu sangat berlawanan dengan intuisi, oleh karena itu, untuk memahaminya, perlu untuk memikirkan kembali algoritma penelusuran sinar.

Hunian

Algoritma path tracing sangat sederhana dan dapat dijelaskan hanya dalam beberapa baris pseudocode:

vec3 Trace( vec3 O, vec3 D ) IntersectionData i = Scene::Intersect( O, D ) if (i == NoHit) return vec3( 0 ) // ray left the scene if (i == Light) return i.material.color // lights do not reflect vec3 R, pdf = RandomDirectionOnHemisphere( i.normal ), 1 / 2PI return Trace( i.position, R ) * i.BRDF * dot( i.normal, R ) / pdf 

Input adalah sinar primer yang lewat dari kamera melalui piksel layar. Untuk balok ini, kami menentukan persimpangan terdekat dengan adegan primitif. Jika tidak ada persimpangan, maka balok menghilang ke dalam kekosongan. Jika tidak, jika sinar mencapai sumber cahaya, maka kami telah menemukan jalur cahaya antara sumber dan kamera. Jika kita menemukan sesuatu yang lain, maka kita melakukan refleksi dan rekursi, berharap sinar yang dipantulkan masih akan menemukan sumber penerangan. Perhatikan bahwa proses ini menyerupai jalur (kembali) dari foton yang memantulkan permukaan pemandangan.

GPU dirancang untuk melakukan tugas ini dalam mode multi-threaded. Pada awalnya mungkin tampak bahwa penelusuran sinar sangat ideal untuk ini. Jadi, kami menggunakan OpenCL atau CUDA untuk membuat aliran untuk piksel, setiap aliran melakukan algoritme yang benar-benar berfungsi sebagaimana mestinya, dan cukup cepat: lihat saja beberapa contoh dengan ShaderToy untuk memahami seberapa cepat penelusuran sinar dapat dilakukan. pada GPU. Tapi betapapun mungkin, pertanyaannya berbeda: apakah pelacak sinar ini benar - benar secepat mungkin ?


Algoritma ini memiliki masalah. Sinar primer dapat menemukan sumber cahaya segera, atau setelah satu refleksi acak, atau setelah lima puluh refleksi. Programer untuk CPU akan melihat stack overflow potensial di sini; programmer GPU harus melihat masalah hunian . Masalahnya disebabkan oleh rekursi ekor bersyarat: jalur mungkin berakhir di sumber cahaya atau berlanjut. Mari kita transfer ini ke banyak utas: sebagian utas akan berhenti, dan bagian lainnya akan terus bekerja. Setelah beberapa refleksi, kami akan memiliki beberapa utas yang perlu melanjutkan komputasi, dan sebagian utas akan menunggu utas terakhir selesai bekerja. Pekerjaan adalah ukuran porsi utas GPU yang melakukan pekerjaan yang bermanfaat.

Masalah ketenagakerjaan berlaku untuk model eksekusi perangkat SIMT GPU. Streaming diatur ke dalam grup, misalnya, dalam GPU Pascal (NVidia equipment class 10xx) 32 utas digabungkan menjadi warp . Utas dalam warp memiliki penghitung program umum: mereka dieksekusi dengan langkah tetap, sehingga setiap instruksi program dijalankan oleh 32 utas secara bersamaan. SIMT adalah kependekan dari instruksi tunggal , yang menjelaskan konsep dengan baik. Untuk prosesor SIMT, kode dengan kondisi rumit. Ini jelas ditunjukkan dalam dokumentasi resmi Volta:


Eksekusi kode dengan ketentuan dalam SIMT.

Ketika kondisi tertentu berlaku untuk beberapa utas di warp, cabang-cabang pernyataan if adalah serial. Alternatif untuk pendekatan "semua utas melakukan hal yang sama" adalah "beberapa utas dinonaktifkan." Dalam blok if-then-else, rata-rata pekerjaan warp adalah 50%, kecuali semua thread memiliki konsistensi mengenai kondisi tersebut.

Sayangnya, kode dengan kondisi dalam pelacak ray tidak begitu langka. Sinar bayangan dipancarkan hanya jika sumber cahaya tidak berada di belakang titik naungan, jalur yang berbeda dapat bertabrakan dengan bahan yang berbeda, integrasi dengan metode roulette Rusia dapat menghancurkan atau membiarkan jalan hidup, dan seterusnya. Ternyata hunian menjadi sumber utama ketidakefisienan, dan tidak mudah untuk mencegahnya tanpa tindakan darurat.

Streaming Jalur Menelusuri

Algoritma penelusuran jalur streaming dirancang untuk mengatasi akar penyebab masalah yang sibuk. Streaming path tracing membagi algoritma path tracing menjadi empat langkah:

1. Hasilkan
2. Perpanjang
3. Naungan
4. Terhubung

Setiap tahap diimplementasikan sebagai program terpisah. Karena itu, alih-alih mengeksekusi pelacak jalur penuh sebagai program GPU tunggal ("kernel", kernel), kita harus bekerja dengan empat core. Selain itu, seperti yang akan segera kita lihat, mereka dieksekusi dalam satu lingkaran.

Tahap 1 ("Hasilkan") bertanggung jawab untuk menghasilkan sinar primer. Ini adalah inti sederhana yang menciptakan titik awal dan arah sinar dalam jumlah yang sama dengan jumlah piksel. Output dari tahap ini adalah buffer sinar besar dan penghitung menginformasikan tahap selanjutnya dari jumlah sinar yang perlu diproses. Untuk sinar primer, nilai ini sama dengan lebar layar dikalikan ketinggian layar .

Tahap 2 ("Pembaruan") adalah inti kedua. Ini dijalankan hanya setelah tahap 1 selesai untuk semua piksel. Kernel membaca buffer yang dihasilkan pada langkah 1 dan memotong setiap sinar dengan adegan. Output dari tahap ini adalah hasil persimpangan untuk setiap sinar yang disimpan dalam buffer.

Tahap 3 ("Bayangan") dilakukan setelah penyelesaian tahap 2. Ini menerima hasil persimpangan dari tahap 2 dan menghitung model bayangan untuk setiap jalur. Operasi ini mungkin atau mungkin tidak menghasilkan sinar baru, tergantung pada apakah jalur telah selesai. Jalur yang menghasilkan sinar baru (jalur "memanjang") menulis sinar baru ("segmen jalan") ke buffer. Jalur yang secara langsung mengambil sampel sumber cahaya ("pencahayaan sampel secara eksplisit" atau "menghitung kejadian berikutnya") menulis berkas bayangan ke buffer kedua.

Tahap 4 ("Sambungkan") melacak sinar bayangan yang dihasilkan pada tahap 3. Ini mirip dengan tahap 2, tetapi dengan perbedaan penting: sinar bayangan perlu menemukan persimpangan, sedangkan sinar yang diperluas perlu menemukan persimpangan terdekat. Oleh karena itu, inti yang terpisah telah dibuat untuk ini.

Setelah menyelesaikan langkah 4, kami mendapatkan buffer yang berisi sinar yang memperpanjang jalur. Setelah mengambil sinar ini, kami melanjutkan ke tahap 2. Kami terus melakukan ini sampai tidak ada sinar ekstensi atau sampai kami mencapai jumlah iterasi maksimum.

Sumber Ketidakefisienan

Seorang programmer yang peduli dengan kinerja akan melihat banyak momen berbahaya dalam skema algoritma penelusuran jalur streaming:

• Alih-alih satu panggilan kernel, kami sekarang memiliki tiga panggilan per iterasi , ditambah satu generasi kernel. Core yang menantang berarti peningkatan beban tertentu, jadi ini buruk.
• Setiap inti membaca buffer besar dan menulis buffer besar.
• CPU perlu tahu berapa banyak utas yang dihasilkan untuk setiap inti, sehingga GPU harus memberi tahu CPU berapa banyak sinar yang dihasilkan pada langkah 3. Memindahkan informasi dari GPU ke CPU adalah ide yang buruk, dan perlu dilakukan setidaknya sekali per iterasi.
• Bagaimana tahap 3 menulis sinar ke buffer tanpa membuat spasi di mana-mana? Dia tidak menggunakan penghitung atom untuk ini?
• Jumlah jalur aktif masih berkurang, jadi bagaimana skema ini bisa membantu sama sekali?

Mari kita mulai dengan pertanyaan terakhir: jika kita mentransfer sejuta tugas ke GPU, itu tidak akan menghasilkan sejuta utas. Jumlah sebenarnya dari thread yang dijalankan secara bersamaan tergantung pada peralatan, tetapi dalam kasus umum, puluhan ribu thread dieksekusi. Hanya ketika bebannya turun di bawah angka ini kita akan melihat masalah ketenagakerjaan yang disebabkan oleh sejumlah kecil tugas.

Kekhawatiran lain adalah I / O buffer dalam skala besar. Ini memang kesulitan, tetapi tidak seserius yang Anda duga: akses ke data sangat mudah diprediksi, terutama saat menulis ke buffer, sehingga penundaan tidak menyebabkan masalah. Faktanya, GPU terutama dikembangkan untuk jenis pemrosesan data ini.

Aspek lain yang ditangani GPU dengan sangat baik adalah penghitung atom, yang sangat tidak terduga bagi programmer yang bekerja di dunia CPU. Z-buffer memerlukan akses cepat, dan karenanya penerapan penghitung atom dalam GPU modern sangat efektif. Dalam praktiknya, operasi penulisan atom sama mahalnya dengan menulis yang tidak di-cache ke memori global. Dalam banyak kasus, penundaan akan tertutupi oleh eksekusi paralel skala besar di GPU.

Masih ada dua pertanyaan: panggilan kernel dan transfer data dua arah untuk penghitung. Yang terakhir ini sebenarnya masalah, jadi kita perlu perubahan arsitektur lain: utas yang persisten .

Konsekuensinya

Sebelum mempelajari detailnya, kita akan melihat implikasi dari penggunaan algoritma penelusuran jalur gelombang. Pertama, katakanlah tentang buffer. Kami membutuhkan buffer untuk menampilkan data tahap 1, yaitu sinar primer. Untuk setiap balok kita membutuhkan:

• Asal berkas: tiga nilai float, mis. 12 byte
• Arah ray: tiga nilai float, mis. 12 byte

Dalam praktiknya, lebih baik menambah ukuran buffer. Jika Anda menyimpan 16 byte untuk awal dan arah berkas, GPU akan dapat membacanya dalam satu operasi baca 128-bit. Alternatifnya adalah operasi membaca 64-bit diikuti oleh operasi 32-bit untuk mendapatkan float3, yang hampir dua kali lebih lambat. Yaitu, untuk layar 1920 × 1080 kita mendapatkan: 1920x1080x32 = ~ 64 MB. Kami juga membutuhkan buffer untuk hasil persimpangan yang dibuat oleh Extend kernel. Ini adalah 128 bit per elemen, yaitu 32 MB. Lebih lanjut, kernel "Shadow" dapat membuat ekstensi path 1920x1080 (batas atas), dan kami tidak dapat menulisnya ke buffer dari mana kita membaca. Itu adalah 64 MB. Dan akhirnya, jika pelacak jalur kami memancarkan sinar bayangan, maka ini adalah buffer 64 MB lainnya. Setelah merangkum semuanya, kami mendapatkan 224 MB data, dan ini hanya untuk algoritme wavefront. Atau sekitar 1 GB dalam resolusi 4K.

Di sini kita perlu terbiasa dengan fitur lain: kita memiliki banyak memori. Tampaknya. 1 GB itu banyak, dan ada cara untuk mengurangi angka ini, tetapi jika Anda mendekati ini secara realistis, maka pada saat kita benar-benar perlu melacak jalur di 4K, menggunakan 1 GB pada GPU dengan 8 GB akan lebih sedikit dari masalah kita.

Lebih serius daripada persyaratan memori, konsekuensinya adalah algoritma rendering. Sejauh ini saya telah menyarankan bahwa kita perlu menghasilkan satu sinar ekstensi dan, mungkin, satu bayangan bayangan untuk setiap thread di inti Shadow. Tetapi bagaimana jika kita ingin melakukan Ambient Occlusion menggunakan 16 sinar per pixel? 16 sinar AO perlu disimpan dalam buffer, tetapi, lebih buruk lagi, mereka hanya akan muncul di iterasi berikutnya. Masalah serupa muncul ketika menelusuri sinar dalam gaya Witted: memancarkan sinar bayangan untuk beberapa sumber cahaya atau membelah balok dalam tabrakan dengan kaca hampir mustahil untuk diwujudkan.

Di sisi lain, penelusuran jalur gelombang menyelesaikan masalah yang telah kami daftarkan di bagian Hunian:

• Pada tahap 1, semua aliran tanpa kondisi membuat sinar primer dan menuliskannya ke buffer.
• Pada tahap 2, semua aliran tanpa kondisi memotong sinar dengan adegan dan menulis hasil persimpangan ke buffer.
• Pada langkah 3, kami mulai menghitung hasil persimpangan dengan hunian 100%.
• Pada langkah 4, kami memproses daftar sinar bayangan terus menerus tanpa spasi.

Pada saat kita kembali ke tahap 2 dengan sinar yang masih hidup dengan panjang 2 segmen, kita kembali mendapatkan buffer ray kompak, yang menjamin pekerjaan penuh ketika kernel dimulai.

Selain itu, ada keuntungan tambahan yang tidak boleh diremehkan. Kode ini diisolasi dalam empat langkah terpisah. Setiap inti dapat menggunakan semua sumber daya GPU yang tersedia (cache, memori bersama, register) tanpa memperhitungkan inti lainnya. Ini memungkinkan GPU untuk mengeksekusi kode persimpangan dengan adegan di lebih banyak utas, karena kode ini tidak memerlukan register sebanyak kode shader. Semakin banyak utas, semakin baik Anda bisa menyembunyikan penundaan.

Full-time, penyempurnaan penundaan tunda, rekaman streaming: semua manfaat ini terkait langsung dengan kemunculan dan sifat platform GPU. Untuk GPU, algoritma penelusuran jalur gelombang sangat alami.

Apakah itu sepadan?

Tentu saja, kami memiliki pertanyaan: apakah pekerjaan yang dioptimalkan membenarkan I / O dari buffer dan biaya untuk meminta core tambahan?

Jawabannya adalah ya, tetapi membuktikan ini tidak mudah.

Jika kita kembali ke pelacak trek dengan ShaderToy sebentar, kita akan melihat bahwa sebagian besar dari mereka menggunakan adegan sederhana dan kode keras. Menggantinya dengan adegan full-blown bukanlah tugas yang sepele: bagi jutaan primitif, memotong balok dan adegan menjadi masalah yang kompleks, solusinya sering diserahkan kepada NVidia ( Optix ), AMD ( Radeon-Rays ) atau Intel ( Embree ). Tak satu pun dari opsi ini dapat dengan mudah menggantikan adegan hard-coded dalam pelacak ray buatan CUDA. Dalam CUDA, analog terdekat (Optix) membutuhkan kontrol atas eksekusi program. Embree dalam CPU memungkinkan Anda untuk melacak balok individu dari kode Anda sendiri, tetapi biaya ini adalah overhead kinerja yang signifikan: ia lebih suka melacak kelompok balok besar daripada balok individu.


Layar dari It's About Time diberikan bersama Brigade 1.

Akankah pelacakan jalur gelombang lebih cepat daripada alternatifnya (megakernel, seperti yang Lane dan rekannya sebutkan) tergantung pada waktu yang dihabiskan di inti (adegan besar dan shaders yang mahal mengurangi biaya relatif yang dibanjiri oleh algoritma muka gelombang), pada panjang jalur maksimum , pekerjaan mega-core dan perbedaan beban pada register dalam empat tahap. Dalam versi awal Brigade Path Tracer asli, kami menemukan bahwa bahkan adegan sederhana dengan campuran permukaan reflektif dan Lambert yang berjalan pada GTX480 diuntungkan dengan menggunakan muka gelombang.

Streaming Path Tracing di Mercusuar 2

Platform Lighthouse 2 memiliki dua jalur pelacak jejak gelombang. Yang pertama menggunakan Optix Prime untuk implementasi tahap 2 dan 4 (tahap persimpangan sinar dan adegan); yang kedua, Optix digunakan langsung untuk mengimplementasikan fungsi itu.

Optix Prime adalah versi sederhana dari Optix yang hanya berurusan dengan persimpangan satu set balok dengan adegan yang terdiri dari segitiga. Tidak seperti perpustakaan Optix lengkap, itu tidak mendukung kode persimpangan khusus, dan hanya memotong segitiga. Namun, ini adalah persis apa yang diperlukan untuk pelacak jalur gelombang.

Optix Prime berbasis pelacak jalur gelombang diimplementasikan dalam rendercore.cpp proyek rendercore.cpp . Inisialisasi Optix Prime dimulai pada fungsi Init dan menggunakan rtpContextCreate . Adegan dibuat menggunakan rtpModelCreate . Berbagai buffer ray dibuat dalam fungsi rtpBufferDescCreate menggunakan rtpBufferDescCreate . Perhatikan bahwa untuk buffer ini kami menyediakan pointer perangkat yang biasa: ini berarti bahwa mereka dapat digunakan baik di Optix dan di core CUDA biasa.

Render dimulai dalam metode Render . Untuk mengisi buffer ray primer, sebuah inti CUDA yang disebut generateEyeRays . Setelah mengisi buffer, Optix Prime disebut menggunakan rtpQueryExecute . Dengan itu, hasil persimpangan ditulis ke extensionHitBuffer . Perhatikan bahwa semua buffer tetap berada dalam GPU: dengan pengecualian panggilan kernel, tidak ada lalu lintas antara CPU dan GPU. Tahap "Bayangan" diimplementasikan dalam inti shade CUDA biasa. Implementasinya ada di pathtracer.cu .

Beberapa detail implementasi untuk optixprime_b layak disebutkan. Pertama, bayangan bayangan dilacak di luar siklus muka gelombang. Ini benar: sinar bayangan memengaruhi piksel hanya jika tidak diblokir, tetapi dalam semua kasus hasilnya tidak diperlukan di tempat lain. Artinya, bayangan balok sekali pakai , dapat ditelusuri kapan saja dan dalam urutan apa pun. Dalam kasus kami, kami menggunakan ini dengan mengelompokkan sinar bayangan sehingga bets akhirnya ditelusuri sebesar mungkin. Ini memiliki satu konsekuensi yang tidak menyenangkan: dengan iterasi N dari algoritma muka gelombang dan sinar primer X, batas atas jumlah sinar bayangan sama dengan XN .

Detail lainnya adalah pemrosesan berbagai counter. Tahap "Memperbarui" dan "Bayangan" harus tahu berapa banyak jalur yang aktif. Penghitung untuk ini diperbarui dalam GPU (secara atomis), yang berarti mereka digunakan dalam GPU, bahkan tanpa kembali ke CPU. Sayangnya, dalam salah satu kasus ini tidak mungkin: perpustakaan Optix Prime perlu mengetahui jumlah sinar yang dilacak. Untuk melakukan ini, kita perlu mengembalikan informasi dari penghitung sekali iterasi.

Kesimpulan

Artikel ini menjelaskan apa yang dimaksud dengan penelusuran jalur gelombang dan mengapa perlu untuk melakukan pelacakan jalur secara efektif pada GPU. Implementasi praktisnya disajikan dalam platform Lighthouse 2, yang bersifat open source dan tersedia di Github .