Ning Li, Numerical Algorithms Group Ltd.
目次
1 イントロダクション
2 ノンブロッキングMPIグループ通信
2.1 LibNBC
2.1.1 GNUコンパイラーとOpenMPを用いた開発システム
2.1.2 HECToRフェーズ3システム
2.1.3 非同期実行
3 2DECOMP&FFTにおいてOCCをサポートするAPI
3.1 ノンブロッキング・グローバル行列転置をサポートする低レベルAPI
3.2 3次元FFTの応用
3.3 OCCを用いた多重独立FFTをサポートする高レベルAPI
3.4 細粒度OCCによる3次元FFT API
4 2DECOMP&FFTのフレキシブルなデータレイアウト
4.1 概要
4.2 戦略
4.3 実装の詳細
5 結論と今後
6 謝辞
1 イントロダクション
本プロジェクトは、インペリアル・カレッジの乱流、混流および流体制御グループにより開発・利用されているCFDアプリケーションIncompact3Dの継続的な開発に関連付けられるものです。このアプリケーションIncompact3Dは、産業コードの汎用性にスペクトル法コードの正確性を組み合わせたNavier-Stokesソルバーです[7][8]。これまでのdCSEサポートの大きな成功により、Incompact3Dは現在、10万コア以上までスケールし[9]、HECToR上で8万~1万6千コアのジョブ実行が定常的に行われています。この結果、本研究グループは、マルチスケール/フラクタルに生成される乱流の物理に対する研究遂行により、最先端の乱流研究成果を産出しています。
その高度な並列処理の達成には、ここで開発された分散FFTインターフェイスを持つ高並列の2次元ペンシル型領域分割ライブラリー:2DECOMP&FFTが重要な役割を担っています。この数値計算フレームワークは、以前のIncompact3DのdCSEプロジェクトによる再利用ソフトウェアコンポーネントを含んでおり、同様の数値計算アルゴリズムと並列化の仕組みを用いて、他のアプリケーションへ容易に適用することが可能です[4]。このソフトウェアはその後、オープンソースとなり[1]、現在はOpen Petascale Librariesの一部になっています[3]。
2Dペンシル領域分割の導入により大規模並列が可能になりましたが、現在スケーラビリティの主たる障害となるのは通信コストであり、大規模シミュレーションにおいては多くの場合総コストの50%以上に達します。この問題の回避に対して理論的に明らかな方法は、通信と計算のオーバーラップOCC:overlapofcommunicationandcomputationを行うことです。しかしこうしたオーバーラップを行うのは簡単ではありません。何故ならこれらアプリケーションで用いられているall-to-all通信パターンは、現存のMPIライブラリーではブロッキング通信として実装されているため、一般的には望ましいソフトウェア的なサポートはありません。本プロジェクトは、Incompact3DのようなアプリケーションでOCCを容易にするために、2DECOMP&FFTフレームワーク内でOCCをサポートすることによりこの問題に対処します。
本プロジェクトは、フルタイムベースで5人月の予算が与えられ、実際には40%ベースで1人年とされ、公式には2012年5月から開始されました。
元々の提案では2つの作業項目が設定されました。一つ目は、2DECOMP&FFTにフレキシブルなデータレイアウトをサポートすることで、これは他の作業に対して前もって必要な作業で、セクション4で議論します。2つ目の作業は、Incompact3Dに対して、ノンブロッキングMPIグループ通信を用いた別のFFTコードを開発することで、これはセクション2,3で議論します。
2 ノンブロッキングMPIグループ通信
all-to-all通信を使うアプリケーションでは、通信と計算のオーバーラップを実現する技術的なアプローチは複数あります。例えば、これまでのHECToRプロジェクトにおいてAntonら[4]は、OpenMPスレッドを用いればOCCが実現できることを示しました。しかしながらこれは、all-to-all呼出しをノンブロッキングMPI送受信と置き換える必要がありますつまり、高レベルのMPI関数を低レベルの操作で書き換えることです。
これとは別に、OCCを片方向通信で置き換える方法があります。これは、GEMINIインターコネクトに内蔵されたRDMAを持つCray XE6には魅力的なアイデアです。しかしながらこれは、一般的に言って実装は困難であり、低レベルのシステムライブラリーHECToR上のlibntkおよびlibonesided形式のソフトウェアサポートが必要になりますが、著者の見解ではこれらは十分に使いこなせる段階のものではありません。
本プロジェクトは第3の方法を用いる事とします。それはノンブロッキングMPIグループ通信を用いてOCCを実現することです。ノンブロッキングMPIグループ通信のアイデアは長期間に渡り検討されてきました。それは前のMPI-2.2標準をかろうじて逃しましたが、おそらくMPI-3.0で最も詳細に調べられた新機能です。基本となるアイデアは直截的に、アプリケーションが以下の形式で'即時に'グループ通信することを許すものです:
CALL MPI_I......(......, request, ierror) ! more computations CALL MPI_WAIT(request, status, ierror)
これは通信と計算のオーバーラップを容易に行い、すでにあるMPI1対1通信で可能です。現状のプロジェクトに直接関わるのは、MPI-3.0で新たに導入された関数MPI_IALLTOALLおよびMPI_IALLTOALLVです。
2.1 LibNBC
本プロジェクトが始まった2012年5月にはまだ、MPI-3.0標準は決まっていませんでした。その仕様は2012年9月にリリースされています。当然ライブラリーベンダーはより品質の高い実装を行うにはより時間が掛かります。そのため、本プロジェクトでは、ノンブロッキングMPIグループ通信のプロトタイプであるLibNBCをベースに作業しました。本レポートが発行された時点では、幾つかの技術的な詳細は残念ながら旧式なものになってしまいましたが、主要な考え方は同等です。
LibNBC[2][5]はノンブロッキングMPIグループ通信のリファレンス実装です。本作業では、最新版1.1.12012年7月を用いました。ここではこのライブラリーを用いた構築の技術的詳細を示します。
2.1.1 GNUコンパイラーとOpenMPを用いた開発システム
ライブラリーはLIBNBC_DIRローカルパスに指定できますへ、GNUコンパイラーと$PATHで指定されるOpenMPバイナリー群を使って以下のように構築します:
./configure --prefix=$LIBNBC_DIR make make install
このライブラリーを用いてアプリケーションを作成するには、リンク時に以下のフラグを追加します:
$LIBNBC_DIR/lib/libnbc.a -lstdc++ -lmpi_cxx
2.1.2 HECToRフェーズ3システム
HECToR上では、ライブラリーはLIBNBC_DIRへ、PGIコンパイラーを使って以下のようにします:
MPICXX=CC ./configure --prefix=$LIBNBC_DIR --host=x86_64-unknown-linux make make install
-hostにより正しいクロスコンパイラを使うようにします。アプリケーション作成時には以下をリンカーに渡します:
$LIBNBC_DIR/lib/libnbc.a
2.1.3 非同期実行
理想的には、MPIライブラリーはハードウェアのインターコネクトへ通信を任せて、プロセッサーは計算に専念することが可能です。[6]で報告されているように、このことはInfiniBandクラスターで実現されています。こうしたハードウェアやライブラリーサポートが可能でない場合も、ソフトウェアにより実現することは可能です。libNBCはスレッドに対して同時に通信することを許容します。こうしたサポートをするには、configureスクリプトのコマンドラインに次のフラグを追加します:
--with-thread あるいは --with-rt-thread
残念ながらHECToR上では、こうしてリンクされたアプリケーションは全て実行時エラーとなってしまいます。原因については、1ここには極めて低レベルのソフトウェア実装の問題を含むため本調査の範囲を超える、また、2通信を可能にする別の実用的な方法:アプリケーションの主な計算スレッドからMPI_TESTを呼び出すという方法があるため、調査はしていません。
完全な非同期実行の実装は多くの場合プラットフォーム依存であり、今後この問題を扱うのにMPIライブラリーのベンダー実装から離れたほうが好ましいと考えられます。
3 2DECOMP&FFTにおいてOCCをサポートするAPI
ノンブロッキングMPIグループ通信を使ってアプリケーションに通信と計算のオーバーラップを実装するために、2DECOMP&FFTへ多くの新しいAPIを導入しました。数値計算アルゴリズムにより様々なOCC実現方法があります。このセクションではこれらの詳細を述べます。
3.1 ノンブロッキング・グローバル行列転置をサポートする低レベルAPI
Incompact3Dのような大規模シミュレーションにおいては、内部的にはall-to-all通信の全行列転置操作に、多くの場合非常に時間が掛かります。例えば、アプリケーションデータが2Dペンシル型2Dペンシル領域分割についてはhttp://www.2decomp.org/decomp.htmlを参照して下さい。特にペンシルの正確な定義がこのwebページ内の図2に示されています。で配置されているとすれば、X-ペンシルからY-ペンシルへデータを転置するには、このアプリケーションは以下の2DECOMP&FFT通信APIが必要になります:
call transpose_x_to_y(in, out)
ここで、inはX-ペンシルに格納された入力データ、outはY-ペンシルに格納された出力です。この通信ルーチンは内部的に以下の3つの段階から成ります:
- ①入力データ配列からMPI送信バッファへデータをギャザー(収集)する
- ②MPIプロセスへデータを再分配するためにMPI_ALLTOALLVあるいはユーザー指定によりMPIALLTOALLを呼出す
- ③MPI受信バッファから利用可能な形式の出力データ配列へデータをスキャッター(分散)する
特にステップ2はブロッキング操作であり、通信が完了するまでロックされるため、大規模シミュレーションにおいては非常に大きな時間が掛かります。ノンブロッキングAPIにおいては、MPIのノンブロッキングAPI仕様に従って、この操作は以下の2つのパーツに分かれます:
call transpose_x_to_y_start(handle, in, out, sbuf, rbuf) call transpose_x_to_y_wait (handle, in, out, sbuf, rbuf)
ここでhandleは特別な通信セットを指定するのに用いられます。同時に複数のノンブロッキング通信が発生するため、アプリケーションは各通信用に送信バッファsbufと受信バッファrbufを用意する必要があります。startルーチンはMPI送信バッファを用意して、all-to-all通信を開始してすぐに戻ります。続いてwaitルーチン呼出しはその通信が完了するのを待ってMPI受信バッファを展開します。start呼出しとwait呼出しの間、予期せぬ結果を避けるために、sbufの内容は修正されるべきでなく、outの内容は参照されるべきでありません。通信が行われている間に、他の関係しない計算は実行可能となります。
この通信と計算のオーバーラップの原理は極めて単純で、アプリケーション開発者次第でそのアイデアを自身のアルゴリズムに適用することができるでしょう。
3.2 3次元FFTの応用
上述のノンブロッキングAPIを実例として、多重独立3次元FFTを実行するアルゴリズムを紹介します。データは2Dペンシルとして配置されていると仮定して、典型的な並列FFT計算を以下のように実装することが出来ます:
- ①実空間データをX-ペンシルへ配置し、最初にX軸方向の1D FFTを実行する
- ②X-ペンシルをY-ペンシルへ転置する
- ③Y方向の1D FFTを実行する
- ④Y-ペンシルをZ-ペンシルへ転置する
- ③Z方向の1D FFTを実行する。得られたスペクトル実空間データはZ-ペンシルに格納される他のデータ配置でも実用上問題は生じません。スペクトル実空間データをX−ペンシルへ戻す2つの転置を実行するオプションもあります。。
通常のMPI_ALLTOALLVで上記の転置操作を実現した場合、一度に1つの並列FFTしか実行できません。ノンブロッキングAPIを使えば、1つのFFTの通信と、他のFFTの計算をオーバーラップさせるように設計することが可能です。このようなアルゴリズム設計には様々な方法がありますが、本プロジェクトでは[6]で提案された、最も直截的なやり方で実装しました。このアルゴリズムは以下の疑似コードで表されますデータデットをViで代表させています:
1D FFTs in X for V_1 call transpose_x_to_y for V_1 (blocking) 1D FFTs in Y for V_1 call transpose_y_z_start for V_1 do k=2,N 1D FFTs in X for V_k call transpose_x_to_y for V_k (blocking) 1D FFTs in Y for V_k call transpose_y_to_z_start for V_k call transpose_y_to_z_wait for V_(k-1) 1D FFTs in Z for V_(k-1) end do call transpose_y_to_z_wait for V_N 1D FFTs in Z for V_N
変数kのYからZへの転置と変数k-1のZ方向の1D FFT計算がオーバーラップしています。
以前に記したように、libNBCで非同期通信を行おうとすると、HECToRでうまく行きません。MPI_TEST呼出しを通信に用いなければなりません。通常は上述のアルゴリズムによる多重1D FFTは、FFTWのようなAPIで一度に実行可能です。今はこれらは、MPI_TESTが正しく挿入され呼出しが出来るように、ループ内で単純な1D FFTで実装しなくてはなりません。将来より良いMPI実装が可能になれば、この制約は外されるでしょう。
3.3 OCCを用いた多重独立FFTをサポートする高レベルAPI
前のセクションのアルゴリズムをベースに、2DECOMP&FFTの高レベルAPIを導入し、一回の関数呼出しで多重「独立FFTを実行しましょう。これはスペクトル法によっては大変便利です。そのAPIは以下の形式です:
call decomp_2d_multiple_fft(in, out, opt_sbuf, opt_rbuf)
ここで、入力inと出力outは別の3Dデータセットを示す次元を含む4次元配列です。各3Dデータセットは、2DECOMP&FFTで定義されるペンシル型分散形式でなくてはなりません。2つの付随する作業領域配列は、アプリケーションでMPIグループ通信に用いる送受信バッファーとして利用されます。これらは各々通信/計算オーバーラップ時に要求されるために、少なくとも個々の3Dデータセットの2倍でなければなりません。もしこのような作業領域が確保できないときは、ライブラリーは必要なスクラッチ領域を内部的に確保します。
このAPIは、実際のアプリケーション利用において、ユーザーがより適切とするデータ構造に関する情報により変更されることが考えられます。しかしながら、2DECOMP&FFTフレームワークはFortranの正規なインターフェイスにより柔軟な設計となっており、新たな変更を容易に導入することが可能です。
3.4 細粒度OCCによる3次元FFT API
1つのFFTの通信と他のFFTの計算をオーバーラップさせるという、セクション3.2で示したアルゴリズムを粗粒度OCCと呼びます。1つの3D FFT内でOCCを実現することも可能で、これを細粒度OCCを呼ぶことにします。
このアイデアは、[11]の同じペンシル領域分割を用いた分散FFTアルゴリズムで検証されており、その中で著者らは、最初に転置のためにデータセットの4分の3を任意に選択し、データ転置を開始し、残りの4分の1の計算をオーバーラップさせています。このような初歩的なアプローチでさえ、問題サイズが十分に大きければHECToRで10%の性能向上を示しています。
本プロジェクトの細粒度OCCアルゴリズムはより柔軟なものです。それは、図1で記述されるような、Y-ペンシル左図とZ-ペンシル右図間の転置が1つのMPI_ALLTOALLV操作で実行可能なものです。より小さな操作で、例えば一度に複数MPI_ALLTOALLV操作を用いて1つのX-平面へデータを再配置することも可能です。
同様にX⇔Y転置において、一度に一つのZ-平面のデータを扱うことが可能です。このような様々な細粒度OCCの実装が可能です。次の図はX⇔Y転置のアルゴリズムですセクション4で説明するように、この操作に最も適したメモリーレイアウトです。
図1 : Y-ペンシルからZ-ペンシルへの転置
1D FFTs in X for Z_1 plane call transpose_x_to_y_start for Z_1 do k=2,nz (where nz is the size of Z dimension) 1D FFTs in X for Z_k plane call transpose_x_to_y_start for Z_k call transpose_x_to_y_wait for Z_(k-1) 1D FFTs in Y for Z_(k-1) plane end do call transpose_x_to_y_wait for Z_nz 1D FFTs in Y for Z_nz plane ...... code for Y to Z transpose and 1D FFT in Z
このアルゴリズムは、以前に述べた粗粒度OCCのものと似たロジックを持ち、Zk平面のデータ通信とZk−1平面の計算をオーバーラップさせています。このアルゴリズムはスタンドアローンアプリケーションに実装され、正常に実行されていますこのアルゴリズムは、2DECOMP&FFTの通信APIの再利用が技術的に困難で、ライブラリー実装はされていません。。
4 2DECOMP&FFTのフレキシブルなデータレイアウト
本セクションは最初の提案における作業項目1に焦点を当てます。これは他の作業項目におけるソフトウェアの基盤です。
4.1 概要
2DECOMP&FFTライブラリーの以前のバージョンは、分散データi,j,kのペンシル操作において、iが最初に変化するインデックスであるFortranオーダーのような、通常の格納形式における3次元配列しか扱えませんでした。これは多くのアプリケーションにおいて十分便利ですが、さらに柔軟なデータレイアウトが求められる場面があります:
- Fortranの多次元配列の最初の次元を操作することは良い性能を引き出すためのポイントになりますが、それはキャッシュ効率を向上させ、その最初の次元のデータ要素がメモリー上に隣接するからです。例えば多くのFFTライブラリーは1つ飛びのデータ変換において最も良い性能を示しますが、1つ飛びのデータ入出力をサポートしていません。
- 古いアプリケーションでは、おそらく古いタイプのハードウェアでの最適化が理由で例えばベクトル機上でベクトル長を長くするために、多次元配列の次元が交換される場合があります。
本プロジェクトに関連する柔軟なデータレイアウト設計実現は、現状の2DECOMP&FFTライブラリーの通信で最小の要素であるペンシルが、通信と計算のオーバーラップを実装するためにセクション3.4で議論したようにさらにブロック化する必要があるという事実から要請されることです。
例えば、図1で示した転置において、1つのX-平面を一度に転置しようとすると、各X-平面のデータはメモリー上で自然に連続しているので、iを最後の次元にして、通信バッファのパック/アンパックをより便利で効果的にすることが望ましいでしょう。
4.2 戦略
如何なるi,j,kの組合せによるデータ格納も可能ですが、ここでは標準のi,j,kとは異なる一つの組合せが決定されました。この状況を以下に示します:
- X-ペンシルデータは常に標準のi,j,k順であり、iは最初の次元である。
- Y-ペンシルデータはj,i,kの順に格納でき、jは最初の次元となる
- Z-ペンシルデータはk,j,iの順に格納でき、kは最初の次元となる
これらの組合せは、全てのペンシル方向において完全にメモリー上ローカルな次元が常に最初の次元であり、その次元上でのアルゴリズムはキャッシュ効率が良いことを保証します。
セクション4.1での理由によって、Y-ペンシルデータにとって、j,i,kはX⇔Y転置に適しており、j,k,iはY⇔Z転置に適しています。明らかに、同時に両方の条件を満たすことはできません。よって通信バッファを用意するアルゴリズムに追加のローカルな転置が必要となります。
4.3 実装の詳細
2DECOMP&FFTにおいて、異なるデータレイアウトはプリプロセスとしてコードに実装され、2DECOMP&FFTライブラリーのビルド時に、フラグ-DSTRIDE1でスイッチされます。もしアプリケーションがこのオプションを用いたならば、その3D配列が転置されたデータレイアウトを用いて定義されます。実装の詳細をここに記します:
- アプリケーションに分散配列をアロケートさせるユーティリティールーチンを導入します。このルーチン群は、ユーザーのストレージ選択に従ってメモリーアロケーションを行いうため、開発者はこれに介在する必要はありません。開発者は分散配列のループ操作には依然として注意すべきです。
- 2DECOMP&FFTのI/Oルーチンは1つ飛びデータレイアウトに応じて更新されました。メモリー格納方法を考慮して、I/Oルーチンで生成されたデータファイルは、プリ・プロセスの簡単化のために常にi,j,k順に3D配列を保存します。
- FFTW3のAPIを使った分散FFTインターフェイスは、1つ飛びデータレイアウトに応じて更新されました。他のFFTライブラリーとの結合については特に要求がないため更新されませんでした。1つ飛びデータレイアウト使用時のHECToR上の性能差は、小規模から中規模サイズ問題においては確認されませんでした。P3DFFTユーザーガイドに従えば、1つ飛びデータレイアウトは性能上の有効性が示される場合があります。これはおそらくP3DFFTもループ・ブロッキング最適化を導入しているためです。このテクニックは便利ですが一般化や自動チューニングには困難なやり方です。
5 結論と今後
本プロジェクトを通して、2DECOMP&FFTをベースとするアプリケーションに通信と計算のオーバーラップを可能にするために、様々なテクニックを実装しました。特に以下の結果が達成されました:
- アルゴリズムとしてOCC利用を簡便にするために、2DECOMP&FFTにおける低レベルAPIが開発されました。
- このAPIの有効性は、多重独立FFTを1つのサブルーチン呼出しで可能にすることで実証されました。
- 2DECOMP&FFTを用いて構築することにより、CFDコードIncompact3DはMPI-3対応となり、将来のMPIの更新にも対応が可能となりました。
- 3D分散FFTの細粒度OCC仕様を実証する簡単なアプリケーションが作成されました。
- 2DECOMP&FFTライブラリーにより柔軟なデータレイアウトを導入しました。
- 追加されたデータレイアウトをサポートするために2DECOMP&FFTライブラリーのI/Oコードが更新されました。
本プロジェクトにおいて開発されたソフトウェアは、より広いコミュニティーの利益になるべく公開されました。
- 2DECOMP&FFTライブラリーのバージョン1.5は2012年10月にリリースされました。本リリースには本プロジェクトで開発された様々なAPIが含まれます。このライブラリーはHECToRの8つのCFDコードで用いられ、国際的に多くの研究グループに採用されています。
- CFDコードIncompact3Dは2012年11月からオープンソースとなり、研究コミュニティーから興味を持たれ、新たなコラボレーションの機会を産出しました。
dSCEサポート外ですが最初の提案に追加して2つの作業項目が追加されました。dCSEプロジェクトのスコープとは離れますが、下記のような成果がありました:
- 2DECOMP&FFTライブラリーの最新バージョンに、アプリケーションにグローバルアレイGAの片方向通信ルーチンへのアクセスを容易にするAPIが導入されました。
- FFTライブラリーのスレッドバージョンを用いる2DECOMP&FFTが開発されました。これは幾つかのシステムで良好な性能を示しました。
6 謝辞
本プロジェクトはnAG Ltd.によるHECToR分散計算科学・工学サービスdCSEにより実行されました。HECToRAResearchCouncilsUKHighEndComputingServiceは英国の国立スーパーコンピューティングサービスであり、英国リサーチカウンシルの代行としてEPSRCにより管理されています。そのミッションは英国学術界の科学および工学の実行能力をサポートすることです。HECToRスーパーコンピューターは、UoE HPCx Ltd.およびnAG Ltd.によるCSEサポートサービスにより管理運営されています。
参考文献
[1] | 2DECOMP&FFT website. http://www.2decomp.org. |
[2] | LibNBC website. http://www.unixer.de/research/nbcoll/libnbc/. |
[3] | Open Petascale Libraries website. http://www.openpetascale.org. |
[4] | L. Anton, N. Li, and K.H. Luo. A study of scalability performance for hybrid mode computation and asynchronous MPI transpose operation in DSTAR. In Cray User Group 2011 conference, May 2011. |
[5] | T. Hoe fler, A. Lumsdaine, and W. Rehm. Implementation and performance analysis of non-blocking collective operations for MPI. In International Conference for High Performance Computing, Networking, Storage and Analysis SC07, 2007. |
[6] | K. Kandalla, H. Subramoni, K. Tomko, D. Pekurovsky, S. Sur, and D.K. Panda. High-performance and scalable non-blocking all-to-all with collective offload on InfiniBand clusters: a study with parallel 3D FFT. Computer Science - Research and Development, 263−4:237-246, 2011. |
[7] | S. Laizet and E. Lamballais. High-order compact schemes for incompressible flows: A simple and efficient method with quasi-spectral accuracy. Journal of Computational Physics, 22816:5989-6015, 2009. |
[8] | S. Laizet, E. Lamballais, and J.C. Vassilicos. A numerical strategy to combine high-order schemes, complex geometry and parallel computing for high resolution dns of fractal generated turbulence. Computers & Fluids, 393:471-484, 2010. |
[9] | S. Laizet and N. Li. Incompact3d, a powerful tool to tackle turbulence problems with up to 0105 computational cores. International Journal of Numerical Methods in Fluids, 6711:1735-1757, 2011. |
[10] | N. Li and S. Laizet. 2DECOMP&FFT - a highly scalable 2D decomposition library and FFT interface. In Cray User Group 2010 conference, May 2010. |
[11] | R. Saksena. On non-blocking collectives in 3D FFTs. In Workshop on Latest Advances in Scalable Algorithms for Large-scale Systems, 2011. |