Bagaimana masalah gravitasi n-tubuh diselesaikan secara paralel?

Bagaimana masalah gravitasi n-tubuh diselesaikan secara numerik secara paralel?

Apakah tradeoff presisi-kompleksitas mungkin?

Bagaimana presisi mempengaruhi kualitas model?

Ada berbagai macam algoritma; Barnes Hut adalah metode yang populer, dan Metode Fast Multipole adalah alternatif O ( N ) yang jauh lebih canggih .$\mathcal{O}(N \log N)$$\mathcal{O}(N)$

Kedua metode menggunakan struktur data pohon di mana node pada dasarnya hanya berinteraksi dengan tetangga terdekat mereka di setiap tingkat pohon; Anda dapat berpikir untuk memisahkan pohon di antara serangkaian proses pada kedalaman yang cukup, dan kemudian meminta mereka bekerja sama hanya pada tingkat tertinggi.

Anda dapat menemukan makalah terbaru membahas FMM pada mesin petascale di sini .

Lihatlah metode multipole cepat . Ini sangat scalable dan . Hal ini memungkinkan perdagangan antara presisi dan biaya. Berikut adalah contoh di mana dijalankan di 42 Tflops pada cluster GPU .$O(n)$

Sebagai sumber alternatif, Anda juga bisa melihat metode seperti Ewald berbasis mesh. Asal-usul metode "partikel mesh" (seperti PPPM dan partikel halus smooth Ewald) terletak pada simulasi galaksi untuk astrofisika; koneksi ke tagihan adalah efek samping yang tidak disengaja (yang kebetulan akhirnya menyalip penggunaan aslinya).

Baru-baru ini, ada juga beberapa literatur tentang metode penjumlahan bertingkat yang serupa dengan metode multipole cepat dan Barnes-Hut, tetapi dapat menawarkan keuntungan dalam keadaan yang berbeda (geometri yang lebih umum dan fleksibel, beberapa peningkatan efisiensi, dll.).

Untuk masalah gravitasi n-body klasik , saya pikir dua makalah berikut melakukan pekerjaan yang baik dalam membahas isi implementasi paralel untuk langkah evaluasi gaya. Meskipun makalah membahas implementasi GPU, mereka melakukan pekerjaan dengan baik dalam membahas paralelisme dan memberikan rincian algoritma:

Makalah ini oleh Nyland, Harris, dan Prins menyajikan algoritma n-tubuh langsung di CUDA untuk GPU.

Ini kertas lainnya oleh Yokota dan Barba memiliki diskusi yang baik pada dari treecode dan algoritma cepat multipole juga dalam konteks GPU-komputasi

Pertanyaan Anda tentang keakuratan simulasi numerik n-tubuh sedikit lebih terlibat dan ada begitu banyak detail penting sehingga jawaban dapat menelurkan beberapa buku. Saya pikir pemikiran terbaik yang harus dilakukan adalah memberi Anda beberapa referensi buku. Saya menyarankan:

Simulasi Gravitasi N-tubuh oleh Sverre J. Aarseth

Simulasi komputer menggunakan partikel oleh Hockney dan Eastwood. (Maaf tidak ada versi pdf)

Jika Anda memerlukan pendekatan implementasi sederhana yang tidak optimal dalam arti asimptotik, Anda mungkin ingin mempertimbangkan untuk menggunakan operasi komunikasi semua-kumpulkan. Karena masing-masing N-body perlu mengetahui efek gravitasi dari benda lain, penting bagi setiap prosesor untuk mengetahui seluruh dataset. Inilah yang dilakukan semua operasi pengumpulan. Ada sebuah buku yang bagus: Pemrograman Paralel dalam C dengan MPI dan OPENMP oleh Michael J. Quinn (2004) yang membahas topik ini dengan tepat di halaman 82. Mungkin patut untuk dilihat untuk memberi Anda permulaan.

Lihat Google Cendekia dan cari referensi untuk HACC dan GADGET, di antara kode-kode lainnya.