Loading article…
数値解析における並列メッシュ生成は、計算幾何学と並列計算という2つの科学計算 分野 の境界にある新しい研究分野です。[1]並列メッシュ生成法は、元のメッシュ生成問題を小さなサブ問題に分解し、複数のプロセッサまたはスレッドを使用して並列に解決（メッシュ化）します。既存の並列メッシュ生成法は、2つの基本的な属性で分類できます。
- 個々のサブ問題をメッシュ化するために使用される順次手法と
- サブ問題間の結合度。
並列メッシュ生成における課題の 1 つは、既製の順次メッシュ コードを使用して並列メッシュ ソフトウェアを開発することです。
概要
並列メッシュ生成手順では、一般に、元の 2 次元 (2D) または 3 次元 (3D) メッシュ生成問題を N 個の小さなサブ問題に分解し、P 個のプロセッサまたはスレッドを使用して同時に解決 (メッシュ化) します。[1]サブ問題は、密結合、 [2] [3]部分的に結合[4] [5]または分離 [6] のいずれかに定式化できます。[7]サブ問題の結合によって、サブ問題間で必要な通信の強度と同期の量/タイプが決まります。
並列メッシュ生成方法の課題は、並列メッシャーの安定性を維持すること（つまり、最先端のシーケンシャル コードによって生成された有限要素の品質を保持すること）と、並列メッシャーのスケーラビリティを大幅に低下させることなく 100% のコード再利用を達成すること（つまり、継続的に進化し、完全に機能する既製のシーケンシャル メッシャーを活用すること）です。
並列メッシュ生成と並列三角測量には違いがあります。並列三角測量では、事前に定義された点のセットを使用して、点のセットの凸包をカバーする並列三角形を生成します。並列Delaunay 三角測量の非常に効率的なアルゴリズムは、Blelloch ら[8]に示されています。このアルゴリズムは、並列メッシュ生成のために Clemens と Walkington [9]によって拡張されています。
並列メッシュ生成ソフトウェア
多くのソルバーが並列マシンに移植されている一方で、グリッド ジェネレーターは取り残されています。メッシュ生成の前処理手順は、依然としてシミュレーション サイクルの連続的なボトルネックとなっています。そのため、安定した 3D 並列グリッド ジェネレーターの開発の必要性は十分に正当化されています。
Simmetrix Inc. [10]の MeshSim メッシュ ジェネレータの並列バージョンは、研究用と商用の両方で利用できます。このバージョンには、表面、ボリューム、境界層メッシュ生成の並列実装と並列メッシュ適応性が含まれています。このバージョンで使用されているアルゴリズムは、参考文献[4]のアルゴリズムに基づいており、スケーラブル (並列という意味でも、シリアル実装に比べて高速化という意味でも) で安定しています。マルチコアまたはマルチプロセッサ システムでは、これらのアルゴリズムのマルチスレッド バージョンも用意されており、ベース MeshSim 製品[11]で利用できます。
もう一つの並列メッシュジェネレーターはD3D [12]で、プラハのチェコ工科大学のダニエル・リプル[13]によって開発されました。D3Dは、 3D領域を並列（または順次）に離散化して混合メッシュを作成できるメッシュジェネレーターです。
BOXERMesh [14]は、Cambridge Flow Solutions [16]が開発した非構造化ハイブリッドメッシュジェネレーター[15]です。分散メモリの完全並列化ソフトウェアとして実装されており、エンジニアリングシミュレーションを制限する従来のボトルネックを克服するように特別に設計されており、任意の複雑さとサイズのジオメトリで高度なメッシュ生成を実現します。そのスケーラビリティは、HPCクラスターで生成された非常に大きなメッシュで実証されています。
並列メッシュ生成の課題
商用のシーケンシャル メッシュ生成ライブラリのアルゴリズムとソフトウェア インフラストラクチャの開発には、かなりの時間がかかります。さらに、品質、速度、機能の改善には終わりがないため、最先端の並列メッシュ生成コードを作成する作業は困難です。
並列メッシュ生成がすぐに大きなメリットをもたらす分野は、領域分割です。[17]で提示されたDD問題は、3Dジオメトリに対してはまだ未解決であり、その解決法は、ドロネー法とアドバンシングフロント法の既成のメッシュ生成コードに依存する安定したスケーラブルな方法を提供するのに役立ちます。
最後に、並列メッシュ生成への長期的な投資は、メッシュ生成における未解決の問題を抱える数学者の注目を集め、数学に幅広い影響を与えることです。
参照
参考文献
- ^ 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 の大学 Web ページ、http://mech.fsv.cvut.cz/~dr/
- ^ BOXERメッシュ
- ^ スケーラブルな並列メッシュ生成
- ^ ケンブリッジフローソリューション
- ^ Chrisochoides N.、「並列メッシュ生成方法の調査」、ブラウン大学、プロビデンス RI - 2005 年。