Fungsi Noise Paralel dan Acak untuk Kernel OpenCL


* Artikel ini adalah hasil kerja sama dengan Intel Developer Zone. Artikel asli bisa dilihat di link ini.

Contoh kode Noise yang terkait dengan tulisan ini mencakup implementasi dari Perlin Noise yang berguna untuk menghasilkan tekstur alami seperti marmer dan awan untuk grafis 3D. Kodingan tersebut adalah sebuah tes yang menggunakan Perlin Noise untuk menghasilkan gambar “awan” (Lihat bagian referensi untuk informasi lebih lanjut mengenai Perlin Noise). Versi 2D dan 3D sudah termasuk di kodenya, yang berarti bahwa fungsi di kodingannya mengambil 2 atau 3 input untuk menghasilkan nilai output satu Perlin Noise.

Contoh Noise ini juga termasuk fungsi psuedo-random number generator (RNG) yang menghasilkan hasil yang cukup baik—cukup bahwa yang gambar visual yang dihasilkan terlihat acak. Versi 1D, 2D, dan 3D sudah termasuk juga, ini mengacu pada jumlah input untuk menghasilkan nilai psuedo-random tunggal.

Pengenalan dan Alasan

Banyak aplikasi yang memerlukan sebuah tingkat “keacakan” — atau sebetulnya disebut “psuedo-randomness”. Artinya, serangkaian nilai yang akan muncul secara acak atau “noisy” untuk manusia. Namun, untuk keterulangan, aplikasi juga mengharuskan RNG-nya dapat diandalkan untuk menghasilkan urutan yang sama dari nilai-nilai jika diberikan nilai input “seed” yang sama.

Kebanyakan algoritma RNG memenuhi persyaratan ini dengan membuat setiap nilai yang dihasilkan tergantung pada nilai yang dihasilkan sebelumnya, dengan nilai pertama dalam urutan yang dihasilkan langsung dari nilai “seed”. Pendekatan ke RNG ini bsia bermasalah untuk bahasa pemrosesan pararel tinggi seperti OpenCL.

Memaksa masing-masing dari setiap thread untuk menunggu satu sumber RNG yang berurutan akan mengurangi paralelisme dari algoritma yang menggunakan itu.

Salah satu pendekatan yang bisa digunakan untuk menangani masalah ini adalah dengan menghasilkan sebuah tabel berisi nilai acak terlebih dahulu, dengan masing-masing thread paralel menghasilkan indek determinis namununik ke dalam tabel tersebut. Sebagai contoh, sebuah kernel OpenCL yang memproses gambar mungkin memilih pintu masuk dari tabel yang sebelumnya dibuat dengan menghitung index berdasarkan koordinat pixel yang sedang diproses atau dihasilkan oleh kernel.

Namun, pendekatan ini membutuhkan proses RNG yang berpotensi memakan waktu sebelum algoritma paralel dimulai—membatasi performa kinerja karena paralelisme. Hal ini juga mengharuskan jumlah nomor acak yang digunakan harus diketahui terlebih dahulu sebelum menjalankan algoritma paralel. Itu bisa menjadi masalah bagi algoritma pararel yang perlu untuk secara dinamis menentukan berapa banyak nilai acak yang akan digunakan oleh setiap thread.

Fungsi level kernel OpenCL dalam contoh kode Noise yang terkait dengan artikel ini mengambil pendekatan yang lebih cocok untuk pendekatan OpenCL dalam membagi pekerjaan ke dalam pengerjaan paralel.

Noise dan Random Number Generation (RNG) untuk OpenCL

OpenCL mendefinisikan ruang kerja global (array dari item kerja) dengan satu, dua, atau tiga dimensi. Setiap item pekerjaan dalam ruang global memiliki nilai integer yang unik yang sesuai dengan koordinat x, y, dan z dalam ruang global.

Perlin Noise dan fungsi RNG dalam contoh Noise menghasilkan nomor acak atau noise berdasarkan hingga tiga nilai input yang dapat menjadi ID global untuk setiap pekerjaan. Alternatifnya, satu atau lebih nilai yang mungkin dihasilkan oleh kombinasi ID global dan beberapa nilai data yang diperoleh atau dihasilkan oleh kernel.

Sebagai contoh, berikut kode OpenCL kernel yang menunjukan generasi nomor acak berdasarkan ID global 2D dari item pekerjaan.

kernel void	genRand()
{
	uint	x = get_global_id(0);
	uint	y = get_global_id(1);

	uint	rand_num = ParallelRNG2( x, y );

	...

Kodingan 1. Contoh penggunaan nomor acak dua dimensi

Pendekatan ini memungkinkan untuk fungsi acak atau noise untuk dijalankan secara paralel antara item pekerjaan namun menghasilkan hasil yang memiliki urutan berulang dari nilai-nilai yang “noisy” baik antara item pekerjaan dan berurutan dalam item pekerjaan.

Jika beberapa set 2D dari nilai-nilai perlu dihasilkan, fungsi generasi 3D dapat digunakan. Dengan dua input pertama dihasilkan berdasarkan ID global item pekerjaan ini dan 3 dimensi yang dihasilkan oleh peningkatan urutan nilai yang dimulai untuk setiap nilai tambahan yang diperlukan.

kernel void multi2dNoise( float fScale, float offset )
{
float	fX = fScale * get_global_id(0);
float	fY = fScale * get_global_id(1);
float	fZ = offset;

float	randResult = Noise_3d(  fX,  fY,  fZ );
...

Kodingan 2. Cotoh penggunaan Perlin Noise tiga dimensi

Keterbatasan

Fungsi Noise_2d dan Noise_3d mengikuti dasar yang sama dengan algoritma Perlin Noise tetapi berbeda dalam implementasi berdasarkan rekomendasi Perlin. (Lihat refrensi 1). Di contoh Noise, hanya Noise_3d yang dilakukan untuk mengimplementasikan contoh noice, tetapi tes kernel untuk Noise_2d termasuk Noise.cl untuk pembaca yang memodifikasi contoh untuk menguji variasi itu.

Fungsi Noise_2d dan Noise_3d harus dipanggil dengan nilai input floating point. Nilainya harus menjangkau rentang (0.0, 128.0) untuk mengatur ukuran “grid” (Lihat Gambar 3) dari nilai acak. Pembaca harus melihat pada contoh clouds untuk memahami bagaimana Perlin Noise dapat mentransformasi ke dalam berbagai gambar yang “terlihat natural” .

Fungsi bawaan ParallelRNG yang digunakan dalam tes acak secara visual memberikan hasil yang acak namun itu bukan algoritma RNG tercepat. Fungsi ini didasarkan pada “Wang hash”, yang tidak dirancang untuk digunakan pada RNG.

Namun, beberapa fungsi RNG umum digunakan (contoh yang dikomentari ada di file Noise.cl) menunjukan keteraturan ketika mengisi gambar 2 dimensi khususnya di bagian bawah bit dari yang dihasilkan. Pembaca mungkin ingin mencoba dengan fungsi lain, fungsi RNG yang lebih epat.

Fungsi bawaan ParallelRNG hanya menghasilkan nilai unsigned 32 bit integer—jika nilai floating point pada kisaran (0.0,1.0) diperlukan, aplikasi harus menerapkan pemetaan untuk kisaran tersebut. Contoh random memetakan hasil unsigned integer untuk rentang (0, 255) supaya menghasilkan nilai-nilai skala pixel abu-abu, hanya menggunakan operasi AND biner untuk memilih 8 bit.

Fungsi standar ParallelRNG tidak akan menghasilkan semua 4294967296 (2 ^ 32) nilai unsigned integer untuk panggilan berurutan menggunakan nilai yang dihasilkan sebelumnya. Untuk setiap nilai awal tunggal urutan pseudo-random / siklus berkisar sekecil-kecilnya dari 7.000 nilai unik ke sekitar 2 miliar.

Ada sekitar 20 siklus yang berbeda yang dihasilkan oleh fungsi bawaan ParallelRNG. Penulis percaya itu akan jarang bahwa setiap item pekerjaan dari sebuah kernel OpenCL akan memerlukan lebih banyak urutan angka acak yang dihasilkan dari siklus terkecil yang dapat menyediakan.

Fungsi versi 2D dan 3D-ParallelRNG2 dan ParallelRNG3- menggunakan “mixing” (campuran) siklus dengan menerapkan operasi biner XOR antara hasil dari panggilan sebelumnya untuk ParallelRNG dan nilai input berikutnya, yang akan mengubah panjang siklus. Namun, perilaku karakter belum ditandai secara detail, sehingga dianjurkan pembaca hati-hati dalam memvalidasi fungsi ParallelRNG untuk memenuhi kebutuhan aplikasi.

Stuktur Proyek

Bagian ini hanya berisi daftar element kunci dari contoh kode sumber aplikasi.

NoiseMain.cpp:

Main()
Fungsi poin masuk utama. Setelah pilihan parsing command-line, fungsi tersebut menginisialisasi OpenCL, membangun program kernel OpenCL dari file Noise.cl, mempersiapkan satu kernel untuk dijalankan, dan memanggil ExecuteNoiseKernel(), kemudian ExecuteNoiseReference().

Setelah memvalidasi dua prosedur implementasi dengan hasil yang sama, main() menampilkan informasi waktu masing-masing yang dihasilkan dan menyimpan gambar yang dihasilkan dari masing-masing.

ExecuteNoiseKernel()
Mengeset dan menjalankan kernel Noise yang dipilih dengan OpenCL

ExecuteNoiseReference()
Setup dan menjalankan kode C referensi Noise yang dipilih.

Noise.cl:

Default_perm[256]
Tabel nilai acak 0-255 untuk 3D kernel Perlin Noise. Catat bahwa ini bisa dihasilkan dan diteruskan ke kernel Perlin Noise untuk menambahkan keacakan.

grads2d[16]
16 unit vektor, gradien untuk 2D kernel Perlin Noise

grads3d[16]
16 gradien vektor untuk 3D kernel Perlin Noise

ParallelRNG()
Pseudo-Random Number Generator, satu pas di atas 1 input. Sebuah fungsi RNG alternatif dikomentari kodingannya, dalam kasus pembaca ingin menguji fungsi lebih cepat yang menghasilkan hasil yang lebih jelek.

ParallelRNG2()
RNG melakukan 2 pas untuk 2 input

ParallelRNG3()
RNG melewatkan 3 pas untuk 3 input

weight_poly3() dan weight_poly5() dan WEIGHT()
Ini adalah fungsi alternatif weight yang digunakan oleh Perlin Noise, untuk memastikan gradien terus menerus di manapun. Fungsi kedua (yang lebih disukai) memungkinkan turunan kedua terus menerus di manapun juga. Makro WEIGHT menyeleksi mana yang akan digunakan.

NORM256()
Konversi makro kisaran (0, 255) sampai (-1.0, 1.0)

interp ()
Interpolasi biliner menggunakan yang dibangun OpenCL

hash_grad_dot2 ()
Memilih gradien dan melakukan dot produk dengan input xy, bagian dari fungsi Perlin Noise_2d.

Noise_2d ()
Perlin Noise Generator dengan 2 input.

hash_grad_dot3 ()
Memilih gradien dan melakukan dot produk dengan input xyz, bagian dari fungsi Perlin Noise_3d.

Noise_3d ()
Perlin Noise Generator dengan 3 input.

cloud()
Menghasilkan satu piksel output gambar dari “cloud” untuk CloudTest menggunakan Noise_3d.

map256()
Mengkonversi dari Perlin Noise kisaran output (-1.0, 1.0) untuk rentang (0, 255) yang diperlukan untuk piksel skala abu-abu.

CloudTest()
Tes generasi gambar cloud. Parameter slice diteruskan ke cloud, untuk memungkinkan kode host untuk menghasilkan alternatif gambar cloud.

Noise2dTest()
Uji Noise_2d – tidak digunakan secara bawaan.

Noise3dTest()
Uji Noise_3d – fungsi bawaan Perlin Noise. Menggunakan map256 untuk menghasilkan nilai-nilai piksel untuk gambar grayscale.

RandomTest()
Uji ParallelRNG3, saat ini menggunakan urutan byte rendah dari hasil unsigned integer untuk output gambar grayscale.

Dua solusi Microsoft Visual Studio sudah disediakan, untuk Visual Studio versi 2012 dan 2013, yaitu adalah “Noise_2012.sln” dan “Noise_2013.sln”. Jika pembaca memiliki versi yang lebih baru dari Visual Studio, seharusnya memungkinkan untuk menggunakan Visual Studio terbaru untuk membuat solusi baru yang berasal dari ini.

Perhatikan bahwa di kedua solusi tersebut diasumsikan bahwa Intel OpenCL Code Builder sudah diinstall.

Mengontrol Contoh

Contoh ini dapat dijalankan dari konsol command-line Windows, dari folder yang berisi file EXE:

Noise.exe < Options >

Pilihan:

-h atau -help
Menampilkan bantuan pada command-line. Tidak menjalakan salah satu demo.

-t or –type [ all | cpu | gpu | acc | default | <OpenCL constant for device type>
Pilih perangkat untuk menjalankan kernel OpenCL berdasarkan jenis perangkat. Nilai bawaan : all

<OpenCL constant for device type>

CL_DEVICE_TYPE_ALL | CL_DEVICE_TYPE_CPU | CL_DEVICE_TYPE_GPU |

CL_DEVICE_TYPE_ACCELERATOR | CL_DEVICE_TYPE_DEFAULT

-p or –platform < number-or-string >
Memilih platform yang digunakan. Semua daftar nama dan nomor platform ditampilkan ketika demo dijalankan. Platform yang digunakan akan berciri “Selected” yang ditampilkan di sebelah kanan. Jika menggunakan string, tersedia huruf dari nama platform untuk mengidentifikasi secara unik. Nilai bawaanya: Intel

-d atau –device <number-atau-string>

Pilih perangkat untuk menjalankan pada kernel OpenCL oleh nama atau nomor perangkat. Nomor perangkat dan nama pada platform yang digunakan untuk ditampilkan saat demo dijalankan. Perangkat saat ini akan memiliki ciri “[selected]” yang ditampilkan di sebelah kanan. Nilai bawaan: 0

r atau –run [random | Perlin | clouds]

Pilih fungsi demonstrasi untuk dijalankan. Nomor acak, Perlin Noise, atau generator gambar cloud masing-masing memiliki kernel demo. Nilai default: random

-s atau –seed <bilangan bulat>

Memberikan nilai integer untuk variasi output algoritma. Nilai default: 1

Noise.exe mencetak atau menampilkan waktu kernel OpenCL dan referensi C-coded setara masing-masing untuk dijalankan, serta untuk setiap nama-nama file output. Ketika program telah selesai mencetak/menampilkan informasi, pengguna menunggu untuk tekan ENTER sebelum keluar.

Harap dicatat bahwa tidak ada upaya yang dilakukan untuk mengoptimalkan kinerja dari fungsi kode referensi C-coded; mereka hanya ditujukan untuk memvalidasi kebenaran kode pada kernel OpenCL

Memeriksa Hasil

Setelah selesai menjalankan Noise.exe, periksa file gambar format BMP yang dihasilkan yaitu OutputOpenCL.bmp dan OutputRefrence.bmp di folder proyek. Untuk membandingkan hasil masing-masing dari OpenCL dan kode C++, dua gambar harus identik, meskipun ada kemungkinan ada perbedaan yang sangat kecil antara dua Perlin Noise dan gambar cloud.

(Perlin) output noise akan muncul seperti pada Gambar 1:

Fungsi Noise Paralel dan Acak untuk Kernel OpenCL

Gambar 1. Output Perlin Noise

Output random akan terlihat seperti Gambar 2:

Fungsi Noise Paralel dan Acak untuk Kernel OpenCL

Gambar 2. Output Random Noise

Output fungsi clouds akan terlihat seperti Gambar 3:

Fungsi Noise Paralel dan Acak untuk Kernel OpenCL

Gambar 3. Menghasilkan output cloud

Referensi

  1. Perlin, K., “Improving Noise,” http://mrl.nyu.edu/~perlin/paper445.pdf
  2. “4-byte Integer Hashing,” http://burtleburtle.net/bob/hash/integer.html
  3. Overton, M. A., “Fast, High-Quality, Parallel Random Number Generators,” Dr. Dobb’s website (2011). http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477
  4. Intel Digital Random Number Generator (DRNG) Library Implementation and Uses, https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-library-implementation-and-uses
  5. Intel Sample Source Code License Agreement, https://software.intel.com/en-us/articles/intel-sample-source-code-license-agreement/
  6. Intel OpenCL Code Builder, https://software.intel.com/en-us/opencl-code-builder

* Artikel ini adalah hasil kerja sama dengan Intel Developer Zone. Artikel asli bisa dilihat di link ini.