Contoh algoritma tujuan umum yang mendapat manfaat dari menjalankan GPU? [Tutup]

Saya mencari contoh-contoh algoritma tujuan umum (yang artinya tidak terkait grafis) yang telah terbukti menjalankan urutan besarnya lebih cepat pada GPU daripada pada CPU. Saya akan menggunakan contoh-contoh ini untuk berpikir kreatif tentang algoritma lain yang dapat saya terapkan pada GPU.

Beberapa hal segera terlintas dalam pikiran:

Klien Bitcoin khusus ditulis untuk menggunakan GPU untuk melakukan hash kriptografi. Klien GPU umumnya melakukan lebih dari 10x lebih baik daripada klien CPU SMP pada sistem 4-core yang khas. Bitcoin tergantung pada perhitungan sejumlah besar hash kriptografi yang tidak terkait, yang dapat dihitung secara paralel.

Proyek Folding @ Home menawarkan klien GPU untuk simulasi dinamika molekul mereka. Komputasi ini dilakukan pada ikatan individu antara atom dalam berbagai lingkungan dan kondisi. Matematika relatif sederhana, tetapi harus dihitung milyaran kali untuk setiap ikatan untuk mensimulasikan aktivitas nanodetik belaka.

Contoh "mainan" populer yang digunakan oleh pendukung komputasi GPU adalah masalah n-body .

Yang sama-sama memiliki kesamaan adalah bahwa semuanya memalukan . Artinya, masalahnya dapat didekomposisi menjadi sejumlah kecil perhitungan terpisah yang dilakukan berkali-kali selama satu set data besar. Itu adalah jenis perhitungan yang bagus untuk GPU.

Komputasi kompleks yang bergantung pada hasil perhitungan sebelumnya tidak cocok untuk GPU.

Transcoding video dan audio adalah contoh yang bagus. Ini konversi dari satu format file ke yang lain. Contohnya adalah MPEG-2 hingga H.264.

_{Catatan transcoding video tidak terkait dengan grafik 3D. Anda tidak dapat menyandikan video menggunakan vertex dan pixel shader.}

Pertambangan Bitcoins menggunakan GPU telah menjadi sangat populer.

... sistem uang tunai elektronik peer-to-peer. Pembuatan dan transfer Bitcoin didasarkan pada protokol kriptografi open source dan tidak dikelola oleh otoritas pusat. Setiap bitcoin dibagi menjadi delapan tempat desimal, membentuk 100 juta unit lebih kecil yang disebut satoshi. Bitcoin dapat ditransfer melalui komputer atau smartphone tanpa lembaga keuangan perantara.

Pemrosesan transaksi bitcoin dijamin oleh server yang disebut penambang Bitcoin. Server-server ini berkomunikasi melalui jaringan berbasis internet dan mengkonfirmasi transaksi dengan menambahkannya ke buku besar yang diperbarui dan diarsipkan secara berkala. Selain pengarsipan transaksi, setiap pembaruan buku besar baru membuat beberapa bitcoin yang baru dicetak ...

Aplikasi lain adalah di pasar keuangan untuk perdagangan waktu nyata menggunakan model seperti Black-Scholes .

... Persyaratan utama untuk menggunakan opsi adalah menghitung nilai wajarnya. Menemukan cara memecahkan masalah penetapan harga ini secara efisien telah menjadi bidang penelitian aktif selama lebih dari tiga puluh tahun, dan terus menjadi fokus rekayasa keuangan modern. Karena lebih banyak komputasi telah diterapkan pada masalah terkait keuangan, menemukan cara yang efisien untuk mengimplementasikan algoritma ini pada arsitektur modern menjadi lebih penting.

Bab ini menjelaskan bagaimana opsi dapat dihargai secara efisien menggunakan GPU. Kami melakukan evaluasi kami menggunakan dua model penetapan harga yang berbeda: model Black-Scholes dan model kisi. Kedua pendekatan ini memetakan dengan baik ke GPU, dan keduanya secara substansial lebih cepat pada GPU daripada pada CPU modern. Meskipun keduanya juga memiliki pemetaan langsung ke GPU, menerapkan model kisi membutuhkan kerja tambahan karena saling ketergantungan dalam perhitungan ...

Permainan Kehidupan Conway adalah contoh akademis yang bagus.

... Alam semesta dari Game of Life adalah grid ortogonal dua dimensi yang tak terbatas dari sel-sel kuadrat, masing-masingnya ada di salah satu dari dua kemungkinan keadaan, hidup atau mati. Setiap sel berinteraksi dengan delapan tetangganya, yaitu sel-sel yang berdekatan secara horizontal, vertikal, atau diagonal. Pada setiap langkah waktu, transisi berikut terjadi:

1. Setiap sel hidup dengan kurang dari dua tetangga hidup mati, seolah-olah disebabkan oleh populasi yang kurang.
2. Setiap sel hidup dengan dua atau tiga tetangga yang hidup hidup sampai generasi berikutnya.
3. Setiap sel hidup dengan lebih dari tiga tetangga hidup mati, seolah-olah oleh kepadatan.
4. Setiap sel mati dengan tepat tiga tetangga hidup menjadi sel hidup, seolah-olah dengan reproduksi.

Pola awal merupakan benih dari sistem. Generasi pertama diciptakan dengan menerapkan aturan-aturan di atas secara bersamaan ke setiap sel dalam benih — kelahiran dan kematian terjadi secara bersamaan, dan momen diskrit di mana hal ini terjadi kadang-kadang disebut kutu (dengan kata lain, setiap generasi adalah fungsi murni dari sebelumnya). Aturan terus diterapkan berulang kali untuk menciptakan generasi selanjutnya ...

Masalah yang membutuhkan banyak matematika itu bisa dilakukan secara bersamaan. Di tempat saya dulu bekerja, kami ingin bermain dengan GPU untuk menambah / mengurangi / mengalikan 2 matriks untuk mencari koreksi genetik. Pertama kali saya mendengar tentang GPU adalah bahwa mereka sedang digunakan oleh rumah perangkat lunak keuangan untuk melakukan beberapa pemodelan mereka (monte carlo dan sebagainya). Ini akan berguna dalam pemecahan kode.

GPU mungkin tidak akan banyak membantu dengan masalah pemrograman Anda yang lebih teratur di mana beberapa core CPU sudah cukup karena sebagian besar program reguler hanya perlu menjalankan beberapa proses bersamaan. (mungkin berbeda dengan memori / disk yang jauh lebih cepat daripada yang kita miliki saat ini)

Mungkin saya menjadi sangat matematika / sains / teknik komputasi spesifik tetapi satu yang terlintas dalam pikiran adalah algoritma FFT.

Saya telah melihat patokan FFT ini dilemparkan sebelumnya, dan meskipun beberapa tahun saya pikir itu dilakukan dengan baik seperti apa adanya: http://www.sharcnet.ca/~merz/CUDA_benchFFT