Bagaimana Anda bisa memparalelkan simulasi 2D boids

16

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

contoh boids

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?

Sycren
sumber
Apakah Anda meminta pengoptimalan atau cara memparalelkan? Ini adalah hal yang berbeda.
bummzack
@bummzack Cara memparalelkan, saya baru saja menambahkan penjelasan lebih lanjut, apakah itu membantu?
Sycren

Jawaban:

7

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.

Lars Viklund
sumber
makalah yang bagus, tetapi bagian aktual tentang pertanyaan ini tampaknya banyak seperti jawaban @Fxlll.
Ali1S232
Saya akan mengatakan bagian sebenarnya dari makalah ini adalah bagaimana memecahkan kasus tepi dengan memperkenalkan protokol komunikasi, itulah bagian yang sulit, partisi quad cukup jelas dan dengan sendirinya tidak menyelesaikan masalah kasus tepi.
Maik Semder
4

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.

Richard Fabian
sumber
bayangkan dunia adalah 1.000.000 x 1.000.000 grid, dan ada 10.000.000 boid di dunia, dan setiap boid dapat bergerak tepat satu kotak setiap belokan, dapatkah Anda menjelaskan bagaimana memeriksa apakah ada boid di lingkungan orang lain?
Ali1S232
Saya menduga bahwa kami dapat membaginya menjadi 2000 500x500 kotak atau lebih besar. setiap kotak berisi daftar kapal serta daftar tetangga. Jika boid keluar dari persegi, itu dihapus dari daftar boids dan ditambahkan ke persegi lainnya. Masalah dengan metode ini yang bisa saya lihat adalah jika Anda menambahkan sesuatu dengan berkelompok yang lebih besar dari persegi. solusi quadtree harus dinamis, tetapi saya tidak yakin seberapa mahal itu
Sycren
@Gajet: Anda hanya perlu memeriksa boid di chunk Anda atau batas yang dikelola tetangga. Ingat, perbatasan dijamin oleh desain untuk memperhitungkan seberapa jauh entitas dapat bergerak ditambah jarak yang bisa dilihat entitas. @ Scren: berkelompok, meskipun bagi kami tampaknya entitas besar, masih hanya efek skala kecil. Sekelompok ikan tidak mengikuti sekolah, mereka mengikuti tetangga yang dapat diamati.
Richard Fabian
2

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:

masukkan deskripsi gambar di sini

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:

masukkan deskripsi gambar di sini

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.

Ali1S232
sumber
Kedengarannya seperti ide yang bagus, tetapi sebelum bergerak di langkah 1, saya perlu melakukan deteksi tabrakan untuk melihat apakah mereka bisa bergerak bukan?
Sycren
Anda dapat memindahkannya kemudian memeriksa apakah ada tabrakan yang terjadi pada gerakan itu (untuk boid yang tepat), jika tidak biarkan simulasi berlanjut.
Ali1S232
Terima kasih, itu lebih masuk akal. Selain quadtrees, dapatkah Anda memikirkan cara lain untuk membagi beban kerja?
Sycren
Seperti yang Anda lihat, segmentasi saya bukan sepenuhnya quad tree itu sendiri, ia memiliki satu lagi grup tambahan untuk meningkatkan akurasi, gaya quad tree lebih mudah ditangani. Tergantung pada ukuran dunia Anda dapat menambahkan lebih banyak grup yang berarti lebih sedikit memeriksa di setiap siklus. itu adalah tradeoff antara konsumsi memori dan kecepatan komputasi. dan itu tidak harus menjadi satu utas untuk setiap grup. Anda dapat memiliki beberapa utas untuk menghitung lebih dari satu grup. Anda juga dapat membagi perhitungan grup antara dua atau lebih utas.
Ali1S232
@ Dapatkan jika saya memahami gambar Anda dengan benar, akan ada banyak perhitungan ganda, karena area grup yang tumpang tindih sangat besar. Mengingat bahwa pertanyaannya meminta untuk disimulasikan hingga jutaan poin, itu akan menjadi pemborosan besar.
Maik Semder
2

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.

lelucon buruk
sumber
1

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

FxIII
sumber
@Fxlll Saya tidak yakin apa yang Anda maksud dengan sistem toroidal, ini tidak dalam bentuk donat. Apakah maksud Anda jika sebuah partikel keluar dari sisi kanan, ia muncul kembali di sebelah kiri? Jika tidak demikian halnya, jika sebuah partikel mengenai sisi kanan ia mencoba bergerak ke arah yang berbeda.
Sycren
@Sycren ok dalam hal ini Anda harus melakukan pertimbangan tentang rumbai dan merawat area di tepian dengan cara khusus
FxIII
-1

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

Saya mengembangkan ini di XNA

pengguna106369
sumber
Hanya menautkan ke proyek yang lengkap bukanlah jawaban yang baik. Pembaca dipaksa untuk menggali melalui sumber Anda sampai mereka menemukan bagian yang relevan dengan pertanyaan dan kemudian masih perlu memahami bagaimana itu memecahkan masalah. Bisakah Anda jelaskan dalam bahasa Inggris sederhana bagaimana Anda telah mendekati masalah dan apa kelebihannya dari solusi yang dijelaskan dalam jawaban lain? Anda dapat menyalin & menempelkan beberapa cuplikan kode pendek ke jawaban Anda jika mereka membantu memahami deskripsi Anda.
Philipp