Bagaimana Anda bisa memparalelkan simulasi 2D boids

Bagaimana Anda bisa memprogram simulasi boids 2D sedemikian rupa sehingga bisa menggunakan kekuatan pemrosesan dari berbagai sumber (cluster, gpu).

Dalam contoh di atas, partikel tidak berwarna bergerak di sekitar sampai mereka mengelompok (kuning) dan berhenti bergerak.

Masalahnya adalah bahwa semua entitas berpotensi berinteraksi satu sama lain meskipun entitas di kiri atas tidak mungkin berinteraksi dengan satu di kanan bawah. Jika domain itu dipecah menjadi segmen yang berbeda, itu mungkin mempercepat semuanya, Tetapi jika suatu entitas ingin menyeberang ke segmen lain mungkin ada masalah.

Saat ini simulasi ini bekerja dengan 5000 entitas dengan frame rate yang baik, saya ingin mencoba ini dengan jutaan jika memungkinkan.

Apakah mungkin menggunakan pohon quad untuk lebih mengoptimalkan ini? Ada saran lain?

Tesis master Simulasi Paralel Cairan Partikel oleh Mattias Linde mungkin menawarkan beberapa wawasan tentang partisi data dan algoritma untuk simulasi skala besar.

Makalahnya diarahkan ke Smoothed-Particle Hydrodynamics , yang untuk solusi naif cenderung menggunakan Spatial Hashing dengan ukuran ember sekitar ukuran jejak kernel dari partikel dalam simulasi.

Karena jarak interaksi sangat sulit di kernel SPH khas, optimasi partisi seperti itu hampir penting dalam meningkatkan sistem.

Istilah yang saya pelajari sejak lama adalah kecepatan informasi permainan.

Jika kecepatan boids Anda adalah 1 dan mereka hanya peduli dengan tetangga mereka, maka kecepatan informasinya adalah 3, yaitu, boid yang berjarak dua kotak dari Anda bisa berada dalam kisaran yang Anda pedulikan dalam satu frame:

1 gerakan kuadrat per boid dalam interaksi (1 + 1) ditambah jarak yang Anda bisa melihat hal-hal (1) sama dengan 3.

Dengan ini, kita belajar bahwa kita dapat memotong peta menjadi potongan-potongan, ukuran sekecil yang kita suka, tetapi dengan kecepatan informasi ini tumpang tindih dengan potongan-potongan tetangga.

Saya anggap Anda mengizinkan boids Anda hanya bergerak satu kotak, tetapi mereka bisa melihat tiga

Jika Anda ingin menjalankan sim paralel besar, Anda memotong menjadi 10x10 grid, tetapi tumpang tindih dengan 5 kotak di setiap tepi. Setiap kali salah satu dari Anda berada dalam jarak informasi dari tepi chunk's lokal, Anda harus memperbarui tetangga, dan begitu mereka melintasi batas, mereka bukan milik Anda. Jika tetangga mengatakan bahwa boid yang mereka kontrol telah pindah ke chunk Anda, Anda harus mengambil alih AI-nya.

Ini berarti bahwa komunikasi dilokalkan ke manajer chunk tetangga, dan lalu lintas dikurangi seminimal mungkin. Semakin banyak pekerjaan yang Anda jalankan, semakin banyak CPU yang dapat Anda gunakan untuk menyalakan simulasi, tetapi semakin banyak pekerjaan yang Anda jalankan, semakin tumpang tindihnya, dan oleh karena itu semakin banyak informasi yang melintas di antara pekerjaan / potongan saat simulasi berlangsung. Di sinilah Anda harus mendapatkan tangan berat dan menyesuaikan ukuran chunk berdasarkan kompleksitas AI dan perangkat keras apa yang Anda miliki.

Dengan membaca pertanyaan Anda, sepertinya Anda dapat memanfaatkan quad tree, membuat quad tree, dan menjalankan simulasi untuk setiap segmen pada unit pemrosesan yang berbeda. Ini akan menyebabkan pengecekan hanya terjadi pada objek yang berdekatan satu sama lain. tetapi Anda harus menyinkronkan utas Anda setiap siklus. Yang berarti mentransfer beberapa boid dari satu grup pemrosesan ke yang lain. secara umum setiap siklus akan terdiri dari 3 langkah:

1. Pindahkan semua boids dengan satu unit. (yang dapat dengan mudah diproses menggunakan banyak utas)
2. Tetapkan setiap boid ke grup *. Ini berarti menggunakan algoritme O (n) Anda harus memilih boid mana yang paling mungkin membuat tabrakan. Ini juga dapat ditangani menggunakan beberapa utas.
3. Pada akhirnya Anda harus memeriksa apakah dua boid dalam kelompok yang sama membuat tabrakan.

* Untuk membuat grup, Anda dapat menggunakan pola di bawah ini:

perhatikan bahwa beberapa boids mungkin menjadi bagian dari lebih dari satu grup, tetapi pola ini memberi Anda hasil yang lebih akurat. Anda juga dapat membuat grup sebanyak yang Anda inginkan menggunakan pola ini. Itu hanya angka yang harus Anda temukan untuk berapa banyak boids dan layar yang ukuran layarnya, berapa jumlah grup terbaik yang perlu Anda buat.

--edit--

ada ide lain tentang segmentasi yang dijelaskan dalam makalah @LarsViklund yang disarankan, dengan cara ini ada pemeriksaan ganda yang jauh lebih sedikit dan tidak perlu menambah / mengurangi jumlah utas di antara langkah-langkah:

perhatikan bahwa beberapa daerah masih merupakan bagian dari dua kelompok. dan lebar area kedua kelompok persis 2*maximum speed. Dalam kasus Anda jika boids bergerak satu pixel per langkah simulasi, Anda hanya perlu berbagi area lebar 2 pixel antara masing-masing 2 grup. dan ada area kecil yang merupakan bagian dari 4 kelompok. tetapi secara umum metode ini lebih mudah diimplementasikan dan jauh lebih cepat jika diimplementasikan dengan benar. dan omong-omong tidak ada gerakan mundur dengan cara ini, jika beberapa objek dapat bergerak, ia tidak dapat bergerak lagi.

Saya menangani masalah ini baru-baru ini menggunakan beberapa jawaban ini sebagai titik awal. Hal yang paling membantu untuk diingat adalah bahwa boids adalah semacam simulasi n-body sederhana: setiap boid adalah partikel yang mengerahkan kekuatan pada tetangganya.

Saya menemukan kertas Linde sulit dibaca; Sebagai gantinya, saya menyarankan untuk melihat "Algoritma Paralel Cepat SJ Plimpton untuk Dinamika Molekul Jangka Pendek" , yang dirujuk Linde. Makalah Plimpton jauh lebih mudah dibaca dan terperinci dengan angka-angka yang lebih baik:

Singkatnya, metode dekomposisi atom menetapkan subset atom secara permanen untuk setiap prosesor, metode dekomposisi gaya menetapkan subset perhitungan gaya berpasangan untuk setiap proc, dan metode dekomposisi spasial menetapkan sub-wilayah kotak simulasi untuk setiap proc .

Saya sarankan Anda mencoba AD. Ini yang paling mudah dipahami dan diimplementasikan. FD sangat mirip. Berikut ini adalah simulasi n-body nVidia dengan CUDA menggunakan FD, yang seharusnya memberi Anda gambaran kasar tentang bagaimana ubin dan reduksi dapat membantu secara drastis melampaui kinerja serial.

Implementasi SD pada umumnya adalah teknik optimalisasi, dan memerlukan beberapa tingkat koreografi untuk diimplementasikan. Mereka hampir selalu lebih cepat dan skalanya lebih baik.

Ini karena AD / FD membutuhkan pembuatan "daftar tetangga" untuk setiap boid. Jika setiap kebutuhan boid untuk mengetahui posisi dari tetangganya, komunikasi antara mereka adalah O ( n ²). Anda dapat menggunakan daftar tetangga Verlet untuk mengurangi ukuran area setiap pemeriksaan boid, yang memungkinkan Anda untuk membangun kembali daftar setiap beberapa langkah waktu alih-alih setiap langkah, tetapi masih O ( n ²). Di SD, setiap sel menyimpan daftar tetangga, sedangkan dalam AD / FD setiap boid memiliki daftar tetangga. Jadi alih-alih setiap boid berkomunikasi satu sama lain, setiap sel berkomunikasi satu sama lain. Pengurangan dalam komunikasi adalah dari mana peningkatan kecepatan berasal.

Sayangnya masalah boid menyabotase SD sedikit. Memiliki masing-masing prosesor melacak sel yang paling menguntungkan ketika boids agak merata di seluruh wilayah. Tapi Anda ingin boids berkumpul bersama! Jika kawanan Anda berperilaku baik, sebagian besar prosesor Anda akan berdetak, bertukar daftar kosong satu sama lain, dan sekelompok kecil sel pada akhirnya akan melakukan perhitungan yang sama seperti yang akan dilakukan oleh AD atau FD.

Untuk mengatasinya, Anda bisa menyetel ukuran sel secara matematis (yang konstan) untuk meminimalkan jumlah sel kosong pada waktu tertentu, atau menggunakan algoritma Barnes-Hut untuk quad-tree. Algoritma BH sangat kuat. Paradoksnya, sangat sulit untuk diterapkan pada arsitektur paralel. Ini karena pohon BH tidak beraturan, sehingga benang paralel akan melewatinya dengan kecepatan yang sangat bervariasi, menghasilkan perbedaan benang. Salmon dan Dubinski telah menyajikan algoritme pengabdian rekursif ortogonal untuk mendistribusikan quadtree secara merata di antara prosesor, yang harus disajikan kembali secara iteratif untuk sebagian besar arsitektur paralel.

Seperti yang Anda lihat, kita jelas berada di bidang optimisasi dan ilmu hitam pada saat ini. Sekali lagi, cobalah membaca makalah Plimpton dan lihat apakah itu masuk akal.

Saya berasumsi bahwa Anda adalah sistem toroidal, Anda dapat mempartisi ke ruang sehingga setiap unit memiliki sub area.

Pada setiap langkah partikel dipindahkan, partikel yang keluar sub area dikirim ke prosesor yang relevan; langkah komunikasi akan menyinkronkan prosesor dan langkah terakhir diambil untuk menguraikan posisi partikel asing (jika ada).

Di sini ada tiga masalah di sini:

• 1) bentuk sub area:

Satu dapat memilih untuk persegi panjang tetapi menunjukkan rasio Area / perimeter kecil dibandingkan dengan cirlces. Semakin besar perbatasan, semakin banyak partikel yang tersisa. Sementara cicles menunjukkan rasio A / p terbaik, tidak dapat digunakan untuk tessellation, jadi Anda harus memilih untuk beberapa tessellation (mungkin semi reguler) dengan rasio A / p rata-rata yang baik. Jelas menghitung indeks rumbai dengan koordinat sel harus sederhana jadi pertimbangkan ini sebelumnya untuk mencoba rumbai yang sangat eksotis.

• 2) protokol komunikasi:

Bergantung pada jenis infrastruktur komunikasi yang Anda miliki, Anda dapat memikirkan bagaimana menyebarkan informasi lintas batas di antara prosesor. Rekaman siaran vs rekonstruksi peer-to-peer vs komunikasi peer-to-peer adalah semua opsi.

• 3) Alokasi sub-Area:

Anda harus menjaga elaborasi Anda seimbang karena ada sinkronisasi di setiap langkah. Anda dapat memilih untuk mengalokasikan area secara statis atau dinamis ke prosesor. Ini bukan masalah besar jika ruang Anda secara tertutup ditutupi oleh partikel aktif tetapi saya percaya bahwa itu bisa tidak benar dalam kasus ini karena tumbukan menonaktifkan partikel. Mengubah alokasi membutuhkan langkah komunikasi yang lebih berat; beberapa jalan pintas dapat diambil jika semua prosesor berbagi informasi lintas batas tetapi Anda harus mempertimbangkannya

Coba simulasi saya untuk petunjuk https://github.com/wahabjawed/Boids-Simulation

Saya mengembangkan ini di XNA