近況報告

近況報告
遠藤敏夫
近況の概要
Phoenix上でデータ並列プログラム(LU分解)
を実装
 記述法の議論
 性能評価

MPIと同等(0.89—1.15倍)の速度
性能へテロな環境にも対応
SACSIS03に投稿

背景: Grid

広域に分散した計算資源を効率的に利用する考え
方&環境




多数のノード、ノード増減
ヘテロ性
セキュリティ
Gridツールが徐々に一般的に(Globus, Nimrod…)

でも、ちょっと複雑な並列プログラムが書きにくい
Grid上のアプリケーション

巨大なCPU資源を利用



巨大なストレージ資源を利用


計算物理学、生物情報
SETI＠home
本発表の
メイン
生物情報、gnutella
広域分散した情報を利用

gnutella, ネットワークゲーム
発表の概要

MPIとPhoenixの概要


LU分解アルゴリズム



ノード増減、性能へテロ性への対応
MPIによる並列化
Phoenixによる並列化
LUの性能評価
MPI
素朴なメッセージパッシングAPI
 物理ノードがそのまま見えるモデル


整数のノードIDで通信先指定(0~P-1)
API(抜粋)





MPI_Send(buf, count, type, dest, tag, comm)
MPI_Recv(buf, count, type, source, tag, comm, stat)
MPI_Comm_Rank(comm, rank_p) 自ノードID取得
MPI_Comm_Size(comm, size_p) ノード数取得
集団通信(broadcastなど)
MPIでのデータ並列プログラム
の記述



データ(配列、行列)を
各ノードに分散配置
他ノードのデータが
必要なら通信
ノード増減への対応
が難しい
Phoenix [田浦02]



メッセージパッシングの拡張
仮想ノードID(0~262-1)を対象に通信
API(抜粋)


ph_send(dest, msg)
msg = ph_recv()


自分が担当する仮想ノードあてメッセージを受信
ph_assume(vp_set)

担当仮想ノードの設定
Phoenixでのデータ並列プログラ
ムの記述(1)

2種類のマッピングを指定




データと仮想ノード
仮想ノードと物理ノード
ノード増減時には仮想ノード担当を変更
CPU性能に比例した仮想ノード数を割り当
て → 性能へテロ対応
Phoenixでのデータ並列プログラ
ムの記述(2)
データ
仮想ノード
物理ノード
本当にPhoenixはノード増減へ
の対応が楽なのか？(1)

MPIで増減対応プログラムを書くには



(1) データと物理ノードの新マッピング決定
(2) データの移送処理
(3) データの位置情報の更新
cf. A[i]⇔物理ノードIDの表を全員が更新
本当にPhoenixはノード増減へ
の対応が楽なのか？(2)

Phoenixで増減対応プログラムを書くには
(1) 仮想ノードと物理ノードの新マッピング決
定
 (2) データの移送処理
位置情報の更新は要らない。(1)の変更を行っ
た場合でも、Phoenixランタイムが自動でルー
ティング表を更新、正しい宛先に届けてくれる。

→ Phoenixの利用により(3)が省ける
性能へテロ性への対応


Phoenixでは、CPU性能∝担当仮想ノード
数により、対応可
MPIでもできる場合があるが、サイクリック
分割(後述)の場合にやりにくい
発表の概要

MPIとPhoenixの概要


LU分解アルゴリズム



ノード増減、性能へテロ性への対応
MPIによる並列化
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)
右下ほど計算量が多い
→ ブロック分割よりサイクリック分割が望ましい
MPI上での並列化


物理ノード間で要素たちを分担
LUではサイクリック分割
ブロック分割
P0
P1 P2
P3
P4 P5
サイクリック分割
(実際にはブロック-サイクリッ
ク分割が使われる)
Phoenixモデルでの並列化

各要素を仮想ノード空間にばらまく
サイクリック分割
もどきの一例
ブロック分割
ノード0
ノード262-1

要素たちに一次元の順番
をつけ、ばらまく

行列を適当な数に分割し、
左と同様
Phoenix版の最適化

効率的なブロードキャスト
複数の仮想ノードに同一メッセージを送りたい
 一つ一つメッセージを送るのは通信量大
→ メッセージをまとめることにより通信削減

ノード増減と同時に起こっても正しく動作(論文
参照)
発表の概要

MPIとPhoenixの概要


LU分解アルゴリズム



ノード増減、性能へテロ性への対応
MPIによる並列化
Phoenixによる並列化
LUの性能評価
実験環境

800MHzクラスタ (hibariXX.kototoi.org)



1.4GHzクラスタ (tsubameXX.kototoi.org)



Pentium III 800MHz×2CPU×16ノード
Linux 2.4.18
Pentium III 1.4GHz×1CPU×16ノード
Linux 2.4.18
100Mbpsネットワーク
実験1: Phoenix版とMPI版の比
較

LU-MPI(MPI版LU)


mpich1.2.4を使用
LU-PH(Phoenix版LU)



金田版Phoenixランタイムを使用
物理ノード数、仮想ノード担当はプログラム実行中一
定
接続グラフは全対全
GFlops
LU-PHとLU-MPIの速度比較

4
3.5
3
2.5
2
1.5
1
0.5
0



0
10
20
30
40
# of processors
LU-PH (4096)
LU-MPI (4096)
LU-PH (8192)
LU-MPI (8192)
行列サイズN=4096, 8192
800MHzクラスタ
LU-PHはLU-MPIと同等の速
度 (0.89—1.15倍)
LU-PHは2nプロセッサ以外で
遅め

分割形状が不規則で、通信が
増えるため？
総通信量の比較

総通信量 (MBytes)
6000
LU-PHでは2nプロセッサ以
外で通信が多くなる傾向
5000

4000
3000

2000
1000
0
0
10
20
30
40
# of processors
LU-PH (4096)
LU-MPI (4096)
LU-PH (8192)
LU-MPI (8192)
前頁の結果を全て説明するか
どうか、まだ不明
LU-MPIの通信が多いのは効
率化不足のため
実験2: 性能ヘテロ性への対応


800MHzマシンと1.4GHzマシンを混ぜて実験
Phoenix上で、仮想ノード担当量を自由に調整
速いマシン:遅いマシン=
 1:1
 9:7
 10:6
 11:5
 12:4
性能ヘテロな環境でのLU-PHの
速度

1.4
relative speed
1.2

1
0.8
uniform
"9:7"
"10:6"
"11:5"
"12:4"
0.6
0.4
0.2
0
1+1
2+2
4+4
8+8
# of processors
16+16
プロセッサが少ないとき、
担当変更の効果あり
4+4, 16+16プロセッサで
は変えない方が良かった
関連研究

MPICH-V [Bosilcaら 02] (SC02)



Grid上でMPIプログラムが無変更で動作
ノード故障に対応 (checkpointingによる)
ノード増減、負荷分散はユーザ責任
関連研究

性能へテロクラスタでのLinpack
アルゴリズム[笹生ら02]
(JSPP02)


LinpackはLUを含む
速いマシンに遅いマシンの整数倍
の要素を割り当てる
→ Phoenixではより自由に調整可能
まとめ

Phoenixで並列LU分解プログラムを記述



比較的容易な記述で、ノード増減にも対応
MPI版と同等の性能
性能へテロ性にも対応
今後の展望 (誰かがやってくれ
るであろうことも含めて)


LANをまたいだ環境での実験
ノード増減がある場合の実験




第一段階: 通知してからのノード脱退
第二段階: いきなりノード脱退
多様なアプリケーション
ツールの充実
SGC is still alive!

問い合わせがいくつかあり、SGCをメンテ中です
(Version 0.4beta)
 GC_malloc/GC_free更に高速化
 Boehm GCとの互換性向上(SGC_init廃止など)

TODO:

Incremental GC機能の公開


GC_freeとのからみもやっかい
64bit対応

Download Report