Saya selalu mendengar bahwa paralelisasi yang mudah adalah salah satu keuntungan dari metode DG, tetapi saya tidak benar-benar melihat mengapa salah satu dari alasan itu tidak berlaku untuk Galerkin terus menerus.
finite-element
parallel-computing
discontinuous-galerkin
Truman Ellis
sumber
sumber
Jawaban:
Salah satu alasan mengapa metode DG dapat menerima lebih banyak perhatian sebagai metode paralel adalah bahwa mudah dilihat bahwa metode tersebut secara inheren lokal untuk suatu elemen. Kopling dalam metode DG lemah, karena hanya terjadi melalui tepi yang berdekatan (atau wajah dalam 3d). Jadi, untuk segitiga atau paha depan, DG akan berkomunikasi paling banyak dengan tiga atau empat prosesor. Sedangkan metode CG akan mencakup sudut elemen, sehingga valensi sudut elemen menjadi penting. Bergantung pada generator mesh yang digunakan, valensi ini bisa delapan prosesor (mungkin lebih tinggi). Jadi biaya merakit turunan waktu dapat dianggap "lebih tinggi" untuk metode CG. Ini terutama menyangkut metode spektral, di mana volume informasi yang dikomunikasikan bisa sangat besar (dan persembunyian latensi dapat menjadi lebih sulit karena ukuran setiap partisi menyusut).
Tetapi biaya tambahan ini untuk CG untuk merakit turunan waktunya bisa dikompensasi dengan strategi penyeimbangan beban yang berbeda. Strategi partisi mesh yang berbeda (saya paling farmiliar dengan METIS) memungkinkan pengguna untuk menyeimbangkan beban melalui berbagai metrik, misalnya, memastikan setiap partisi memiliki kira-kira jumlah elemen yang sama atau membatasi jumlah komunikasi antara partisi. Saya merasakan suatu alasan bahwa percakapan sehari-hari dari DG dengan mudah dapat diparalelkan adalah bahwa pemecahan yang naif dari masalah menjadi bagian-bagian yang sama dapat memberikan implementasi paralel yang sangat efisien, bahkan menghadirkan speedup super linier dalam kasus-kasus tertentu karena efek cache (lihat misalnya Baggag et. Al . atau Altmann et. al.). Sedangkan CG mungkin memerlukan metode partisi yang lebih pintar. Jadi mungkin itu terjadi bahwa mengubah diskritisasi spasial dari DG ke CG, katakanlah, akan membutuhkan seseorang untuk juga mempertimbangkan kembali bagaimana membagi mesh menjadi subproblem.
sumber
Dari bertahun-tahun saya menulis perangkat lunak FEM, saya percaya bahwa pernyataan bahwa skema DG lebih cocok untuk paralelisasi daripada skema CG adalah apokrif. Ini sering digunakan dalam pengantar makalah DG sebagai pembenaran untuk metode DG, tapi saya belum pernah melihatnya didukung dengan referensi yang benar-benar menyelidiki pertanyaan. Ini serupa dengan setiap proposal NSF tentang proyek teori bilangan yang merujuk "kriptografi" sebagai bidang dampak yang lebih luas, pernyataan bahwa dalam generalitas ini juga tidak pernah dibuktikan.
Faktanya, saya percaya bahwa dengan satu pengecualian dari skema loncatan waktu eksplisit dan, mungkin, masalah di mana Anda harus membalik matriks massa, skema DG tidak lebih baik atau lebih buruk daripada skema CG jika seseorang menyelidiki biaya komunikasi yang terlibat dalam keduanya. Maksud saya ini dalam arti praktis: tentu saja, orang mungkin harus mengkomunikasikan lebih sedikit data, tetapi saya akan membayangkan perbedaan waktu jam dinding untuk diabaikan oleh semua program operasi lain yang dilakukan pada data ini.
Tentu saja, saya akan senang jika ada yang mengambil tantangan untuk membuktikan saya salah!
sumber
Seperti halnya kebanyakan pernyataan umum tentang skema numerik, jawabannya tergantung pada keadaan yang Anda lihat. Pertama-tama, keuntungan dari DG tentang paralelisasi terutama terbayar dalam kasus skema integrasi waktu eksplisit karena
Sementara pernyataan-pernyataan ini berlaku untuk diskritisasi DG generik, aplikasi HPC nyata (katakanlah, menggunakan beberapa ribu prosesor) memerlukan beberapa upaya lebih lanjut mengenai strategi paralelisasi untuk mempertahankan skala yang baik. Makalah ini menunjukkan, misalnya, bagaimana seseorang dapat mencapai penskalaan yang hampir sempurna hingga satu sel per prosesor . Ini tentu saja sesuatu yang tidak dapat Anda harapkan dari FEM terus menerus, tetapi seperti yang disebutkan sebelumnya, skema implisit adalah hal yang sama sekali berbeda.
sumber
Ketika menyusun matriks kekakuan, data yang disimpan dalam elemen dalam FEM terus menerus (nodal) harus dikomunikasikan ke semua tetangga nodal. Sebaliknya, DGFEM membutuhkan data elemen untuk dikomunikasikan kepada semua tetangga tetangganya. Dalam 1D nodal dan wajah tetangga identik, tetapi dalam 3D perbedaannya bisa sangat besar: Untuk mesh hexahedral biasa, ada 26 tetangga nodal tetapi hanya 6 tetangga wajah. Untuk jerat tidak beraturan dengan banyak simpul valensi tinggi, situasinya menjadi lebih buruk untuk CG, sementara itu tetap sama untuk DG.
sumber
DG untuk PDE hiperbolik dapat digunakan sebagai pengganti skema volume terbatas. Dalam volume terbatas seperti pada perbedaan terbatas, ketika Anda meningkatkan urutan skema, stensil Anda meningkat. Ini membuat paralelisasi lebih sulit, karena untuk setiap urutan skema, Anda memiliki stensil yang berbeda. Pada batas-batas partisi, Anda harus memastikan bahwa semua sel yang diperlukan dari partisi tetangga untuk urutan skema tertentu tersedia. Tetapi dengan DG, tidak peduli apa urutan skema itu, setiap sel berkomunikasi hanya dengan tetangga-tetangganya. Jadi dibandingkan antara volume / perbedaan hingga dan DG, dapat dikatakan DG lebih mudah untuk diparalelkan.
sumber