クラスタコンピューティングの
並列環境と性能
建部修見
電子技術総合研究所
[email protected]
クラスタコンピューティング
ETL-Wiz（電子技術総合研究所）
ETL-Wiz（１）
Node
333MHz Alpha
21164
#PE
32 (+1)
Cache
L1:8KB, L2:96KB,
L3:2MB
Network
Fast Ethernet
Switch
1.2Gbps
backplane
OS
Digital UNIX
Software NFS/MPI/PVM
http://ninf.etl.go.jp/wiz/
ETL-Wiz（２）
UPSによる自動ブートとシャットダウン
共有コンソール
ネットワークスイッチによる完全結合ネット
ワーク
ロードモニタ

http://ninf.etl.go.jp/wiz/load-monitor/
ロックファイルによるプロセッサ自動選択
MPI
メッセージパッシングの標準 [1992-]

実用性、高効率、ポータビリティ、柔軟性
大多数の MPP, NOW 上に実装

AP1000/1000+/3000, Cenju-3/4, SR2201/8000, SP-1/2/3, T3D/E, 大多数の
WS/PCクラスタ, SMP
MPI の特徴
SPMDの通信ライブラリインターフェースの標準
ポータビリティ



コミュニケータ （ライブラリ、集合演算、トポロジ）
FORTRAN77, C（, Fortran90, C++）
基本データ型のデータサイズに非依存
実装方式を規定しない
抽象度の高いインターフェース


効率的な実装の余地
柔軟性
並列プログラムにおける
主要なオーバヘッド
負荷バランス


アルゴリズム、ランタイムで解決すべき？
SPMDなので規則的な問題であればあまり問
題にならない？
通信遅延
通信遅延隠蔽
通信遅延

並列、分散環境の主要なオーバヘッド
計算と通信のオーバラップ
•ノンブロッキング通信
•マルチスレッド実行
(MPI)
(pthread 等)
通信と計算のオーバラップ
PE0
PE1
PE0
communication
time
local computation
non-local computation
computation
PE1
オーバラップの例
ヤコビ法
jacobi() {
int i, j;
forall(i = 1; i < N - 1; ++i)
forall(j = 1; j < N - 1; ++j)
b[i][j] = .25 *
(a[i - 1][j] + a[i][j - 1]
+ a[i][j + 1] + a[i + 1][j]);
}
データ依存関係とデータ分散
PE0
PE1
PE2
PE3
PE4
PE5
PE6
PE7
PE8
PE9
PE10
PE11
PE12
PE13
PE14
PE15
a[i-1][j]
a[i][j-1]
a[i][j+1]
a[i+1][j]
ヤコビ法のデータ依存関係
2次元ブロックデータ分散
プロセストポロジ
２次元メッシュ
#define FALSE (0);
MPI_Comm comm2d;
static int np[2] = { npy, npx };
static int periods[2] = { FALSE, FALSE };
int reorder = FALSE;
次元数 周期的か？
MPI_Cart_create(MPI_COMM_WORLD, 2, np, periods,
reorder, &comm2d);
各次元のプロセス数
ランクの変更可？
Naïve code
/* 送受信先のプロセスランクの計算 */
MPI_Cart_shift(comm2d, 0, 1, &north, &south);
MPI_Cart_shift(comm2d, 1, 1, &west, &east);
/* 南北のプロセスとの通信 */
MPI_Sendrecv(&a[1][1], L_N-2, MPI_DOUBLE, north, NORTHTAG,
&a[L_N-1][1], L_N-2, MPI_DOUBLE, south, NORTHTAG, comm2d, &st[0]);
…
/* 東西のプロセスとの通信 */
for(i = 0; i < L_N - 2; ++i) send_buf[i] = a[i + 1][1];
MPI_Sendrecv(send_buf, L_N-2, MPI_DOUBLE, west, WESTTAG,
recv_buf, L_N-2, MPI_DOUBLE, east, WESTTAG, comm2d, &st[2]);
MPI_Get_count(&st[2], MPI_DOUBLE, &count);
for(i = 0; i < L_N - 2; ++i) a[i + 1][L_N - 1] = recv_buf[i];
…
/* 計算 */
for(i = 1; i < L_N - 1; ++i)
for (j = 1; j < L_N - 1; ++j)
b[i][j] = .25 * (a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j]);
ブロッキング通信
int MPI_Send(buf, count, datatype, dest, tag, comm);
void *buf;
int count, dest, tag;
MPI_Datatype datatype;
MPI_Comm comm;
int MPI_Recv(buf, count, datatype, source, tag, comm, status);
void *buf;
int count, source, tag;
MPI_Datatype datatype;
MPI_Comm comm;
MPI_Status *status;
buf の内容を読み書きできるようになるまでブロック
ブロッキング送受信の注意点
バッファリングの有無は規定外
バッファリングがない場合、


MPI_Send() は対応する MPI_Recv() の
発行が確認され、送信終了までブロック
（=
MPI_Ssend()）
バッファリングが必要な場合、MPI_Bsend()
を利用
ノンブロッキング通信
int MPI_Isend(buf, count, datatype, dest, tag, comm, req);
void *buf;
int count, dest, tag;
MPI_Datatype datatype;
MPI_Comm comm;
MPI_Request *req;
int MPI_Irecv(buf, count, datatype, source, tag, comm, req);
void *buf;
int count, source, tag;
MPI_Datatype datatype;
MPI_Comm comm;
MPI_Request *req;
int MPI_Wait(req, status);
MPI_Request *req;
MPI_Status *status;
int MPI_Test(req, flag, st);
MPI_Request req;
int *flag;
MPI_Status *st;
計算と通信のオーバラップ
/* 送受信リクエストの発行 */
MPI_Irecv(…, &req[1]);
MPI_Isend(…, &req[0]);
/* ローカル計算 */
for(i = 2; i < L_N - 2; ++i)
for(j = 2; j < L_N - 2; ++j)
b[i][j] = .25 * (a[i-1][j] + a[i][j-1]
+ a[i][j+1] + a[i+1][j]);
/* 送信リクエスト完了待ち */
MPI_Wait(&req[0], &st[0]);
/* ローカルデータによる境界点の更新 （略） */
/* 受信リクエスト完了待ち */
MPI_Wait(&req[1], &st[1]);
/* リモートデータによる境界点の更新 （略） */
ETL-Wiz による評価（１）
N = 200
ETL-Wiz による評価（２）
N = 400
ETL-Wiz による評価（３）
N = 200
ETL-Wiz による評価（４）
N = 400
通信遅延隠蔽のまとめ
N=200（L3キャッシュ以下、計算＜通信）

３５％程度性能向上
N=400（L3キャッシュ以上、計算＞通信）


８％程度性能向上
計算順序変更によるキャッシュミス増大
２次元隣接通信では、プロセッサあたり
N=400以上は必要

スライド 1