Apakah Galerkin terputus benar-benar lebih paralel dari Galerkin kontinu?

9

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.

Truman Ellis
sumber
1
Saya rasa tidak, tetapi mungkin menambah pertanyaan jika Anda menautkan atau menjelaskan beberapa alasan yang seharusnya.
Bill Barth

Jawaban:

9

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.

Andrew Winters
sumber
8

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!

Wolfgang Bangerth
sumber
5

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

  • Matriks massa sel-lokal skema DG (jadi Anda tidak harus menerapkan kebalikan dari matriks massa secara global)
  • Rasio yang menguntungkan antara pekerjaan CPU-lokal (integral volume) dengan pekerjaan terkait komunikasi (integral tepi), terutama untuk pesanan yang lebih tinggi

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.

bigge
sumber
1

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.

gokturk
sumber
Benar, tetapi apakah yang Anda katakan tentang masalah praktis ? Dengan kata lain, jika Anda mengukur waktu untuk mengkomunikasikan elemen-elemen ini dalam program FEM nyata dan membandingkannya dengan waktu yang diperlukan untuk menghitung entri matriks, apakah itu penting?
Wolfgang Bangerth
1

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.

cfdlab
sumber