近況: Phoenixモデル上の データ並列プログラム (副題: Top500@homeへの第一歩?) 遠藤敏夫

背景: Grid Gridツールが徐々に一般的に(Globus, Nimrod…) 古典的な並列計算研究ではGridに対応しきれない でも、ちょっと複雑な並列プログラムが書きにくい 古典的な並列計算研究ではGridに対応しきれない 多数のノード、ノード増減 ヘテロ性 セキュリティ Gridの特徴に対応しつつ、古典的並列に迫る性能は可能か？

TOP500(www.top500.org)とは 速いスーパーコンピュータ上位500位 古典的並列の祭典? Linpack(密行列連立一次方程式)のGflopsにより決定 データ依存関係が多いので、seti@homeよりは難しい ちなみに2002/6現在、 1位: 地球シミュレータ (35,860GFlops) 2位: ASCI White (7,226GFlops) 47位: 松岡研480CPUクラスタ (716GFlops)

現状 Phoenixモデル上でLinpackもどきを記述 記述を楽にするために以下のモジュール作成 性能はまだヘボヘボ LU分解のみ、pivotingなし 記述を楽にするために以下のモジュール作成 分散行列 集団通信 性能はまだヘボヘボ Ultra SPARC　750MHz ×16上で、0.50GFlops アプリケーション 分散行列 モジュール 集団通信 モジュール Phoenix通信 モジュール

発表の概要 普通のモデルとPhoenixモデル LU分解と、単純な並列化 集団通信 まとめ ブロードキャストを用いた場合 部分ブロードキャストを用いた場合 まとめ

普通の メッセージパッシングモデル MPI (www.mpi-forum.org) 汎用メッセージパッシングAPI仕様 物理ノードがそのまま見えるモデル ノードIDは0～P-1 ノード数増減への対応はプログラマの責任 API MPI_Send: 送信 MPI_Recv: 受信 MPI_Comm_Rank: ノードID取得 集団通信(broadcastなど) など

Phoenixモデル [田浦01] 仮想ノード空間([0,264)など)を物理ノードに分配 仮想ノード数が莫大な点が、のちのち話題に 物理ノード増減 = 仮想ノードのやりとり バケツリレーによりメッセージを配送 [0000,3FFF] [4000,7FFF] [8000,FFFF] [8000,BFFF] [C000,FFFF] 仮想ノード数が莫大な点が、のちのち話題に

Phoenix通信API P_send(dest, msg) (dest, msg) = P_recv() 自分あてのメッセージを一つ受信 vpset = P_get_assigned_vps() 自分の担当する仮想ノード集合を取得 P_set_assigned_vps(vpset) ～を設定 その他、ノード集合演算 etc.

発表の概要 普通のモデルとPhoenixモデル LU分解と、単純な並列化 集団通信 まとめ ブロードキャストを用いた場合 部分ブロードキャストを用いた場合 まとめ

LU分解 U L A U L A(i) 全体の計算量はO(n3) 右下ほど計算量が多い → ブロック分割よりサイクリック分割が望ましい for( i = 0; i < n; i++ ) for( j = i+1; j < n; j++ ){ A[j][i] /= A[i][i]; for( k = i+1; k < n; k++) A[j][k] -= A[i][k] * A[j][i]; } U L A U L A(i) 全体の計算量はO(n3) 右下ほど計算量が多い → ブロック分割よりサイクリック分割が望ましい

普通のモデルでの並列化 「ノード数<<要素数」なので、要素を分担 P0 P1 P2 P3 P4 P5 ブロック分割 サイクリック分割 P0 P1 P2 P3 P4 P5 (実際にはブロック-サイクリック分割が使われる)

Phoenixモデルでの並列化 「仮想ノード数>>要素数」 に注意 仮想ノード空間に均一に割り当てる ブロック分割 サイクリック分割 ノード 0000 ノード FFFF 仮想ノード空間に均一に割り当てる 行列を適当な数に分割し、左と同様

並列LU分解の実装(単純版) LUアプリケーション 分散行列モジュール P_send/P_recvにより記述 Phoenix通信モジュール ブロック分割・サイクリック分割に対応 仮想ノード移送時にデータも移送(詳細略) Phoenix通信モジュール TCP/IP上に(てきとうに)実装 ノード増・リーフノード減に対応(詳細略)

実験環境 Sun Bladeクラスタ gcc –O4 各ノードに均等に仮想ノード割り当て パラメータ Ultra SPARC 750MHz × 2 × 16ノード (各ノード1CPUのみ使用) gcc –O4 各ノードに均等に仮想ノード割り当て パラメータ 行列サイズ=2048×2048 ブロックサイズ=64×64 サイクリック分割数=8×8

単純版LUの性能 4CPUで性能頭打ち 原因の一つは無駄な通信の多さ → ブロードキャストが必要 2n以外で特に遅いのは分割の不規則性のためか？

発表の概要 普通のモデルとPhoenixモデル LU分解と、単純な並列化 グループ通信 まとめ ブロードキャストを用いた場合 部分ブロードキャストを用いた場合 まとめ

LU分解の通信パターン 1つの要素を、複数の要素の計算に用いる 近くの要素たちは、おそらく同CPUが担当 第iループ for( j = i+1; j < n; j++ ){ A[j][i] /= A[i][i]; ← 真上の要素を使って更新 for( k = i+1; k < n; k++) A[j][k] -= A[i][k] * A[j][i]; ↑ 真左と真上の要素を使って更新 } 1つの要素を、複数の要素の計算に用いる 近くの要素たちは、おそらく同CPUが担当 → 相手ごとにメッセージを送るのはムダ → ブロードキャストしたい

Phoenix上での ブロードキャスト メッセージを仮想ノード空間全体に送信したい 物理ノードグラフを知っていることにする？ 実際のメッセージ数が、O(仮想ノード数)やO(行列要素数)では困る O(物理ノード数)にしたい 物理ノードグラフを知っていることにする？ モデルが複雑に 送信とほぼ同時にノード増減が起こると微妙 → 空間のDivide&conquerで手軽に実現

ブロードキャストアルゴリズム メッセージにあて先ノード範囲を添付 範囲中の任意の1ノードへ送信 受信メッセージのあて先が 物理ノード アプリ 集団通信モジュール Phoenixモジュール 物理ノード アプリ 集団通信モジュール Phoenixモジュール 物理ノード アプリ 集団通信モジュール Phoenixモジュール 物理ノード メッセージにあて先ノード範囲を添付 範囲中の任意の1ノードへ送信 受信メッセージのあて先が すべて自分→受信 それ以外→２分してやり直し

ブロードキャスト版LUの性能 2, 4, 8CPU以外で悪化 さすがに仮想ノード全部に送るのはムダ 2n以外でメッセージが増加

発表の概要 普通のモデルとPhoenixモデル LU分解と、単純な並列化 グループ通信 まとめ ブロードキャストを用いた場合 部分ブロードキャストを用いた場合 まとめ

一部へのブロードキャスト MPIの場合 Phoenixの場合 任意のノード集合を設定可能 (ex. CPU0と2と6にブロードキャスト) 任意の仮想ノード集合 メモリ・時間コスト大 任意の行列要素

どんな部分集合を考えるか 同じ行・列へのブロードキャストの出番は多 → のノード集合へ送ればよい これもDivide&conquerでok これ以外の集合については検討課題

部分ブロードキャスト版LUの性能 これまでより圧倒的に性能向上 ただし8CPUで頭打ち 2n以外ではやはり悪い

関連研究 MPICH-V [Bosilcaら 02] (SC02) HPF2.0仕様 [荒木ら 02] (JSPP02) Grid上でMPIプログラムが無変更で動作 ノード故障に対応 (checkpointingによる) ノード増減、負荷分散はユーザ責任 HPF2.0仕様 任意の幅のBLOCK分割に対応 [荒木ら 02] (JSPP02) 性能ヘテロに対応した動的負荷分散 (HPF2.0使用) プログラマが性能計測フェーズを記述し、その後処理系が配列マッピングし直し 負荷分散時に全プロセッサが協調

関連研究 Space filling curve [Peano 1890] d次元から1次元へのマッピング 非均一な並列プログラムの負荷分散方法として利用される 本研究の文脈では、行・列の部分集合をどう表現？

まとめ Phoenixは高性能計算に向いているか？ → 実装がヘボいので結論はまだ出せない 現状では、最高0.516GFlops (台数効果4.0倍)

TCP/IP tips 小さいメッセージの到着が遅れる → setsockopt()でTCP_NODELAYを設定 通信量が増えるとデッドロックする read()だけでなくwrite()もブロックする → fcntl()でO_NONBLOCKを設定