Apakah unit pemrosesan paralel masif saat ini mampu menjalankan automata seluler secara efisien?

Saya bertanya-tanya apakah unit komputasi paralel masif yang disediakan dalam kartu grafis saat ini (yang diprogram dalam OpenCL , misalnya) cukup baik untuk mensimulasikan 1D seluler automata (atau mungkin 2D seluler automata?) Secara efisien.

Jika kita memilih kisi hingga apa pun yang cocok dengan memori chip, dapatkah kita mengharapkan satu transisi dari otomat seluler yang ditentukan pada kisi ini untuk dihitung dalam waktu kuasi?

Saya menganggap automata seluler 2D akan membutuhkan lebih banyak bandwidth untuk komunikasi antara berbagai bagian chip daripada 1D automata.

Saya juga tertarik dengan pertanyaan yang sama dalam hal pemrograman FPGA atau chip khusus.

Pertanyaan yang sangat bagus Saya yakin jawabannya adalah ya.

Mengembangkan otomat seluler pada dasarnya setara dengan melakukan perhitungan stensil. Pada beberapa grid 1D, 2D, atau 3D, nilai berturut-turut poin (atau sel) dihitung berdasarkan nilai terakhir dari lingkungan titik. Dalam CA 1D sederhana, lingkungan ini mungkin sel dan dua sel ke kiri dan kanan. Ada banyak contoh perhitungan stensil yang dilakukan pada GPU; Suite benchmark SHOC ORNL untuk OpenCL / CUDA berisi contoh stensil 2D, misalnya.

Ide dasarnya adalah meminta setiap utas mendapatkan salinan lokal dari lingkungan tersebut untuk beberapa poin, lalu menghitung nilai berikutnya untuk poin yang ditentukan oleh lingkungan tersebut. Dengan menggunakan hierarki memori secara tepat dalam mis. CUDA (register, shared, constant, tekstur, dan memori global) dan model pemrosesan SIMT (mis., Dengan secara tepat menghitung fungsi transisi tanpa memperkenalkan perbedaan warp yang berlebihan), kinerja yang baik dapat dicapai.

Jawaban ini akan jauh lebih baik jika saya memberi contoh, tetapi saya terlalu sibuk untuk menulis kode apa pun sekarang ... Tapi secara teori, saya pikir layak untuk mensimulasikan CA secara efisien pada GPU dengan memodelkannya setelah stensil. perhitungan. Banyak pertimbangan digunakan untuk menulis perhitungan stensil yang baik untuk GPU.

Apa pun yang Anda lakukan, menghitung status berikutnya untuk otomat seluler meminta sebanyak mungkin perhitungan daripada jumlah sel dalam otomat. Jadi untuk mendapatkan waktu yang konstan, Anda membutuhkan inti komputasi sebanyak sel.

Jumlah ini dalam GPU saat ini paling banyak beberapa ribu, sedangkan perhitungan negara berikutnya sangat sederhana sehingga saya berharap hasilnya terikat IO, yaitu Anda bisa mendapatkan perkiraan yang sangat baik dari waktu yang dibutuhkan dengan hanya mempertimbangkan perpindahan data diperlukan (dan jika itu bukan perkiraan yang baik, baik implementasinya memiliki inefisiensi atau arsitektur tidak cocok, tetapi itu akan sangat mengejutkan).

Untuk FPGA, pertanyaannya lebih sulit dan mungkin akan tergantung pada campuran memori dan unit komputasi yang tersedia. Jika saya tidak terlalu jauh, Anda tidak akan memiliki cukup memori untuk membuat semua unit sibuk dan jika Anda mengandalkan memori eksternal, Anda berada di kursi yang sama dengan GPU, bandwidth memori akan menjadi faktor pembatas dan saya tidak akan kaget jika kesimpulannya adalah bahwa tidak ada kelebihan dibandingkan GPU. (Perhatikan bahwa sementara saya bekerja dengan FPGA, itu bertahun-tahun yang lalu, sekarang mungkin ada model FPGA dengan campuran yang tepat).

ASIC menawarkan lebih banyak fleksibilitas. Anda dapat dengan mudah memiliki implementasi seperti sistolik (tetapi dengan aliran data dua arah, beberapa sistolik biasanya terbatas pada aliran data searah), masing-masing sel fisik adalah satu yang logis: sedikit memori dan logika yang diperlukan untuk menghitung keadaan berikutnya dan ditata jadi tetangga fisiknya itu logis. Anda jelas berada di ranah waktu yang konstan. Bergantung pada makro keras yang Anda miliki, Anda mungkin lebih baik menjadi sedikit kurang jelas dan memiliki sel fisik yang menyusun kembali beberapa yang logis. Tujuannya adalah untuk memaksimalkan apa yang dilakukan dalam satu chip, dengan kata lain untuk meminimalkan komunikasi dengan bagian luar chip segera setelah kebutuhan komunikasi Anda sebanding dengan jumlah sel, Anda akan memiliki bandwidth terbatas. Ya, itu berarti bahwa jika Anda perlu melihat semua sel untuk setiap langkah, Anda mungkin tidak jauh lebih baik daripada dengan GPU. (Kustom penuh hanya akan memberikan integrasi yang lebih baik, yaitu lebih banyak sel per chip).

Rangkuman: - jika Anda ingin melihat semua kondisi perantara, GPU adalah pendekatan yang paling efektif - jika Anda tidak, Anda perlu volume untuk membenarkan ASIC untuk memiliki sesuatu yang lebih baik, FPGA mungkin tidak akan menawarkan keuntungan yang cukup jika mereka Punya beberapa.

Saya bertanya-tanya apakah unit komputasi paralel masif yang disediakan dalam kartu grafis saat ini cukup baik untuk mensimulasikan 1D seluler automata (atau mungkin 2D seluler automata?) Efisien.

menjadi sangat umum, ya komputasi GPU adalah alternatif terbaik dalam perangkat keras standar yang tersedia untuk semua orang.

$O(1)$$n \le P$$n$$P$$O(1)$

di sisi FPGA dan ASIC, saya tahu bahwa ada penelitian tentang membangun CA fisik sebagai grid gerbang logika dengan negara, semua terhubung oleh tetangga mereka; yaitu susunan sistolik . Idenya adalah untuk tidak menggunakan memori global lagi tetapi mengandalkan kondisi masing-masing node di grid. Sebuah mesin jenis ini akan menjadi revolusioner sejak itu kita bisa berhenti berbicara tentang komputer yang mensimulasikan CA dan mulai berbicara tentang CA yang berjalan sebagai komputer (beberapa CA sedang menyelesaikannya).