Apa kelebihan dan kekurangan dari penguraian partikel dan algoritma paralelisasi dekomposisi domain?

Saya menjalankan simulasi dinamika molekul (MD) menggunakan beberapa paket perangkat lunak, seperti Gromacs dan DL_POLY.

Gromacs sekarang mendukung algoritma dekomposisi partikel dan domain dekomposisi. Secara default, simulasi Gromacs menggunakan dekomposisi domain, meskipun selama bertahun-tahun, hingga saat ini, dekomposisi partikel adalah satu-satunya metode yang diterapkan dalam Gromacs. Dalam salah satu makalah Gromacs (DOI 10.1002 / jcc.20291), penulis memberikan alasan untuk pilihan awal penguraian partikel:

"Keputusan desain awal adalah pilihan untuk bekerja dengan dekomposisi partikel daripada dekomposisi domain untuk mendistribusikan pekerjaan pada prosesor. Dalam kasus terakhir, domain spasial ditugaskan untuk prosesor, yang memungkinkan menemukan tetangga spasial dengan cepat hanya melalui komunikasi lokal, tetapi komplikasi akibat untuk partikel yang bergerak melewati batas spasial cukup besar. Dekomposisi domain adalah pilihan yang lebih baik hanya ketika ukuran sistem linier jauh melebihi rentang interaksi, yang jarang terjadi dalam dinamika molekuler. Dengan dekomposisi partikel setiap prosesor menghitung kekuatan dan mengoordinasikan / memperbarui kecepatan untuk fraksi partikel yang ditentukan, menggunakan daftar tetangga yang dikomputasi secara merata didistribusikan melalui prosesor$F_{ij}$ timbul dari interaksi pasangan antara partikel dan, yang diperlukan untuk pembaruan kecepatan kedua partikeldan $i$$j$$i$$j$, dihitung hanya sekali dan dikomunikasikan ke prosesor lain. Setiap prosesor menyimpan dalam memori lokal set lengkap sistem koordinat daripada membatasi penyimpanan ke koordinat yang dibutuhkan. Ini lebih sederhana dan menghemat overhead komunikasi, sedangkan klaim memori biasanya bukan faktor pembatas sama sekali, bahkan untuk jutaan partikel. Tetangga, di sisi lain, yang dapat mengandung hingga 1000 kali jumlah partikel, didistribusikan di atas prosesor. Komunikasi pada dasarnya terbatas pada pengiriman koordinat dan kekuatan sekali per langkah waktu di sekitar cincin prosesor. Pilihan-pilihan ini telah terbukti kuat dari waktu ke waktu dan mudah diterapkan pada kelompok prosesor modern. "

Apa yang mereka maksud dengan "ukuran sistem linier" dalam kalimat "Dekomposisi domain adalah pilihan yang lebih baik hanya ketika ukuran sistem linier jauh melebihi rentang interaksi, yang jarang terjadi dalam dinamika molekul"? Dari paragraf di atas, saya mendapatkan gagasan bahwa dekomposisi partikel memiliki keuntungan bahwa seseorang tidak harus berurusan dengan partikel yang bergerak melintasi batas-batas domain; alih-alih, Anda hanya perlu memiliki memori yang cukup untuk setiap prosesor untuk menyimpan konfigurasi sistem total . Jadi dekomposisi partikel terlihat sangat menguntungkan, sedangkan dekomposisi domain terlihat sangat tidak menguntungkan.

Saya yakin bahwa ini adalah pertanyaan yang sangat rumit (dan mungkin menjadi pokok bahasan banyak buku), tetapi pada dasarnya, jika dekomposisi partikel tampak sangat menguntungkan, mengapa ada yang perlu menggunakan dekomposisi domain? Apakah dekomposisi domain hanya menguntungkan jika ukuran sistem sangat besar (membuatnya sulit atau tidak mungkin untuk menyimpan konfigurasi total di setiap prosesor)? Berdasarkan paragraf yang dikutip di atas, saya tidak yakin mengapa dekomposisi domain sekarang, baru-baru ini, algoritma paralelisasi default di Gromacs.

Tampaknya DL_POLY sekarang (versi 4) juga menggunakan dekomposisi domain. Dari manual versi 4:

"Pembagian data konfigurasi dengan cara ini didasarkan pada lokasi atom dalam sel simulasi, seperti alokasi geometrik data sistem adalah ciri khas dari algoritma DD. Perhatikan bahwa agar strategi ini bekerja secara efisien, simulasi sistem harus memiliki kerapatan yang cukup seragam, sehingga setiap prosesor mengalokasikan bagian data atom yang hampir sama (sebanyak mungkin). Melalui pendekatan ini, perhitungan gaya dan integrasi persamaan gerak dibagi (secara wajar) secara merata antara prosesor dan sebagian besar dapat dihitung secara independen pada setiap prosesor.Metode ini secara konsep sederhana namun sulit untuk diprogram dan sangat cocok untuk simulasi skala besar, di mana efisiensi tertinggi.

...

Dalam kasus strategi DD, algoritma SHAKE (RATTLE) lebih sederhana daripada metode Replicated Data dari DL_POLY Classic), di mana pembaruan global dari posisi atom (penggabungan dan penyambungan) diperlukan. "

Ini membuatnya terdengar seolah-olah dekomposisi domain baik karena mungkin lebih efisien, meskipun mungkin lebih sulit untuk diterapkan.

Di sisi lain, versi sebelumnya (DL_POLY Classic) menggunakan paralelisasi data yang direplikasi, yang tampaknya menjadi nama lain untuk dekomposisi partikel. Dari manual versi itu:

$\textbf{r}_i$$\textbf{v}_i$$\textbf{f}_i$$N$atom dalam sistem simulasi, direproduksi pada setiap node pemrosesan). Dalam strategi ini sebagian besar kekuatan perhitungan dan integrasi persamaan gerak dapat dibagi dengan mudah dan sama antara node dan sebagian besar diproses secara independen pada setiap node. Metode ini relatif sederhana untuk diprogram dan cukup efisien. Selain itu, dapat "runtuh" ​​untuk berjalan pada satu prosesor dengan sangat mudah. Namun strategi ini bisa jadi mahal dalam memori dan memiliki overhead komunikasi yang tinggi, tetapi secara keseluruhan strategi ini telah terbukti berhasil melalui beragam aplikasi.

Paragraf ini tampaknya secara umum konsisten dengan paragraf pertama dalam pertanyaan ini, kecuali bahwa ia mengatakan bahwa dekomposisi data / partikel yang direplikasi memiliki "overhead komunikasi yang tinggi." Paragraf dari makalah Gromacs tampaknya mengatakan sebaliknya - bahwa dekomposisi partikel lebih disukai karena memiliki overhead komunikasi yang lebih rendah daripada dekomposisi domain.

Apakah Anda punya pikiran?

Dekomposisi partikel dan domain terhubung langsung ke dua metode utama untuk mempercepat perhitungan gaya untuk sistem dengan interaksi jarak terbatas - Daftar tetangga verlet dan daftar yang terhubung sel. Jika Anda ingin memerinci, ada buku yang cukup bagus dari Allen dan Tildesley, yang disebut Computer Simulation of Liquids , yang oleh banyak orang dianggap sebagai "Alkitab" dari Dinamika Molekuler dan studi-studi Monte Carlo. Lalu ada Simulasi Numerik dalam Dinamika Molekuler dari Griebel, Knapek dan Zumbusch, yang masuk jauh ke berbagai teknik untuk implementasi paralel MD.

$O(N^2)$$O(N)$

$O(N)$$O(N)$ $N$itu bersisik lebih baik. Oleh karena itu argumen ukuran linier. Metode dekomposisi domain adalah perpanjangan langsung dari metode daftar tautan sel - sel dibagi di antara CPU yang berbeda.

Masalah dengan dekomposisi domain adalah bahwa ia harus berkomunikasi ketika partikel berpindah dari satu sel ke sel lain yang dirawat oleh CPU lain. Ini bisa menjadi masalah pada suhu simulasi yang lebih tinggi di mana partikel cenderung bergerak lebih jauh dari posisi keseimbangannya, atau ketika ada aliran partikel. Juga informasi dari sel di perbatasan domain harus ditransfer pada setiap iterasi ke domain tetangga. Tetapi semua ini adalah komunikasi yang sinkron secara lokal dan dapat dilakukan dengan sangat efisien.

Data yang direplikasi adalah pendekatan yang paling mudah, tetapi sayangnya hal itu mengharuskan pada setiap langkah semua informasi posisi dan kecepatan disinkronkan secara global. Ini benar-benar tidak berskala dengan baik dan untuk sistem yang sangat besar jumlah memori global adalah ukuran struktur data dikalikan jumlah CPU yang digunakan, sementara salah satu tujuan pemrosesan paralel adalah distribusi data sehingga setiap CPU kurang memegang dari jumlah data global.

Singkatnya, tidak ada metode "satu ukuran cocok untuk semua", cocok untuk semua sistem yang disimulasikan. Sebagian besar waktu strategi parallelisation terbaik dapat disimpulkan dari sistem geometri dan yang sesuai untuk kasus itu kode MD dapat dipilih - mereka semua menerapkan lebih kurang bidang kekuatan dan integrator yang mendasari yang sama setelah semua.

Dengan "Dekomposisi domain adalah pilihan yang lebih baik hanya ketika ukuran sistem linier jauh melebihi rentang interaksi, yang jarang terjadi dalam dinamika molekuler" para penulis makalah GROMACS itu (sangat tua) berarti bahwa jika ukuran spasial dari daftar tetangga adalah dari urutan 1 nm, dan sel simulasi hanya beberapa nanometer, maka biaya overhead dari melakukan dekomposisi domain terlalu tinggi. Anda juga dapat menerima distribusi informasi all-to-all dalam dekomposisi partikel, dan tidak perlu menghabiskan waktu pada semua pembukuan untuk dekomposisi domain.

Masalah dengan dekomposisi partikel ketika GROMACS menerapkannya adalah bahwa dari waktu ke waktu partikel yang ditugaskan untuk setiap prosesor berdifusi melalui ruang. Karena tanggung jawab untuk menghitung setiap interaksi ditetapkan oleh lokasi awal mereka, difusi secara bertahap meningkatkan volume total ruang yang perlu diketahui setiap prosesor untuk membangun daftar tetangganya, bahkan jika total perhitungan yang dijelaskan oleh daftar tetangganya konstan. Dalam praktiknya, Anda akan memulai kembali simulasi secara berkala untuk mereset lokasi data dan komunikasi.

Anggapan Anda bahwa "dekomposisi partikel memiliki keuntungan bahwa seseorang tidak harus berurusan dengan partikel yang bergerak melintasi batas-batas domain" tidak berlaku jika difusi signifikan terhadap skala waktu simulasi.

Dekomposisi domain berurusan dengan "muka" ini dengan memigrasikan tanggung jawab untuk interaksi bersama dengan difusi, sehingga meningkatkan lokalitas data pada setiap prosesor, dan meminimalkan volume komunikasi.

Penafian: Saya membantu mengembangkan GROMACS, dan mungkin akan merobek implementasi dekomposisi partikel minggu depan ;-)

Saya ingin menambahkan jawaban Hristo Iliev. Sementara jabatannya sebagian besar berbicara tentang kompleksitas komputasi , ketika datang ke paralelisasi, kompleksitas komunikasi setidaknya sama pentingnya - dan bahwa itu adalah alasan utama untuk dekomposisi domain.

Mesin paralel modern biasanya memiliki semacam topologi torus. Ini berarti bahwa setiap CPU memiliki sejumlah CPU "tetangga" yang dapat berkomunikasi dengan sangat cepat. Berkomunikasi ke CPU yang bukan tetangga lebih mahal. Oleh karena itu, selalu lebih baik untuk memiliki algoritma yang hanya perlu berkomunikasi dengan CPU tetangga.

$P$$\mathcal{O}(P^2)$

$P$$\mathcal{O}(P)$

$\mathcal{O}(P)$

Perhatikan, bagaimanapun, bahwa sistem yang tidak seragam tidak umum seperti kedengarannya, mereka hanya terjadi ketika mensimulasikan sesuatu dalam ruang hampa, atau ketika menggunakan pelarut implisit. Kerapatan kristal dan cairan cukup dekat untuk menjalankan dekomposisi domain.