並列計算のための非構造格子の領域分割
Phil Ridley, Numerical Algorithms Group Ltd,
April 17, 2010
概要
非構造格子は有限要素法や有限体積法においてよく用いられています。有限差分法によく適用される構造格子とは違い、非構造格子は、任意の頂点が如何に個々の要素を形作るかを特定する結合情報のリストを必要とします。分散メモリーコンピューターシステムで非構造格子の数値計算による分割を実装するには、最初の格子分割に特別な注意が必要です。
このCSEレポートは、非構造格子の分割処理について議論します。最初に、グラフ分割によるアルゴリズムの概要を示し、このアルゴリズムを用いる最も一般的に利用されているアプリケーションMETISとScotchを紹介します。さらにこれらがHECToRプロジェクトでどのように実装利用されるかを、クイックスタートガイドとして利用できるように説明します。最後に、有限体積法コードCABARETでの利用を目的として、非構造格子へ適用することにより、これら2つのパッケージによる分割の有効性を比較検証します。
もくじ
- 1. はじめに
- 1.1 背景
- 1.2 構造格子と非構造格子
- 1.3 非構造格子
- 2. 分散コンピュータでのグリッド分割
- 2.1 非構造格子のグラフ表現形式
- 2.2 デュアル・グラフ形式
- 2.3 グラフ分割問題
- 2.4 分割探索アルゴリズム
- 3. METIS：グラフ分割の例
- 3.1 背景
- 3.2 HECToRでのコンパイル
- 3.3 非構造格子の分割
- 4. Scotchを用いた非構造格子の分割
- 4.1 背景
- 4.2 HECToRでのコンパイル
- 4.3 非構造格子の分割
- 5. METISとScotchの比較
- 5.1 アウトライン
- 5.2 CABARET
- 6. 結論
1. はじめに
1.1 背景
例えばCFDや構造解析のような有限要素法や有限体積法に基礎を置く科学技術計算コードは、その背景となる数値的な領域分割に非構造格子が多用されています。また、非構造格子は構造格子と違い、グリッドやメッシュの構成方法を特定する結合情報も必要になります。このことは、そのアルゴリズムは構造格子の場合のようにメニーコアマシンでの効率が出ないとまでは言えませんが、性能を上げるにはさらに多くの労力が必要になると言えるでしょう。計算機科学的な考察においては、これは間接アドレッシング、 非連続メモリーアクセスおよびプロセス間の最適化から生じるデータ操作の効率に対する付加的なオーバーヘッドを含んでいます。最適なプロセス間通信のために必要となる効率的な領域分割アルゴリズム、それが本レポートの主題です。
高度に非構造化されたグラフの効率的な分割を見つけ出すアルゴリズムは、分散メモリー並列コンピュータを用いた多くの応用分野における幅広い問題を解く場合、極めて重要です。例えば、有限要素法に基づく大規模シミュレーションは、その有限要素メッシュを個々のプロセッサーへ割り当てることが要求されるでしょう。この要素分散では、各プロセッサーに割り当てられた要素数はほぼ一定にすべきであり、また、異なるプロセッサーに割り当てられた隣接要素の数は、できる限り小さくしなくてはなりません。最初の条件は、プロセッサー間の計算量の負荷をバランスすることで達成されます。二番目の条件は、隣接要素を異なるプロセッサーへ配置することによる、その通信の最小化を保証するものです。グラフ分割のプロセス[1]は、最初に有限要素を一つのグラフへ変換し、次に最適な方法でこれを分割することで、これらの条件を満足させることが出来ます。
1.2 構造格子と非構造格子
構造化メッシュあるいはグリッドの全ての内部頂点は、同数の隣接要素を持ちます。構造メッシュは通常は、全て四面体(2D)あるいは六面体(3D)です。このようなメッシュを作成するアルゴリズムは、境界や特定の領域に要素を並べるために、繰り返し平滑化を行う複雑な方法です。さらに重要なことは、グリッド内の各セル(要素)は2次元では一つのインデックス(I;j)、3次元では(I;j;k)で指定でき、各頂点の座標は、格子間隔を表す実数dx,dy,dzを用いて、2次元では(i・dx;j・dy)、3次元では(i・dx;j・dy;k・dz)で表すことが出来ることです。
非構造メッシュは、全ての内部頂点は同じ数の隣接要素を持つ必要はないため、一つの頂点に接する要素数は様々です。非構造メッシュとしては、三角(2D)と四面体(3D)メッシュが最も広く利用されていますが、四面体や六面体でも可能です。構造メッシュ／グリッドとは異なり、各セルは一つのインデックスでは指定できず、その代わりに基底関数としてよく知られている区分多項式内挿関数の組が用いられます。さらに、与えられた頂点の組を個々の要素に割当てる方法を指定する結合情報リストが必要となります。
世の中には、構造メッシュと非構造メッシュを扱う市販およびフリーのソフトウェアが多く存在し、これは「グリッド生成」と一般には呼ばれます。本レポートでは直接これらのパッケージを利用はしませんが、これらパッケージの出力結果には注目する必要があります。なぜなら、これら自身が非構造格子手法を用いるアプリケーションの入力そのものになるからです。
1.3 非構造格子
非構造格子の数値的な領域分割を用いる、いかなるアプリケーションコードも、そのメッシュやグリッドのトポロジーを記述する入力フォームを要求します。このデータは常にNVERT個の頂点に関する一つのリストで構成されます。ここで、各Vi,i=1::NVERTは、2あるいは3次元空間座標内の頂点座標とします。さらにそれは、実際のグリッドからこれら頂点をどのように構成するかを記述する、セルあるいは要素の結合情報リストの形になるでしょう。このようなリストはNCELL個のセル(あるいは要素)を含みます。ここで各セルは、例えば四面体ではN=4、六面体ではN=8となる、セルが含む頂点数Nを持ちます。通常NVERTとNCELLは、データを読み込む前に動的に配列を用意することから、非構造グリッドデータが格納される全てのデータファイルの先頭に置かれます。
非構造グリッドコードはシリアル版の場合は、全メッシュトポロジーへ直接にメモリーアクセスしますが、分散メモリー版でのSPMD方式では、各プロセスは自身の受け持つメッシュセクション(例えば領域)のローカルコピーへアクセスします。その通信の全影響を考慮するためには、その領域の周辺部に関してもまた実装されなくてはなりません。ソフトウェア開発上で考慮しなくてはいけない最も重要な2つのこととして、まず第一に、個々の頂点各々のローカルからグローバルへの参照関係を追跡することが必要です。第二に、最初の効率的なメッシュ分割です。第一の観点から行うべきはノード内の(プロセス内の)最適化で、第二点は問題全体の負荷バランスの最適化です。
2. 分散コンピュータでのグリッド分割
2.1 非構造格子のグラフ表現形式
広く利用される市販ベースでない領域分割パッケージには、Chaco [3]、Jostle [4]、METIS [5]、Scotch [6]があります。これらは全て、入力メッシュの表現にデュアルグラフ形式を要求します。しかしながらMETISは、トポロジー記述から非構造グリッドを処理する機能が備わっています。この機能は、メッシュをデュアルグラフへ変換するのに大変都合が良いものです。
非構造グリッドのデュアルグラフ形式は、オプション次第で各頂点あるいは各セル(要素)の結合情報をリストすることが出来ます。こうして、頂点あるいは要素のどちらでもデュアルグラフを計算することが出来ます。並列計算の観点から、これら要素(セル)のデュアルグラフを扱うことにします。何故なら、グリッドセルの領域分割の方が、頂点による領域分割よりも負荷バランスがとりやすいからです。
グリッドセルに基づく非構造グリッドのデュアルグラフは、そのエントリーが個々のセルi=1::NCELL毎のその近隣セルをリストした、長さNCELLの単純なリストです。よって各エントリーは、最大N個の近隣セルを持つことが出来ます。ここでNは、個々の要素の辺の数で、例えば四面体であればN=4、六面体であればN=8です。元のメッシュのセルに関するデュアルグラフの考え方を描写するために、図1で示すような簡単な有限要素を考えてみましょう。ここで、３つの直三角有限要素と、そのメッシュを形成する全部で5つの頂点があります。対応するセルに関するデュアルグラフを図2と表形式で示します。
図１
| 3 | 2 | |
| 1 | 2 | 3 |
| 2 | 1 | |
| 3 | 1 |
図２
2.2 デュアル・グラフ形式
第一行目は、デュアルグラフ内の頂点数Vと同じである、元のメッシュの要素数(NCELL)と、次にエッジ数Eが記されます。続く行は、各頂点エントリーで、その近隣頂点のリストが与えられています。この形式はChaco、Jostle、METISで採用されていますが、Scotchは多少異なりますが、後に紹介します。
2.3 グラフ分割問題
これら領域分割パッケージは、双対再帰的二分割(dual recursive bipartitioning)法[7]あるいはマルチレベル法[8,9]のどちらか一方の方法で対処しています。マルチレベル法は実際には、より一般的な双対再帰的二分割法の特殊なケースです。特にScotchは一般的な双対再帰的二分割法を採用しています。
2.4 分割探索アルゴリズム
双対再帰的二分割法は、セル(デュアルグラフの頂点V)を各領域へ再帰的に配置するのに分割統治アルゴリズムを用いています。そのアルゴリズムはステップ毎に、対象の領域を連結しないサブ領域へ分割し、これら2つの領域へ頂点を配置する二分割ルーチンを呼び出します。専用の二分割ルーチンが、コスト関数により頂点配置を最適化します。個別のアルゴリズム(マルチレベル法もその一つです)の選択に関するオプションがあり、コスト関数は対象とする分散処理システムの通信量を表現できるものでなくてはなりません。
マルチレベル法あるいはk分割グラフ問題(GPP)は最初に、（重み付き）頂点集合Vと（重み付き）エッジ集合Eと共にグラフG(V,E)を作成し、Vを、各集合が同じ頂点重みを持ちかつ、例えば領域で分割されたエッジ重みの総量としての分割重みが最小になるように、頂点をk個の非連結集合へ分割します。GPP問題は、最小化されるべき目的関数として分割重みを用い、頂点重みを制約条件としてバランスさせる、組合せ最適化問題として通常扱われます。しかしながら、領域の品質を高めるために、通常はこの制約は緩めて用いられます。
3. METIS：グラフ分割の例
3.1 背景
METISの最新バージョンは（本レポート作成時点において）4.0.1であり、[5]から入手できます。このパッケージは、ミネソタ大学と空軍HPC研究センターとクレイ・リサーチ社が共同開発しました。関連する論文には[5],[6]があります。
METISはグラフ分割と有限要素メッシュ作成のシリアルプログラム群です。METISに実装されているアルゴリズムは、マルチレベル再帰的バイセクション、マルチレベルk分割、および多重制約領域分割スキームに基づいています。このマルチレベル法は、元のグラフサイズを縮小して分割を行い、その後最終的に元のグラフの領域を求めていきます。METISは領域分割ソフトとしてスタンドアロン・ソフトとして利用できますが、METISライブラリをFORTRANまたはC言語プログラムから呼び出して利用も可能です。
ParMETISはMITISを機能拡張するMPIベースの並列ライブラリです。大規模並列数値計算シミュレーションに特別に用意されたルーチンを含み、追加のグラフ生成ソフトを必要とせずに、大規模メッシュの高品質な領域分割が可能です。METISとParMETISは共に、並列分散アプリケーションで利用できますが、本レポートの目的から、ここではシリアル動作のMETISのみを考えます。そこから得られた領域は、CFDでの問題を非構造格子アプローチで解くアプリケーションのための、並列領域分割に用いられます。
METISは、[5]で示された条件に従い、市販あるいは市販でない場合の両方の目的で配布可能です。配布あるいはアプリケーションにMETISを付随させる場合、metis@cs.umn.eduへ許可を求める必要があります。
3.2 HECToRでのコンパイル
最初にMETISを[11]からwgetでダウンロードします。この作業はユーザ用作業ディレクトリで行い、下記tarコマンドを用いると便利です。
tar -zxvf metis-4.0.tar.gz
Makefileには、~/metis-4.0ディレクトリにオブジェクトが生成されることになっています。Makeをする前に、このコードは自前のlog2関数を定義していることに注意します（C99標準に備わっているものです）。よってコンパイルには-c89を指定しなくてはなりません。ここで、~/metis-4.0/ Makefile.in内でCOPTIONS=-c89を指定しましょう。そしてmakeコマンドでコンパイルします。 METISパッケージのディレクトリ構造は以下の通りです：
| ・ Doc | - | METISユーザマニュアル |
| ・ Graphs | - | METISで利用可能な小規模グラフとメッシュのサンプル |
| ・ Lib | - | METISのライブラリコード |
| ・ Programs | - | METISのスタンドアロンプログラム |
| ・ Test | - | METISの領域分割ルーチンの包括的なテストデータ |
本レポートでは、mesh2dual、kmetis、partdmesh、およびMETIS library - libmetis.aのみに焦点を当てます。これらは全て、metis-4.0ディレクトリ直下にあります。
3.3 非構造格子の分割
METISの領域分割のデモンストレーションの例として、以下の非構造格子を考えましょう。この例において元のグリッドから128のメッシュを効率的に分割することを考えます。以下の六面体メッシュファイル(hexcells.mesh)の最初の数行を見ると、そのファイルの最初の行にセル(有限要素)数、続いて要素タイプが記載されています。タイプの値は、1,2,3,4に対してそれぞれ、三角、四面体、六面体、四角形要素を示します。この例の対応は六面体で、このファイルの残りの100000行は、各行8つの頂点で構成されます。
| 100000 | 3 | ||||||
| 321 | 112 | 113 | 650 | 15961 | 5363 | 16133 | 22812 |
| 15961 | 5363 | 16133 | 22812 | 15762 | 5364 | 16124 | 27493 |
| 15762 | 5364 | 16124 | 27493 | 15563 | 5365 | 16115 | 32174 |
| 15563 | 5365 | 16115 | 32174 | 15364 | 5366 | 16106 | 36855 |
| 15364 | 5366 | 16106 | 36855 | 15165 | 5367 | 16097 | 41536 |
| 15165 | 5367 | 16097 | 41536 | 14966 | 5368 | 16088 | 46217 |
| ... |
この形式は、partmeshコマンドでMETISに領域を作成させる入力形式そのものです。このアプリケーションは、領域を計算する前にメッシュをデュアルグラフへ変換するので、最初にmesh2dualコマンドを用いたほうが便利です。これは毎回デュアルグラフを生成保存して異なるサイズの幾つかの領域を生成したい場合に特に便利です。METISのmesh2dualとkmetisは、hexcells.mesh.dgraph.part.128の元のメッシュに対して128の領域を生成するのに用いることが出来ます。
>./mesh2dual hexcells.mesh
**********************************************************************
METIS 4.0.1 Copyright 1998, Regents of the University of Minnesota
Mesh Information ----------------------------------------------------
Name: hexcells.mesh, #Elements: 100000, #Nodes: 111741, Etype: HEX
Forming Dual Graph... -----------------------------------------------
Dual Information: #Vertices: 100000, #Edges: 288600
Timing Information --------------------------------------------------
I/O: 0.230
Dual Creation: 0.060
**********************************************************************
>./kmetis hexcells.mesh.dgraph 128
**********************************************************************
METIS 4.0.1 Copyright 1998, Regents of the University of Minnesota
Graph Information ---------------------------------------------------
Name: hexcells.mesh.dgraph, #Vertices: 100000, #Edges: 288600, #Parts: 128
K-way Partitioning... -----------------------------------------------
128-way Edge-Cut: 25959, Balance: 1.03
Timing Information --------------------------------------------------
I/O: 0.050
Partitioning: 0.190 (KMETIS time)
Total: 0.240
**********************************************************************
この結果はpartdmeshを用いても可能で、以下のようにhexcells.mesh.dgraph.part.128と同等な出力ファイルhexcells.mesh.epart.128を生成します。
> ./partdmesh hexcells.mesh 128
**********************************************************************
METIS 4.0.1 Copyright 1998, Regents of the University of Minnesota
Mesh Information ----------------------------------------------------
Name: hexcells.mesh, #Elements: 100000, #Nodes: 111741, Etype: HEX
Partitioning Dual Graph... ------------------------------------------
128-way Edge-Cut: 25959, Balance: 1.03
Timing Information --------------------------------------------------
I/O: 0.160
Partitioning: 0.270
**********************************************************************
ファイルhexcells.mapの内容には、総セル数に対応する0~127の領域番号が含まれます。このセクションでは、スタンドアロンのMETISアプリケーションであるmesh2dual、kmetis、partdmeshをデモンストレーションしましたが、ユーザー自身のFortranやCコードへMETISライブラリをリンクすることも可能です。また、自動分割のためのサブルーチンMETIS PartGraphKway、 METIS MeshToDual、METIS PartMeshDualを用いる事も出来ます。
4. Scotchを用いた非構造格子の分割
4.1 背景
Scotchパッケージの最新版は（本レポート作成時では）5.1.7で、[7]からダウンロードできます。Scotchはボルドー大学情報学研究所LaBRIで開発され、現在はINRIA ボルドー南西研究センターのScAlApplixeプロジェクト内で開発されています。
デュアル再帰的二分割(DRB)マッピングアルゴリズムは、分割統治アプローチに基ずく、幾つかの発見論的グラフ二分割法を用いており、全てScotchパッケージに実装されています。最近になって、ハイパーグラフ分割アルゴリズムの応用により、Scotchの順序付け機能は元のメッシュ構造へ拡張されました。Scotchの並列実装がPT-Scotch(Parallel Threaded Scotch)です。両方のコードは大部分を共有しており、操作するサブグラフが単一プロセッサに割当てられたときは、PT-ScotchはScotchライブラリのシリアル動作ルーチンへ制御を移行します。ScotchとPT-Scotchは並列分散計算アプリケーションで用いられるグリッド分割に極めて有用です。本レポートの目的のために、領域分割にシリアル動作のScotchを用い、その結果を例題としてCFDアプリケーションコードのための、並列領域分割に用います。
Scotchはデュアルライセンスベースで利用可能です。ライブラリとして利用か、あるいは新規の領域分割や順序付け手法開発のためのテストベッドとして寄与するために利用したいと考える全ての人々に対して、フリーソフトとしてScotchのWebぺーじからダウンロード可能です。また例えば商用ソフトへ組み込むなど、別のライセンス条件形態としても入手可能です。Scotchのフリーソフトウェアライセンスは、CeCILL-Cライセンス[12]で、基本的にはGNU LGPLと同等です：フリーのあるいは商用ソフトへのライブラリとしてコードをリンクしたり、コードを改変したり、あるいは改変済みコードの再配布が可能です。バージョン4.0はLGPLライセンスで配布されています。
4.2 HECToRでのコンパイル
最初にScotchを[13]からwgetでダウンロードします。ユーザ作業用ディレクトリで行い、パッケージを展開することをお勧めします。
tar -zxvf scotch_5.1.7.tar.gz
マシン依存のコンパイルオプションをMakefile.incに設定して、Makefileを用いてオブジェクトコードを作成します。ここで、
cd ~/scotch_5.1/src/
とすると、CrayXT用のMakefile.incがすでにあるので、コンパイルする前に下記のようにコピーをしておきましょう。、
cp Make.inc/Makefile.inc.x86-64\_cray-xt4\_linux2} ./Makefile.inc
make
下記のように実行形式が出来ていることを確認します。
ls ~/scotch_5.1/bin/
下記のようファイルが存在すれば、Scotchのコンパイルは完了です。
acpl amk_fft2 amk_hy amk_p2 gbase gmap gmk_m2 gmk_msh gmtst ...
4.3 非構造格子の分割
ここでMETISの例で扱った同じ非構造格子の分割を考えましょう。Scotchはユーザのメッシュを直接読み込む機能がないので、最初に下記のような形式から、Scotchが必要なデュアルグラフ形式へメッシュを変換します。下記の非構造六面体メッシュファイル(hexcells.mesh)の最初の数行を見ると、ファイルの先頭行に、セル(有限要素)と要素タイプが記載されています。タイプの値は、1,2,3,4に対してそれぞれ、三角、四面体、六面体、四角形要素を示します。この例の対応は六面体で、このファイルの残りの100000行は、各行8つの頂点で構成されます。
| 100000 | 3 | ||||||
| 321 | 112 | 113 | 650 | 15961 | 5363 | 16133 | 22812 |
| 15961 | 5363 | 16133 | 22812 | 15762 | 5364 | 16124 | 27493 |
| 15762 | 5364 | 16124 | 27493 | 15563 | 5365 | 16115 | 32174 |
| 15563 | 5365 | 16115 | 32174 | 15364 | 5366 | 16106 | 36855 |
| 15364 | 5366 | 16106 | 36855 | 15165 | 5367 | 16097 | 41536 |
| 15165 | 5367 | 16097 | 41536 | 14966 | 5368 | 16088 | 46217 |
| ... |
Scotchを使ってこのメッシュを分割する前に、デュアルグラフ形式へ変換する必要があります。これはMETISのmesh2dualを使えば簡単です。METISの実行形式を用いて次のコマンドを用います。
mesh2dual hexcells.mesh
こうして、出力ファイルとしてhexcells.mesh.dgraphが生成されます。
| 100000 | 288600 | ||
| 21 | 4001 | 2 | |
| 1 | 22 | 4002 | 3 |
| 2 | 23 | 4003 | 4 |
| 3 | 24 | 4004 | 5 |
| 4 | 25 | 4005 | 6 |
| 5 | 26 | 4006 | 7 |
| 6 | 27 | 4007 | 8 |
| 7 | 28 | 4008 | 9 |
| 8 | 29 | 4009 | 10 |
| 9 | 30 | 4010 | 11 |
| ... |
しかしながらこれはScotchが必要なものではありません。各行の先頭に各近隣セルの数を出力するために、METISとmesh2dualを再コンパイルする必要があります。これには、WriteGraph関数のmetis-4.0/Programs/io.cが必要なファイルです。以下のコード断片は、要素番号も1からではなく0からにした修正バージョンです。
void WriteGraph(char *filename, int nvtxs, idxtype *xadj, idxtype *adjncy)
{
int i, j;
FILE *fpout;
if ((fpout = fopen(filename, "w")) == NULL) {
printf("Failed to open file %s\n", filename);
exit(0);
}
/* fprintf(fpout, "%d %d", nvtxs, xadj[nvtxs]/2);*/
fprintf(fpout, "%d %d", nvtxs, xadj[nvtxs]);
for (i=0; i<nvtxs; i++) {
fprintf(fpout, "\n");
fprintf(fpout, "%d ",xadj[i+1]-xadj[i]);
for (j=xadj[i]; j<xadj[i+1]; j++)
fprintf(fpout, "%d ", adjncy[j]);
/* fprintf(fpout, " %d", adjncy[j]+1); */
}
fclose(fpout);
}
metis-4.0/Programs/io.cを上述のように修正して再度コンパイルしてやり直します
mesh2dual hexcells.mesh
出力ファイルhexcells.mesh.dgraphは次のようになります
| 100000 | 577200 | |||
| 3 | 20 | 4000 | 1 | |
| 4 | 0 | 21 | 4001 | 2 |
| 4 | 1 | 22 | 4002 | 3 |
| 4 | 2 | 23 | 4003 | 4 |
| 4 | 3 | 24 | 4004 | 5 |
| 4 | 4 | 25 | 4005 | 6 |
| 4 | 5 | 26 | 4006 | 7 |
| 4 | 6 | 27 | 4007 | 8 |
| 4 | 7 | 28 | 4008 | 9 |
| 4 | 8 | 29 | 4009 | 10 |
| ... |
これでもまだScotchには十分でなく、以下のような修正が必要です。最初にこのファイルをhexcells.grfへコピーするリネームします。そしてこのファイルの最初の行を以下のように変更します。
| 0 | ||||
| 100000 | 577200 | |||
| 3 | 20 | 4000 | 1 | |
| 4 | 0 | 21 | 4001 | 2 |
| 4 | 1 | 22 | 4002 | 3 |
| 4 | 2 | 23 | 4003 | 4 |
| 4 | 3 | 24 | 4004 | 5 |
| ... |
ファイルhexcells.grfはこれでScotchを実行できます。このScotchの.grfを再度確認して、実行形式gtstを以下のように実行します
> bin/gtst grf/hexcells.grf
S Vertex nbr=100000
S Vertex load min=1 max=1 sum=100000 avg=1 dlt=0
S Vertex degree min=3 max=6 sum=577200 avg=5.772 dlt=0.358279
S Edge nbr=288600
S Edge load min=1 max=1 sum=288600 avg=1 dlt=0
元の六面体メッシュの分割を行うためには、次のコマンドでメッシュに対して128の領域を作成し、ファイルhexcells.mapへ出力します。これはMETISの出力であるhexcells.mesh.epart.128やhexcells.mesh.dgraph.part.128と同等のものです。
> echo cmplt 128 | bin/gmap grf/hexcells.grf - grf/hexcells.map
これでhexcells.mapの内容には、セル総数(例えば100000)およびセル番号とその対応する0〜127の領域番号が含まれます。このセクションでは、スタンドアロンのScotchアプリケーションgtstとgmapを用いましたが、ユーザ自身のFortran(あるいはC)コードへScotchライブラリをリンクすることも、サブルーチンとしてSCOTCH_graphCheckやSCOTCH_graphMapを使うことも可能です。
5. METISとScotchの比較
5.1 アウトライン
このセクションでは、非構造格子CFDアプリケーションであるFortran90/MPIコード「CABARET」を対象とした、METISとScotchの実際の応用を比較します。METISとScotchを用いて生成したメッシュ分割と、通常の(例えば連続の)有限要素順序においても同様に、CABARETの性能を比較しました。このセクションの残りでは、これらの結果を示します。
図3：4万ステップ時における流れ場のx方向速度成分
5.2 CABARET
乱流構造を正確に解像するには、高信頼性CFDシミュレーションを数百万格子で解く必要があります。Compact Accurately Boundary Adjusting high-Resolution Technique (CABARET)は、従来の高解像度スキームに比べ少なくとも10倍の効率で、正確な結果を生成することが出来ます。CABARET[14]は、局所的に二次の有限差分スキームを基礎にしており、これは分散メモリー並列計算システムとの相性が極めて良い手法です。レイノルズ数が104、マッハ数が0.05程度の低い場合に、CABARETは追加のプレコンディショナーを必要とせずに急速に収束します。
このセクションでは、異なる領域分割手法における、HECToRでの非構造6面体メッシュのCABARETコードの性能を評価します。256コアまでのコードの性能を、METISとScotchという領域分割アプリケーションで生成されたグリッドに対して、負荷バランスとの関連性について議論します。
CABARETコードは3つの計算フェーズを持ち、これらは通信にピュアMPIを使用しています。そのスキームの各繰り返しにおいて、3つの最近接通信タイプと一つのグローバルな通信all_reduceを持ちます。計算対象グリッドは8頂点(例えば線形の)六面体有限要素で構成されます。その並列分割は、離散化スキームにおいて生じるであろう特異性を回避するように要求されます。
テストケースのデモンストレーションのために、100000有限要素の固定グリッドを用いた3D後方ステップ周りの乱流を考えましょう。結果は276回の繰り返し計算となり、I/Oを除いた時間を計測しました。
図3は40000時間ステップにおける流れ場の正規化されたx方向速度成分を示し、図4は方法の正確性を表し、100000ステップ後の再循環領域周りの正確に解像されたストリームラインが示されています。
METISとScotchが生成した領域の有効性を比較するために、HECToRフェーズ2a.Aのクアッドコアノードを用いて、32,64,128,256コアについてテストを行いました。テストにおいては、100000六面体有限要素の固定グリッドが分割され、並列CABARETコードで使用可能な分散されたメッシュを生成することとします。ここでMETISとScotchおよび連続領域分割を用いました。METISとScotchの領域分割は本レポートの先に述べた方法を用いて実行されました。
図4：100000ステップ後の再循環領域周りのストリームライン
図5：CABARETの256時間ステップの実行時間
図6：128領域のセル数
連続領域分割はグリッドサイズを単純に分けることで実施しました。例えば、100000をコア数pで割った数で分ければ、最初の1,2,・・・,100000/pをプロセッサー1へ、次に(100000/p + 1),・・・, 2(100000/p)をプロセッサー２へ、等として、余りrはプロセッサーに一つづつ分ける等とします。この方法は通信に関して最適化を考慮せず、最初のメッシュ生成からの要素順序付けの効率のみに依存します。連続領域分割法では、各プロセスに連続した番号を持つ要素を割当てられて、グリッド内の離れた領域に属する要素が同じプロセスに割当てられるため、特に高い性能は期待できないでしょう。
領域分割に異なる手法を用いたCABARETコードの256時間ステップの計測時間を図5に示します。各線は32,64,128,256コアに対するMETIS,Scotch,連続領域分割を示します。全てのケースにおいてScotchがMETISに比べて経過時間で約3%高速です。しかしながら、特に128コアの場合は10%近く高速です。また同じ分割数では、連続方式がMETISと同程度の性能を示しています。
128コアでの負荷バランスを考えるために、図6に各3手法における128領域毎のセル数を示しました。またその他の影響として、境界面を含む領域でのセル数があります。領域分割において境界の不公平な配置があれば、余分な通信を持つ領域が生じるでしょう。
この特別な例題のために、問題サイズを100000セルに固定したままコア数を増やすと、通信オーバーヘッドは増加し、32コアで全通信時間は54%だったのに対し、256コアでは78%でした。つまり256コアの3つのケースの場合、経過時間中では通信時間がほとんどで、領域分割の工夫による利得は多くありません。しかしながらより少ない領域数では分割法による効果が重要なのは明白です。
これらの結果はCABARETで用いる際に非構造六面体メッシュの領域分割には、他に比べてScotchが僅かに良好な性能を示したことが実証されました。METISは、Scotchはデュアルグラフ形式入力が必要となるのに比べ、元の非構造グリッドに似た入力をユーザへ提供することから、より使いやすい手法です。実際には、分割を実施する前のプリプロセスの段階で、簡単に組み合わせて利用することが出来ます。
6. 結論
本報告において非構造グリッドの考え方を紹介しました。このようなグリッドタイプを用いるアプリケーションは、分散メモリー並列計算機へ移植する場合に、グリッドに対する効果的な分割方法が必要です。METISとScotchという領域分割パッケージの利用について概説し、HECToRフェーズ2a上での利用をデモンストレーションしました。CFDコードCABARETで用いる固定サイズの非構造6面体グリッドに対して、領域分割へのこれらの利用を比較しました。
代表的なテストケースの結果は、Scotchが生成する領域分割の性能が、METISに比べて僅かに良好であることが示されましたが、METISは、今回のケースではScotchより比較的使いやすいことも示されました。
Reference
[1] "An efficient heuristic procedure for partitioning graphs", B. W. Kernighan and S. Lin, Bell Systems Technical Journal 49 (1970), pp291-307.
Also available at http://www.cs.princeton.edu/~bwk/btl.mirror/new/partitioning.pdf
[2] http://www-users.informatik.rwth-aachen.de/~roberts/software.html
[3] http://www.cs.sandia.gov/CRF/chac.html
[4] http://www.gre.ac.uk/~c.walshaw/jostle/
[5] http://www-users.cs.umn.edu/~karypis/metis/
[6] http://www.labri.fr/Perso/~pelegrin/scotch/
[7] "Static mapping by dual recursive bipartitioning of process and architecture graphs", F. Pelegrini, Proceedings of the IEEE Scalable High-Performance Computing Conference (1994), pp486-493.
[8] "A multilevel algorithm for partitioning graphs", B. Hendrickson and R. Leland, Proceedings of the IEEE/ACM SC95 Conference(1995), pp28-28. Also available at http://www.sandia.gov/ bahendr/papers/multilevel.ps
[9] "Multilevel k-way partitioning scheme for irregular graphs", G. Karypis and V. Kumar, Journal of Parallel and Distributed Computing Vol.48 (1998), pp96-129. Also available at http://www.cs.umn.edu/~karypis
[10] "A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs", G. Karypis and V. Kumar, SIAM Journal on Scientific Computing Vol. 20 (1999), pp359-392.
[11] http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/metis-4.0.tar.gz
[12] http://www.cecill.info/licenses.en.html
[13] http://gforge.inria.fr/frs/download.php/23390/scotch 5.1.7.tar.gz
[14] "A New Efficient High-Resolution Method for Nonlinear Problems in Aeroacoustics", S.A. Karabasov and V.M. Goloviznin, American Institute of Aeronautics and Astronautics Journal Vol. 45 (2007), pp2861-2871.
さらに詳しくお知りになりたい場合は、HECToR CSE Team までお問い合わせください。
The Numerical Algorithms
Group Ltd, Wilkinson House, Jordan Hill Road, Oxford, OX2 8DR, United
Kingdom
Telephone: 01865 511 245 Email: hector-cse@nag.co.uk
Web: http://www.hector.ac.uk/cse/