近況: Phoenixモデル上の
データ並列プログラム
(副題: Top500@homeへの第一歩?)
遠藤敏夫
背景: Grid
Gridツールが徐々に一般的に(Globus, Nimrod…)
でも、ちょっと複雑な並列プログラムが書きにくい
古典的な並列計算研究では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]
[8000,BFFF]
[8000,FFFF]
[C000,FFFF]
[4000,7FFF]
仮想ノード数が莫大な点が、のちのち話題に
Phoenix通信API
P_send(dest, msg)
仮想ノードdestにmsgを送信
(dest, msg) = P_recv()
自分あてのメッセージを一つ受信
vpset = P_get_assigned_vps()
自分の担当する仮想ノード集合を取得
P_set_assigned_vps(vpset)
～を設定
その他、ノード集合演算 etc.
発表の概要
普通のモデルとPhoenixモデル
LU分解と、単純な並列化
集団通信
ブロードキャストを用いた場合
部分ブロードキャストを用いた場合
まとめ
LU分解
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 (i)
A
全体の計算量はO(n3)
右下ほど計算量が多い
→ ブロック分割よりサイクリック分割が望ましい
普通のモデルでの並列化
「ノード数<<要素数」なので、要素を分担
ブロック分割
P0
P1 P2
P3
P4 P5
サイクリック分割
(実際にはブロック-サイクリック分割
が使われる)
Phoenixモデルでの並列化
「仮想ノード数>>要素数」 に注意
ブロック分割
サイクリック分割
ノード
0000
ノード
FFFF
仮想ノード空間に均一に
割り当てる
行列を適当な数に分割し、
左と同様
並列LU分解の実装(単純版)
LUアプリケーション
P_send/P_recvにより記述
分散行列モジュール
ブロック分割・サイクリック分割に対応
仮想ノード移送時にデータも移送(詳細略)
Phoenix通信モジュール
TCP/IP上に(てきとうに)実装
ノード増・リーフノード減に対応(詳細略)
実験環境
Sun Bladeクラスタ
Ultra SPARC 750MHz × 2 × 16ノード
(各ノード1CPUのみ使用)
gcc –O4
各ノードに均等に仮想ノード割り当て
パラメータ
行列サイズ=2048×2048
ブロックサイズ=64×64
サイクリック分割数=8×8
単純版LUの性能
LU
実行時間(s)
60
50
40
30
no bcast
20
10
0
0
4
8
12
ノード数
16
20
no bcast
速度(Gflops)
1CPU
peak
0.114
0.225
(4CPU)
4CPUで性能頭打ち
原因の一つは無駄な通信の多さ → ブロードキャストが必要
2n以外で特に遅いのは分割の不規則性のためか？
発表の概要
普通のモデルとPhoenixモデル
LU分解と、単純な並列化
グループ通信
ブロードキャストを用いた場合
部分ブロードキャストを用いた場合
まとめ
LU分解の通信パターン
第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モジュール
ブロードキャスト版LUの性能
LU
実行時間(s)
200
150
no bcast
all bcast
100
50
0
0
4
8
12
ノード数
16
20
no bcast
all bcast
速度(Gflops)
1CPU
peak
0.114
0.225
0.115
0.300
2, 4, 8CPU以外で悪化
さすがに仮想ノード全部に送るのはムダ
2n以外でメッセージが増加
(4CPU)
(4CPU)
発表の概要
普通のモデルとPhoenixモデル
LU分解と、単純な並列化
グループ通信
ブロードキャストを用いた場合
部分ブロードキャストを用いた場合
まとめ
一部へのブロードキャスト
MPIの場合
任意のノード集合を設定可能
(ex. CPU0と2と6にブロードキャスト)
Phoenixの場合
任意の仮想ノード集合
任意の行列要素
メモリ・時間コスト大
どんな部分集合を考えるか
同じ行・列へのブロードキャストの出番は多
→ { p | p0 s i, (0 i c)}
のノード集合へ送ればよい
これもDivide&conquerでok
これ以外の集合については検討課題
部分ブロードキャスト版LUの
性能
LU
60
実行時間(s)
50
40
no bcast
all bcast
part bcast
30
20
10
0
0
5
10
ノード数
15
20
速度(Gflops)
1CPU
no bcast
0.114
all bcast
0.115
part bcast 0.129
これまでより圧倒的に性能向上
ただし8CPUで頭打ち
2n以外ではやはり悪い
peak
0.225
0.300
0.516
(4CPU)
(4CPU)
(8CPU)
関連研究
MPICH-V [Bosilcaら 02] (SC02)
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を設定
© Copyright 2026 ExpyDoc
