NEC

MathKeisanユーザーズガイド

METISおよびParMETIS

概要

METISは行列やグラフを分割したり、オーダリングしたりするためのライブラリです。METISは、Solverにおける行列分解処理でのfill-inを少なくするため、行列のオーダリングに使用されています。

ParMETISは、グラフ分割や疎行列のオーダリングのための様々なアルゴリズムを持つMPIベースの並列ライブラリです。

MathKeisanのParMETISは、 George KarypisとVipin Kumarが、University of MinnesotaとArmy HPC research centerで開発した、オリジナルのParMETIS version 3.1をベースにしています。

ユーザインタフェース

ユーザインタフェース情報は、いくつかの箇所に記載されています。

METISルーチン一覧

名称 説明
METIS_PartGraphRecursive multilevel recursive bisection によるメッシュの分割
METIS_PartGraphKway edge cut を最小にするための、multilevel k-way 分割によるメッシュ分割
METIS_PartGraphVKway 通信量を最小にするための、multilevel k-way 分割によるメッシュ分割
METIS_mCPartGraphRecursive edge cut を最小にするための、 multi-constraint multilevel recursive bisection によるメッシュ分割
METIS_mCPartGraphKway edge cut を最小にするための、multi-constraint multilevel k-way 分割によるメッシュ分割
METIS_WPartGraphRecursive prescribed partition weightsを用いるPartGraphRecursive
METIS_WPartGraphKway prescribed partition weightsを用いるPartGraphKway
METIS_WPartGraphVKway prescribed partition weightsを用いるPartGraphVKway
METIS_PartMeshNodal メッシュを節点グラフに変換後、METIS_PartGraphKwayを使用
METIS_PartMeshDual メッシュを双対グラフに変換後、METIS_PartGraphKwayを使用
METIS_EdgeND multilevel nested dissectionアルゴリズムによる、 疎行列のfill reducing orderingの計算。3次元有限要素の大規模行列にのみ使用。
METIS_NodeND multilevel nested dissectionアルゴリズムによる、 疎行列のfill reducing orderingの計算。一般的にMETIS_EdgeNDより好まれる。
METIS_NodeWND METIS_NodeWNDと同様の動作。ただし、本ルーチン呼び出し前に圧縮を行うことが前提。
METIS_MeshToNodal メッシュの節点グラフへの変換
METIS_MeshToDual メッシュの双対グラフへの変換
METIS_EstimateMemory 使用メモリ量の計算

ParMETISルーチン一覧

名称 説明
ParMETIS_PartKway multilevel k-way 分割アルゴリズムによる、p個のプロセッサでのグラフのp-way分割
ParMETIS_PartGeomKway 座標ベース分割とmultilevel k-way 分割アルゴリズムを併用した、p個のプロセッサでのグラフのp-way分割
ParMETIS_PartGeom 座標ベースの空間fill曲線を使った、p個のプロセッサでのグラフのp-way分割
ParMETIS_RepartLDiffusion  改良されたメッシュに対応するグラフの作業負荷の均衡化。局所的な負荷不均衡情報に基づく拡散法を使用。
ParMETIS_RepartGDiffusion 改良メッシュに対応するグラフの作業負荷の均衡化。全体的な負荷不均衡情報に基づく拡散法を使用。
ParMETIS_RepartRemap 改良メッシュに対応するグラフの作業負荷の均衡化。 新しいp分割をベースに、元の分割へ最適なマッピングを行うため、移行コストが最小限で済む。
ParMETIS_RepartMLRemap 改良メッシュに対応するグラフの作業負荷の均衡化。 最も疎なグラフの新しいp-way分割をベースに、元の分割へ最適なマッピングを行うため、移行コストが最小限。multilevel paradigmを使って改良している。
ParMETIS_RefineKway multilevel p-way改良アルゴリズムを使って、 p個のプロセッサでの既存のp-way分割の質を向上させる
ParMETIS_NodeND multilevel nested dissectionによる、 行列のfill-reducing orderingの計算

参考文献

  1. G. Karypis and V. Kumar. "METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices." Univ. MN., 1998.
  2. G. Karypis, K. Schloegel and V. Kumar. ParMETIS: Parallel Graph Partitioning and Sparse Matrix Ordering Library." Univ MN., 2003.
  3. METISHome Page