Apa yang paling mutakhir dalam metode ODE paralel?

39

Saat ini saya sedang mencari metode paralel untuk integrasi ODE. Ada banyak literatur baru dan lama di luar sana yang menggambarkan berbagai pendekatan, tetapi saya belum menemukan survei terbaru atau artikel ikhtisar yang menggambarkan topik secara umum.

Ada buku karya Burrage [1], tetapi sudah hampir 20 tahun dan karenanya tidak mencakup banyak ide yang lebih modern seperti algoritma parareal.

[1] K. Burrage, Metode Paralel dan Sekuensial untuk Persamaan Diferensial Biasa, Clarendon Press, Oxford, 1995

parallel-computing ode numerical-analysis Florian Brucker
sumber

35

Saya tidak mengetahui adanya artikel ikhtisar terkini, tetapi saya terlibat aktif dalam pengembangan algoritma PFASST sehingga dapat berbagi beberapa pemikiran.

Ada tiga kelas luas teknik paralel waktu yang saya ketahui:

melintasi metode - tahapan independen RK atau integrator ekstrapolasi dapat dievaluasi secara paralel; lihat juga RIDC (algoritma koreksi tangguhan integral revisionis)
melintasi masalah - relaksasi bentuk gelombang
melintasi domain waktu - Parareal; PITA (algoritma waktu paralel); dan PFASST (skema aproksimasi penuh paralel dalam ruang dan waktu).

Metode yang diparalelkan di seluruh metode biasanya berkinerja sangat dekat dengan spesifikasi tetapi tidak skala di luar segelintir prosesor (waktu). Biasanya mereka relatif lebih mudah diimplementasikan daripada metode lain dan bagus jika Anda memiliki beberapa core tambahan dan mencari speedup yang dapat diprediksi dan sederhana.

Metode yang diparalelkan di seluruh domain waktu termasuk Parareal, PITA, PFASST. Metode-metode ini semuanya iteratif dan terdiri dari penyebar "kasar" yang tidak mahal (tapi tidak akurat) dan penyebar "baik" yang mahal (tapi akurat). Mereka mencapai efisiensi paralel dengan mengevaluasi secara berulang-ulang propagator halus secara paralel untuk meningkatkan solusi serial yang diperoleh dengan menggunakan propagator kasar.

$E$ $E < 1/K$ $K$

Banyak permainan dapat dimainkan dengan semua metode ini untuk mencoba dan mempercepatnya, dan tampaknya kinerja teknik lintas domain tergantung pada masalah apa yang Anda pecahkan dan teknik mana yang tersedia untuk mempercepat kasar. propagator (grid kasar, operator kasar, fisika kasar dll).

Beberapa referensi (lihat juga referensi yang tercantum di koran):

Makalah ini menunjukkan bagaimana berbagai metode dapat diparalelkan di seluruh metode: Perbandingan teoretis Runge-Kutta eksplisit tingkat tinggi, ekstrapolasi, dan metode koreksi yang ditangguhkan ; Ketcheson dan Waheed.
Makalah ini juga menunjukkan cara yang bagus untuk memparalelkan seluruh metode, dan memperkenalkan algoritma RIDC: Integrator tingkat tinggi paralel ; Christlieb, MacDonald, Ong.
Makalah ini memperkenalkan algoritma PITA: Metode Implisit Waktu-Paralel untuk Mempercepat Solusi Masalah Dinamika Struktural Nonlinier ; Cortial dan Farhat.
Ada banyak makalah tentang Parareal (hanya Google itu).
Berikut ini adalah makalah tentang metode Nievergelt: Pendekatan komunikasi minimal untuk integrasi waktu paralel ; Barker.
Makalah ini memperkenalkan PFASST: Menuju metode waktu paralel paralel yang efisien untuk persamaan diferensial parsial ; Emmett dan Minion;
Makalah ini menjelaskan aplikasi PFASST: Pemecah N-tubuh paralel ruang-waktu yang sangat besar ; Speck, Ruprecht, Krause, Emmett, Minion, Windel, Gibbon.

Saya telah menulis dua implementasi PFASST yang tersedia di internet ': PyPFASST dan libpfasst .

Matthew Emmett
sumber

1

Saat ini saya sedang belajar parareal. Dan saya pikir itu sangat membantu saya.

eccstartup

Ini adalah gambaran yang bagus. Namun harus secara eksplisit disebutkan bahwa ODE sering diselesaikan setelah diskritisasi spasial dari PDE. Oleh karena itu, paralelisme di seluruh metode dapat menghasilkan skalabilitas yang sangat besar ke ribuan core jika domain spasial Anda cukup besar. Ini karena sebagian besar waktu komputasi masuk ke dalam perhitungan, misalnya, evaluasi RHS tahap RK.

NoseKnowsSemua

15

Meskipun postingan ini sekarang berumur dua tahun, jika ada orang yang menemukannya, izinkan saya memberikan pembaruan singkat:

Martin Gander baru-baru ini menulis artikel ulasan yang bagus, yang memberikan perspektif historis di lapangan dan membahas banyak metode PINT yang berbeda: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

Sekarang ada juga situs web komunitas yang mencantumkan sangat banyak referensi dan memberikan deskripsi berbagai metode: http://www.parallel-in-time.org/

Diskusi tentang algoritma pararel paralel dalam waktu khususnya dapat ditemukan di sini: https://en.wikipedia.org/wiki/Parareal

Daniel
sumber

1

Sedikit terkejut bahwa Gander tidak berbicara tentang pendekatan MGRIT oleh Falgout, dkk., Terutama karena tampaknya didukung oleh perangkat lunak yang bagus (XBraid), tapi saya tahu makalah MGRIT baru keluar baru-baru ini.

Geoff Oxberry

1

Hai Geoff, saya cukup yakin Martin Gander menulis makalah sebelum makalah MGRIT diterbitkan - sementara makalah tinjauan akan muncul pada tahun 2015, saya pikir cetakan sudah online akhir 2013.

Daniel

1

Sepintas sepertinya "paralel di seluruh metode" dihilangkan dalam ulasan ini - misalnya, ekstrapolasi tidak pernah disebutkan.

David Ketcheson

4

$u_0$ $u(t)=\exp(-\lambda t)u_0,$ $\mathrm{Re}\,\lambda>0.$

Hui Zhang
sumber

Seperti yang saya katakan, saya sudah menemukan banyak artikel tentang masing-masing topik. Apa yang saya lewatkan adalah gambaran umum tentang pendekatan tersebut.

Florian Brucker

1

FWIW, algoritma PFASST menunjukkan konvergensi yang sangat baik (akan segera diterbitkan) untuk sistem Hamilton bahkan untuk banyak (ratusan) prosesor waktu. Karena itu, mendapatkan speedup yang cukup besar tergantung (sekali lagi) pada membuat propagator kasar jauh lebih murah daripada propagator halus - ekspansi multi-bagian atau beberapa pendekatan multi-fisik lainnya tampaknya diperlukan untuk mendapatkan peningkatan yang baik untuk sistem partikel.

Matthew Emmett

Apa yang paling mutakhir dalam metode ODE paralel?

Jawaban: