Contoh perhitungan PDE menggunakan paralelisme di ruang dan waktu

14

Dalam solusi numerik PDE nilai batas awal, sangat umum untuk menggunakan paralelisme dalam ruang . Adalah jauh lebih jarang untuk menggunakan beberapa bentuk paralelisme dalam diskritisasi waktu , dan bahwa paralelisme biasanya jauh lebih terbatas. Saya menyadari semakin banyak kode dan karya yang diterbitkan yang menunjukkan paralelisme temporal, tetapi tidak ada satupun yang memasukkan paralelisme spasial.

Adakah contoh implementasi yang memasukkan paralelisme baik dalam ruang maupun waktu? Saya tertarik dengan publikasi dan kode yang tersedia.

David Ketcheson
sumber
Saya baru saja menemukan pracetak ini, menggabungkan Parareal dengan dekomposisi domain spasial untuk Navier-Stokes yang tidak dapat dikompres pada 2048 prosesor: icsweb.inf.unisi.ch/preprints/preprints/file201203.pdf
David Ketcheson

Jawaban:

8

The PFASST (Paralel penuh Approximation Skema di Ruang dan Waktu) dan PEPC (Pretty Efisien Paralel Coulomb) algoritma baru-baru ini digunakan bersama-sama untuk mencapai paralelisme dalam ruang dan waktu.

PFASST melakukan paralelisme waktu, PEPC melakukan paralelisme ruang. Hasil ini baru-baru ini dipresentasikan pada konferensi DD21 , dan kami telah menyiapkan proposal untuk SC12 yang menggambarkan kombinasi PFASST + PEPC.

Masalah "kecil" yang terdiri dari 4 juta partikel (PEPC adalah pemecah N-tubuh paralel) ditunjukkan untuk skala hingga 8192 inti pada JUGENE hanya menggunakan PEPC (yaitu, hanya paralel dalam ruang). Di luar ini, biaya komunikasi menjadi signifikan dan efisiensi paralel mulai menurun. Penambahan PFASST memungkinkan masalah ukuran tetap ini dijalankan pada 262.144 core (yaitu, kami mengisi JUGENE) dengan menggunakan 32 "waktu" prosesor (masing-masing terdiri dari 8192 "spasial" core).

Meskipun efisiensi paralel dari algoritma time-parallel tidak 100%, kami dapat memperoleh peningkatan sekitar 6,5x menggunakan 32 prosesor PFASST dengan konfigurasi PFASST + PEPC ini.

Berikut ini tautan ke pracetak: Pemecah N-tubuh paralel ruang-waktu yang sangat besar

Matthew Emmett
sumber
Matt yang kedengarannya cukup rapi, perbarui dengan tautan ke konsep saat Anda siap.
Aron Ahmadia
Luar biasa, hanya apa yang saya cari. Omong-omong, kerja bagus.
David Ketcheson
Terima kasih! Saya akan mencoba memposting tautan segera. BTW, saya juga berhasil menggunakan DA PETSc untuk mendistribusikan domain spasial pemecah air dangkal di dalam PyPFASST.
Matthew Emmett
1
@AronAhmadia, tautan ke pracetak ditambahkan!
Matthew Emmett
4

Ada juga DG ruang-waktu dan metode Galerkin terus menerus. Setelah pilihan quadrature, DG ruang-waktu dengan kisi terstruktur dalam arah waktu setara dengan metode Runge-Kutta implisit. Metode DG ruang-waktu, bagaimanapun, memungkinkan untuk ukuran langkah yang berbeda di berbagai bagian domain, kasus yang sulit untuk dianalisis untuk metode RK implisit. Metode multigrid ruang-waktu juga dapat diterapkan dalam konteks ini.

Jed Brown
sumber
Saya tidak mengerti bagaimana ini paralel waktu. Bisakah Anda menunjukkan contoh atau menjelaskan lebih banyak?
David Ketcheson
Saat Anda membuat domain lebih besar, Anda bisa membusuk menjadi lebih banyak domain dengan ukuran tertentu. Metode ruang-waktu menambahkan dimensi waktu ke domain, sehingga meningkatkan paralelisme. Perhatikan bahwa ada manfaat komputasi yang sangat besar untuk melakukan beberapa hal terkait sekaligus sehingga untuk kinerja maksimum dengan slab waktu berukuran sedang, Anda mungkin masih terurai hanya dalam ruang dan vektorisasi secara lokal dalam dimensi waktu.
Jed Brown
2

Setelah Anda mempertimbangkan parallelsim ruang-waktu, subdomain adalah ruang-waktu lebih dari beberapa level waktu. Metode yang disebut relaksasi bentuk gelombang mengeksploitasi subdomain ruang-waktu tetapi memaralelkan hanya dalam ruang (tanpa partisi dalam dimensi waktu). Jadi cartesian dari partisi ruang dan partisi waktu memberikan semacam paralelisme ruang-waktu. Anda dapat menemukan kertas tentang metode kartesius di sini . Seperti yang disebutkan Jed Brown dalam jawabannya, metode ruang-waktu tidak hanya memberikan parallelsim yang lebih fleksibel tetapi juga adaptifitas untuk diskritisasi. Pada topik yang terakhir, Anda dapat google karya Schwab, lihat juga proyek mereka . Untuk karya yang mengeksploitasi paralelisme dan adaptasi, Anda dapat menonton di beranda R. Haynes .

Hui Zhang
sumber
1

Lihat algoritma Parareal dan pekerjaan terkait seperti koreksi spektral ditangguhkan (pencarian Google sederhana ternyata cukup banyak materi). Ide dasarnya adalah menggunakan "mesh" kasar dalam waktu dan melakukan loncatan waktu kasar, tetapi kemudian kembali dan melakukan koreksi pada skala waktu yang lebih baik. Tampaknya sebagian besar digunakan dalam simulasi fluida, tapi saya di bidang elektromagnetik, jadi saya tidak bisa mengatakan lebih banyak tentang itu. Satu-satunya alasan saya mengetahuinya adalah karena saya menghadiri seminar tentang pendekatan koreksi yang ditangguhkan dan tampaknya sangat menarik bahwa segala bentuk paralelisasi dapat dilakukan pada waktunya.

Victor Liu
sumber
Saya tahu itu, tetapi bisakah Anda menunjukkan kasus di mana mereka digunakan bersama dengan paralelisme spasial?
David Ketcheson
Untuk menjadi jelas, ditangguhkan atau cacat skema koreksi sendiri tidak ada hubungannya dengan skema Parareal dan / atau paralel waktu.
Matthew Emmett
1

Metode pemotretan berganda yang digunakan dalam kontrol optimal dirancang sedemikian rupa sehingga sub-masalah pada setiap interval pemotretan dapat diselesaikan secara paralel. Saya tidak tahu makalah yang menyandingkan ini dengan paralelisme spasial (tidak ada banyak masalah kontrol optimal yang telah diselesaikan di masa lalu di mana persamaannya adalah PDE spasial yang tergantung waktu) tetapi akan jelas bagaimana melakukan paralelisme di ruang dan waktu.

Wolfgang Bangerth
sumber