数値解析における並列メッシュ生成は、計算幾何学と並列計算という2つの科学計算 分野 の境界をまたぐ新たな研究分野です。[1]並列メッシュ生成手法は、元のメッシュ生成問題をより小さな部分問題に分解し、複数のプロセッサまたはスレッドを用いて並列に解く（メッシュ化する）手法です。既存の並列メッシュ生成手法は、以下の2つの基本的な属性によって分類できます。
- 個々のサブ問題をメッシュ化するために使用される順次手法と
- サブ問題間の結合度。
並列メッシュ生成における課題の 1 つは、既製のシーケンシャル メッシュ コードを使用して並列メッシュ ソフトウェアを開発することです。
概要
並列メッシュ生成手順では、一般的に、元の2次元(2D)または3次元(3D)メッシュ生成問題をN個の小さなサブ問題に分解し、P個のプロセッサまたはスレッドを使用して同時に解決(メッシュ化)します。[1]サブ問題は、密結合、 [2] [3]部分結合[4] [5]または分離[6] のいずれかに定式化できます。 [ 7]サブ問題の結合によって、サブ問題間で必要な通信の強度と同期の量/タイプが決まります。
並列メッシュ生成方法の課題は、並列メッシャーの安定性を維持すること（つまり、最先端のシーケンシャル コードによって生成された有限要素の品質を保持すること）と、同時に並列メッシャーのスケーラビリティを大幅に低下させることなく 100% のコード再利用を実現すること（つまり、継続的に進化し、完全に機能する既製のシーケンシャル メッシャーを活用すること）です。
並列メッシュ生成と並列三角測量には違いがあります。並列三角測量では、事前に定義された点群を用いて、点群の凸包を覆う並列三角形を生成します。並列ドロネー三角測量のための非常に効率的なアルゴリズムがBlellochら[8]によって提案されています。このアルゴリズムはClemensとWalkington [9]によって並列メッシュ生成用に拡張されています。
並列メッシュ生成ソフトウェア
多くのソルバーが並列マシンに移植されている一方で、グリッドジェネレータは依然として時代遅れとなっています。メッシュ生成の前処理ステップは、依然としてシミュレーションサイクルにおけるボトルネックとなっています。だからこそ、安定した3D並列グリッドジェネレータの開発が不可欠となっています。
Simmetrix社製のMeshSimメッシュ生成器の並列版[10]は、研究用途と商用用途の両方で利用可能です。この並列版には、表面、体積、境界層メッシュ生成の並列実装と、並列メッシュ適応機能が含まれています。このアルゴリズムは参考文献[4]のアルゴリズムに基づいており、スケーラブル（並列という意味でも、シリアル実装に比べて高速化という意味でも）で安定しています。マルチコアまたはマルチプロセッサシステム向けには、これらのアルゴリズムのマルチスレッド版も提供されており、MeshSimの基本製品[11]で利用可能です。
もう一つの並列メッシュ生成器はD3D [12]で、プラハのチェコ工科大学のダニエル・リプル[13]によって開発されました。D3Dは3D領域を並列（または順次）に混合メッシュに離散化できるメッシュ生成器です。
BOXERMesh [14]は、Cambridge Flow Solutions [16 ] によって開発された非構造ハイブリッドメッシュ生成ツール[15]です。分散メモリ型の完全並列化ソフトウェアとして実装されており、エンジニアリングシミュレーションを制約する従来のボトルネックを克服するように特別に設計されており、任意の複雑度とサイズの形状に対して高度なメッシュ生成を実現します。そのスケーラビリティは、HPC クラスター上で生成された非常に大規模なメッシュで実証されています。
並列メッシュ生成における課題
商用のシーケンシャルメッシュ生成ライブラリのアルゴリズムとソフトウェア基盤の開発には、かなりの時間がかかります。さらに、品質、速度、機能面での改善には限界があるため、最先端の並列メッシュ生成コードの開発は困難を極めています。
並列メッシュ生成が直ちに大きなメリットをもたらす分野は、領域分割です。[17]で提示されたDD問題は3次元形状に対して未解決であり、その解決法は、ドロネー法やアドバンシング・フロント法といった既成のメッシュ生成コードを用いた、安定的かつスケーラブルな手法の実現に役立つでしょう。
最後に、並列メッシュ生成への長期的な投資は、メッシュ生成における未解決の問題を抱える数学者の注目を集め、数学に幅広い影響を与えることです。
参照
参考文献
- ^ ab Nikos Chrisochoides、「並列メッシュ生成」、並列コンピュータ上の偏微分方程式の数値解法の章、（編者Are Magnus Bruaset、Aslak Tveito）、Springer-Verlag、pp 237-259、2005年。
- ^ Nikos ChrisochoidesとDemian Nave. 並列Delaunayメッシュ生成カーネル. Int. J. Numer. Meth. Engng., 58:161--176, 2003
- ^ Lohner, J. Camberos, M. Marshal. 並列非構造化グリッド生成.スケーラブル・マルチプロセッサにおける非構造化科学計算の章. (編者 Piyush Mehrotra および Joel Saltz)、pp 31--64、MIT Press、1990年。
- ^ ab H. de CougnyとM.Shephard. 面削除と階層的再分割を用いた並列ボリュームメッシュ生成. Comp. Meth. Appl. Mech. Engng., 174(3-4):275--298, 1999.
- ^ Andrey ChernikovとNikos Chrisochoides. 並列品質保証平面Delaunayメッシュリファインメントと同時ポイント挿入. SIAM Journal for Scientific Computing , Vol. 28, No. 5, pp 1907-1926, 2006.
- ^ J. Galtier、PL George. サブドメインを並列メッシュ化する方法としての事前分割. 非構造化メッシュ生成の動向に関する特別シンポジウム、pp 107--122. ASME/ASCE/SES、1997年。
- ^ Leonidas Linardakis、Nikos Chrisochoides. Delaunay分離法による並列品質保証平面メッシュ生成. SIAM Journal for Scientific Computing , Vol. 27, No. 4, pp 1394-1423, 2006.
- ^ GE Blelloch、JC Hardwick、G.~L. Miller、およびD. Talmor、「実用的な並列Delaunayアルゴリズムの設計と実装」、Algorithmica、24 (1999)、pp. 243--269。
- ^ Clemens Kadow、Noel Walkington. 投影ベースの並列Delaunayメッシュ生成およびリファインメントアルゴリズムの設計。2003年の第4回非構造メッシュ生成の動向に関するシンポジウムの議事録。
- ^ “Parallel MeshSim”. 2009年2月18日時点のオリジナルよりアーカイブ。2009年8月5日閲覧。
- ^ “MeshSim”. 2009年9月27日時点のオリジナルよりアーカイブ。2009年8月5日閲覧。
- ^ D3D メッシュジェネレーターの Web ページ
- ^ Daniel Rypl の大学ウェブページ、http://mech.fsv.cvut.cz/~dr/
- ^ ボクサーメッシュ
- ^ スケーラブルな並列メッシュ生成
- ^ ケンブリッジフローソリューションズ
- ^ Chrisochoides N.、「並列メッシュ生成方法の調査」、ブラウン大学、プロビデンス RI - 2005 年。
