クラスタコンピューティングの 並列環境と性能 建部修見 電子技術総合研究所 tatebe@etl.go.jp

クラスタコンピューティング ETL-Wiz（電子技術総合研究所）

ETL-Wiz（１） http://ninf.etl.go.jp/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, SR-2201/8000, SP-1/2/3, T3D/E, 大多数のWS/PCクラスタ, SMP

MPI の特徴 SPMDの通信ライブラリインターフェースの標準 ポータビリティ 実装方式を規定しない 抽象度の高いインターフェース コミュニケータ （ライブラリ、集合演算、トポロジ） FORTRAN77, C（, Fortran90, C++） 基本データ型のデータサイズに非依存 実装方式を規定しない 抽象度の高いインターフェース 効率的な実装の余地 柔軟性

並列プログラムにおける 主要なオーバヘッド 負荷バランス アルゴリズム、ランタイムで解決すべき？ SPMDなので規則的な問題であればあまり問題にならない？ 通信遅延

通信遅延隠蔽 通信遅延 計算と通信のオーバラップ 並列、分散環境の主要なオーバヘッド ノンブロッキング通信 (MPI) マルチスレッド実行 (pthread 等)

通信と計算のオーバラップ

オーバラップの例 ヤコビ法 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]); }

データ依存関係とデータ分散 ヤコビ法のデータ依存関係 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]);

ブロッキング通信 buf の内容を読み書きできるようになるまでブロック 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); int count, source, tag; 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); int count, source, tag; int MPI_Wait(req, status); int MPI_Test(req, flag, st); MPI_Request *req; MPI_Request req; MPI_Status *status; 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（L3キャッシュ以上、計算＞通信） ８％程度性能向上 計算順序変更によるキャッシュミス増大 ２次元隣接通信では、プロセッサあたり N=400以上は必要