第三回MPI実践セミナー
HPCシステムズ株式会社
新規事業企画室 南本 和秀
大規模・高性能への
大規模・高性能への
大規模・高性能への
大規模・高性能への
需要と物理的限界
需要と物理的限界
需要と物理的限界
需要と物理的限界
•
自然科学や物理シミュレーションなど
•
成果
/
精度を得るには「
速さ
」、「
記憶容量
」が必須
•
大規模メモリ空間が使用可能な時代
CPUクロック周波数は、
クロック周波数は、
クロック周波数は、
クロック周波数は、
4GHzを目前に足踏み
を目前に足踏み
を目前に足踏み
を目前に足踏み
メモリ容量は、物理的に
メモリ容量は、物理的に
メモリ容量は、物理的に
メモリ容量は、物理的に
しかし
並列処理による制限の回避
並列処理による制限の回避
並列処理による制限の回避
並列処理による制限の回避
Problem
小
P
1
つの巨大で複雑な問題(処理)を、
つの巨大で複雑な問題(処理)を、
つの巨大で複雑な問題(処理)を、
つの巨大で複雑な問題(処理)を、
複数の単純な問題(処理)へ分割し
複数の単純な問題(処理)へ分割し
複数の単純な問題(処理)へ分割し
複数の単純な問題(処理)へ分割し
並列に解いて高速化を図る
小
P
小
P
小
P
“並列処理”とは何を示すのか
“並列処理”とは何を示すのか
“並列処理”とは何を示すのか
“並列処理”とは何を示すのか
•
コンピュータにおいて複数のプロセッサで
1
つ
のタスクを動作させること。「問題を解く過程
はより小さなタスクに分割できることが多い」、
という事実を利用して処理効率の向上を図る
手法である。
出典
出典
出典
出典
:
フリー百科事典
フリー百科事典『
フリー百科事典
フリー百科事典
『
『ウィキペディア(
『
ウィキペディア(
ウィキペディア(
ウィキペディア(
Wikipedia
)
)』
)
)
』
』より抜粋
』
より抜粋
より抜粋
より抜粋
Y=a[0]+a[1]+…+a[99]
a=a[0]+…+a[24]
b
=a[25]+…+a[49]
c
=a[50]+…+a[74]
d
=a[75]+…+a[99]
Y=a+
b
+
c
+
d
並列処理の簡単な例
並列処理の簡単な例
並列処理の簡単な例
並列処理の簡単な例
1CPU
4CPU
ΣΣ
並列処理を行う部分
並列処理を行う部分
並列処理を行う部分
並列処理を行う部分
プロセス
0
プロセス
1
プロセス
2
プロセス
3
並列化技術の歴史
並列化技術の歴史
並列化技術の歴史
並列化技術の歴史
マルチスレッド
マルチスレッド
マルチスレッド
マルチスレッド
マルチプロセ
マルチプロセ
マルチプロセ
マルチプロセ
ス
ス
ス
ス
1つのプロセス内で、複数 のスレッドが起動し、異な るスレッドが持つ情報に 容易にアクセス出来る 異なるプロセスとして起動 し、メモリにある情報はそ れぞれ独立している。異な るプロセスのデータには、 直接アクセスできない並列化方式の比較
並列化方式の比較
並列化方式の比較
並列化方式の比較
マルチスレッド:
マルチスレッド:
マルチスレッド:
マルチスレッド:
OpenMP
共有メモリ方式
共有メモリ方式
共有メモリ方式
共有メモリ方式
マルチプロセス:
マルチプロセス:
マルチプロセス:
マルチプロセス:
MPI
分散メモリ方式
分散メモリ方式
分散メモリ方式
分散メモリ方式
メリット
•
メモリモデルが一般的
•
コンパイラによる自動並列
•
データの送受が、メモリコピーの
処理に置き換わる
•
大規模なシステム構成が可能
大規模なシステム構成が可能
大規模なシステム構成が可能
大規模なシステム構成が可能
•
実行ファイルが共有メモリ環境でも動作
実行ファイルが共有メモリ環境でも動作
実行ファイルが共有メモリ環境でも動作
実行ファイルが共有メモリ環境でも動作
デメリット
•
物理的な拡張性が低い
•
プログラムが分散メモリ環境では
動作しない
•
処理の分割法によってメモリモデルが複
雑
•
プログラミングが複雑
•
プロセス同士の情報交換が多いと、計算
全体の性能が上がらない
•
共有メモリ型、分散メモリ型の“ハイブリッド”
•
開発は逐次で行い、マルチプロセスで実行
将来の理想象
MPI
とは
とは
とは
とは
(
(
(
(
Message Passing Interface
)
)
)
)
•
複数のプロセスが、お互いにメッセージを送受
信する仕組みを提供するための標準規格
•
同一(単一)のプログラムを、複数のプロセスで
同時に実行(
SPMD
:
Single Program Multi Data
)
a=a[0]+…+a[24]
a=a[0]+…+a[24]
b
=a[25]+…+a[49]
b
=a[25]+…+a[49]
c
=a[50]+…+a[74]
c
=a[50]+…+a[74]
d
=a[75]+…+a[99]
d
=a[75]+…+a[99]
Y=a+
b
+
c
+
d
Y=a+
b
+
c
+
d
プロセス
0
プロセス
1
プロセス
2
プロセス
3
複数プロセス起動
複数プロセス起動
複数プロセス起動
複数プロセス起動
1
対
対
対
対
1
通信
通信
通信
通信
a=a[0]+…+a[24]
b
=a[25]+…+a[49]
Y=a+
b
+
c
+
d
プロセス
0
プロセス
1
プロセス
0
プロセス
1
送信
受信
データ
送信
受信
データ
全ての通信の基本形
1
対
対
対
対
1
通信を行うための処理
通信を行うための処理
通信を行うための処理
通信を行うための処理
if(RANK==0){
MPI_Send(
sendbuff
, 1, MPI_INT, 1, 1,MPI_COMM_WORLD);
}else if(RANK==1){
MPI_Recv
(
recv
buff
, 1, MPI_INT, 0, 1,MPI_COMM_WORLD, status);
}
RANK1へ、へ、へ、へ、sendbuffををををSend
プロセス
0
プロセス
1
送信
受信
データ
送信
受信
データ
•
同一のプログラムを同時に実行
同一のプログラムを同時に実行
同一のプログラムを同時に実行
同一のプログラムを同時に実行
•
RANK
により、処理を分岐
により、処理を分岐
により、処理を分岐
により、処理を分岐
送受信関数の概要
送受信関数の概要
送受信関数の概要
送受信関数の概要
MPI_Send
(
sendbuff
, 1, MPI_INT, 1, 1,MPI_COMM_WORLD);
MPI_Recv
(
recvbuff
, 1, MPI_INT, 0, 1,MPI_COMM_WORLD, status);
(
送信バッファ
送信バッファ
送信バッファ
送信バッファ
,
サイズ
サイズ
サイズ
サイズ
,
型
型
型
型
,
宛先
宛先
宛先
宛先
,
タグ
タグ
タグ
タグ
,
コミュニケータ
コミュニケータ
コミュニケータ
コミュニケータ
)
(
受信バッファ
受信バッファ
受信バッファ
受信バッファ
,
サイズ
サイズ
サイズ
サイズ
,
型
型
型
型
,
宛先
宛先
宛先
宛先
,
タグ
タグ
タグ
タグ
,
コミュニケータ
コミュニケータ
コミュニケータ
コミュニケータ
,
ステータス
ステータス
ステータス
ステータス
)
※型:(付録参照)
MPI_INT, MPI_REAL
等、
送受信したいバッファの型により変える
※タグ:
同じプロセス同士の通信であっても、
異なる処理を行うための識別子
MPI
を使用するための必須事項
を使用するための必須事項
を使用するための必須事項
を使用するための必須事項
処理 処理処理 処理 ①MPI_Init MPI環境の初期化 ②MPI_Comm_size プロセスの総数取得 ③MPI_Comm_Rank 自ランク取得 ④MPI_Finalize MPI終了処理 (例例例例) RANK0からからからからRANK1へ情報を送信するプログラムへ情報を送信するプログラムへ情報を送信するプログラムへ情報を送信するプログラム1. #include <stdio.h>
2. #include “mpi.h” ←MPI
のためのインクルードファイル
3.
4. int main(int argc, char* argv[]){
5.
int rank, nproc, status;
6.
MPI_Status status;
7.
int buffer, Message=25;
8.
MPI_Init(&argc, &argv);
①
9.
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
②
10.
MPI_Comm_size(MPI_COMM_WORLD, &nproc);
③
11.
12.
13.
if(RANK==0){
14.
MPI_Send( Message, 1, MPI_INT, 1, 1,MPI_COMM_WORLD);
15.
}else if(RANK==1){
16.
MPI_Recv(buffer, 1, MPI_INT, 0, 1,MPI_COMM_WORLD,
&status) ;
17.
}
18.
19.
20.
MPI_Finalize();
④
21.
return 0;
変数 変数変数 変数•
int rank
自ランク番号
•
int nproc
総ランク数
必須のインクルード 必須のインクルード必須のインクルード 必須のインクルードa=a[0]+…+a[24]
b
=a[25]+…+a[49]
c
=a[50]+…+a[74]
d
=a[75]+…+a[99]
Y=a+
b
+
c
+
d
計算の並列化
計算の並列化
計算の並列化
計算の並列化
rank0
rank1
rank2
rank3
並列化プログラム
並列化プログラム
並列化プログラム
並列化プログラム
1. #include <stdio.h> 2. #include "mpi.h"
3. int main(int argc, char* argv[]){ 4. int arr[100];
5. int itr;
6. int nproc; /* Number of proccess */ 7. int rank; /* Number of my rank */ 8. int buf[25]; 9. /* Initialize of MPI */ 10. MPI_Init(&argc, &argv); 11. MPI_Comm_rank( 12. MPI_COMM_WORLD, &rank); 13. MPI_Comm_size( 14. MPI_COMM_WORLD, &nproc); 15. /* 配列arrにデータを格納*/ 16. for(itr=0;itr<100;itr++){ 17. arr[itr]=itr; 18. } 19. if(rank==0){ 20. /* 配列データを各ランクへ配信*/ 21. int dist;
22. for(dist=1; dist<4; dist++){
25. }
26. // bufに入った、25個の、整数型を、 27. // dist番のランクに向かって、 28. // 特定のタグ1を付けて 29. // 送信
30. MPI_Send( buf, 25, MPI_INT, dist, 1, 31. MPI_COMM_WORLD); 32. } 33. for(itr=0;itr<25;itr++){ 34. buf[itr]=arr[itr]; 35. } 36. }else{ 37. /* 0番以外のrank番号を持つプロセス の処理*/ 38. // buf配列に、 39. // 25個の 40. // int型の配列を 41. // プロセス0番から、 42. // タグ1で 43. // 受け取る
44. MPI_Recv( buf, 25, MPI_INT, 0, 1, 45. MPI_COMM_WORLD, 46. MPI_STATUS_IGNORE); 47. } 48. // !!!!!!!!!!!!!!!!!!!!!!!!!! // 49. //並列計算される部分// 52. int sum=0;
53. for(itr=0; itr<25; itr++){ 54. sum=sum+buf[itr]; 55. } 56. printf("RANK=%d,sum=%d¥n",rank,sum); 57. // 各RANKの結果を集計// 58. if(rank == 0){ 59. int sum_other=0; 60. int src; 61. for(src=1; src<4; src++){ 62. MPI_Recv( 63. &sum_other, 1, MPI_INT, src, 2, 64. MPI_COMM_WORLD, 65. MPI_STATUS_IGNORE); 66. sum=sum+sum_other; 67. } 68. printf("SUMMATION=%d¥n",sum); 69. }else{ 70. MPI_Send(&sum, 1, MPI_INT, 0, 2, 71. MPI_COMM_WORLD); 72. } 73. MPI_Finalize(); 74. 75. return 0;
基本的な集団通信
基本的な集団通信
基本的な集団通信
基本的な集団通信
集団通信関数を使用することで、
集団通信関数を使用することで、
集団通信関数を使用することで、
集団通信関数を使用することで、
複数のプロセスがメッセージ交換を一斉に行う
複数のプロセスがメッセージ交換を一斉に行う
複数のプロセスがメッセージ交換を一斉に行う
複数のプロセスがメッセージ交換を一斉に行う
MPI_Scatter
•
1
つの送信元
RANK(Root)
から
•
全プロセスの受信バッファへ
•
決まったサイズのデータを
•
RANK
が小さい順に格納
MPI_Gather
•
全
RANK
の送信バッファから
•
1
つの宛先
RANK(Root)
の受信バッファへ
•
決まったサイズのデータを
•
RANK
が小さい順に格納
RANK 0 RANK 0RANK 0 RANK 1 RANK 2 RANK 3
送信バッファ
送信バッファ
送信バッファ
送信バッファ
送信バッファ
送信バッファ
送信バッファ
送信バッファ
受信バッファ
受信バッファ
受信バッファ
受信バッファ
集団通信を使った足し算プログラム
集団通信を使った足し算プログラム
集団通信を使った足し算プログラム
集団通信を使った足し算プログラム
1. #include <stdio.h> 2. #include "mpi.h"
3. int main(int argc, char* argv[]){ 4. int arr[100]; 5. int itr; 6. int ansr[4]; 7. int sum=0; 8. int nproc; /* 全プロセス数*/ 9. int rank; /* 自分のランク番号*/ 10. int buf[25]; 11. MPI_Init(&argc, &argv); 12. MPI_Comm_rank(MPI_COMM_WORLD, &rank); 13. MPI_Comm_size(MPI_COMM_WORLD, &nproc); 14. if(rank==0){ 15. /* 配列arrにデータを格納*/ 16. for(itr=0;itr<100;itr++){ 17. arr[itr]=itr; 18. } 19. }
20. MPI_Scatter(arr,25,MPI_INT, buf, 25, MPI_INT, 0, 21. MPI_COMM_WORLD);
22. /* 配列の中身を足し合わせ*/ 23. for(itr=0; itr<25; itr++){
24. sum=sum+buf[itr]; 25. }
26. printf("RANK=%d,sum=%d¥n",rank,sum);
27. MPI_Gather(&sum, 1, MPI_INT, ansr, 1, MPI_INT, 0, 28. MPI_COMM_WORLD);
29. if(rank==0){ 30. sum=0;
31. for(itr=0; itr<4; itr++){ 32. sum=sum+ansr[itr]; 33. } 34. printf("sum=%d",sum); 35. } 36. MPI_Finalize(); 37. return 0; 38. }
MPI_Send
MPI_Send//Recv
Recv
に慣れよう!
に慣れよう!
一対一通信を使った
具体例「配列の総和」を
深く理解しよう
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)HPCシステムズ
システムズ
システムズ
システムズ
新規事業企画室
新規事業企画室
新規事業企画室
新規事業企画室
(工学博士)
(工学博士)
(工学博士)
(工学博士)
渡邊
渡邊
渡邊
渡邊
啓正
啓正
啓正
啓正
お話しすること
•
配列の総和
1/2
1/2
1/2
1/2
1/nproc
1/nproc
・・・
・・・
・・・
・・・
rank=0
1
rank=0
1
nproc-1
1/nproc
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)
main() {
MPI
初期化
MPI
終了処理
}
offset, num
の計算
sumup(subA,num[0],&subtotal);
メモリ解放
A
の確保
rank=0
A
の初期化
subA
の確保
A
の後半を
rank=1
へ送信
A
の前半を
subA
にコピー
subtotal
を
rank=1
から受信
answer += subtotal
answer = subtotal
結果テスト
main() {
MPI
初期化
MPI
終了処理
}
offset, num
の計算
sumup(subA,num[1],&subtotal);
メモリ解放
rank=1
subA
の確保
A
の後半を
rank=0
から受信
subtotal
を
rank=0
へ送信
nproc
並列版に変えるには(
1/2
)
•
rank=1
から
/
への処理が
nproc-1
倍に増える
rank=1
への送信
rank=
1..nproc
1..nproc--11
への送信(繰り返し)
rank=1
からの受信
rank=
1..nproc
1..nproc--11
からの受信(繰り返し)
rank=0
rank=
1..nproc
1..nproc--11
rank=0
からの受信
nproc
並列版に変えるには(
2/2
)
•
C
言語でいうと
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)for (
for ( ii = 1;
= 1; ii <
< nproc
nproc;
; ii++ )
++ )
MPI_Send(A+offset[
ii
], num[
ii
],
ii
…);
for (
for ( ii = 1;
= 1; ii <
< nproc
nproc;
; ii++ )
++ )
MPI_Recv(B+offset[
ii
], num[
ii
],
ii
…);
MPI_Recv( A+offset[rank], num[rank], 0…);
MPI_Send( B+offset[rank], num[rank], 0…);
rank=0
rank=
1..nproc
1..nproc--11
main() {
MPI
初期化
MPI
終了処理
}
offset, num
の計算
sumup(subA,num[0],&subtotal);
メモリ解放
A
の確保
rank=0
A
の初期化
subA
の確保
A
の一部を
の一部を
の一部を
の一部を
rank=1..nproc-1
へ送信
へ送信
へ送信
へ送信
A
の一部を
subA
にコピー
subtotal
を
を
を
を
rank=1..nproc-1
から受信
から受信
から受信
から受信
answer += subtotal
answer = subtotal
結果テスト
main() {
MPI
初期化
MPI
終了処理
}
offset, num
の計算
sumup(subA,num[rank],&subtotal);
メモリ解放
rank=1..nproc-1
subA
の確保
A
の一部を
rank=0
から受信
subtotal
を
rank=0
へ送信
MPI
MPI
プログラミング基礎編
プログラミング基礎編
並列プログラムづくりの
イメージを掴もう!
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)HPC
システムズ
システムズ
システムズ
システムズ
新規事業企画室
新規事業企画室
新規事業企画室
新規事業企画室
(工学博士)
(工学博士)
(工学博士)
(工学博士)
渡邊
渡邊
渡邊
渡邊
啓正
啓正
啓正
啓正
お話しすること
•
こうやれば
MPI
を使った並列プログラム を
作れます!
–
「チューニング(効果的な高速化)+並列化」の技法
–
知識と段取りの基本セット
–
「真似して作れる」を目指す
題材
•
行列積
A×B = C
(
matmul-seq.c
)
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)=
・
・
・
・
・
・
・
・
・
・
・
・
・・・
・・・
・・・
・・・
・
・
・
・
A
B
C
N
N
N
105 for (row=0; row<N; row++) {
for (col=0; col<N; col++) {
sum = 0.0;
for (k=0; k<N; k++)
sum += A[row][k] * B[k][col];
C[row][col] = sum;
}
}
複雑な
複雑な
複雑な
複雑な
実アプリでも
実アプリでも
実アプリでも
実アプリでも
「並列化」の
「並列化」の
「並列化」の
「並列化」の
基本は同じ
基本は同じ
基本は同じ
基本は同じ
並列化の一般的な流れ
1.
ホットスポットの特定
2.
計算間の並列性の把握
3.
データ分割方法・粒度の検討
4.
コード編集
5.
コンパイル・リンク
6.
実行
7.
性能評価
•
どの処理に一番時間がかかっているのか?
–
–
そこ
そこ
の高速化がアプリ全体の高速化に効果的!
1.
ホットスポットの特定
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)main(…) {
….;
……….;
…;
…..;
………….;
…;
.;
……;
……..;
…;
…………;
..;
}
0.01
2.20
30.6
30.6
0.05
2.23
0.01
かかった時間
かかった時間
かかった時間
かかった時間
特定方法
1
(簡単)
: gprof
を使う
$ gcc
–pg
foo.c
$ ./a.out
$
gprof
a.out
%
%
%
%
cumulative self
self
self
self
self
total
time
time
time
time
seconds seconds
seconds
seconds
seconds
calls
calls
calls
calls
ms/call ms/call name
name
name
name
77.78
77.78
77.78
77.78
0.07 0.07
0.07
0.07
0.07
4971903
4971903
4971903
4971903
0.00 0.00 mycompare
mycompare
mycompare
mycompare
22.22
22.22
22.22
22.22
0.09 0.02
0.02
0.02
0.02
3769790
3769790
3769790
3769790
0.00 0.00 myswap
myswap
myswap
myswap
0.00 0.09 0.00 117255
117255
117255
117255
0.00 0.00 addToTable
addToTable
addToTable
addToTable
0.00 0.09 0.00 1 0.00 0.00 initresult
0.00 0.09 0.00 1 0.00 88.31 mysort
0.00 0.09 0.00 1 0.00 1.65 validateorder
0.00 0.09 0.00 1 0.00 0.04 validatestability
何%占めるか
何%占めるか
何%占めるか
何%占めるか
実行時間
実行時間
実行時間
実行時間
何回
何回
何回
何回呼ばれたか
呼ばれたか
呼ばれたか
呼ばれたか
関数名
関数名
関数名
関数名
関数ごとの
関数ごとの
関数ごとの
関数ごとの
実行
実行
実行
実行時間統計
時間統計
時間統計
時間統計
特定方法
2
(難しい)
:
ソースコードから考える
•
ソースコードを読んで演算量を見積もる
–
プログラム部位ごとのintやfloatの演算回数
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)プログラム部位
プログラム部位
プログラム部位
プログラム部位
演算回数(オーダー)
演算回数(オーダー)
演算回数(オーダー)
演算回数(オーダー)
入力受付
0
計算時間計測開始
0
メモリ確保
3
初期値設定
3
NN
22
行列積
8
NN
33
+3
NN
22
計算時間計測開始
0
計算時間表示
5
メモリ解放
0
N
が大きいとき
が大きいとき
が大きいとき
が大きいとき
莫大
莫大
莫大
莫大な計算時間を
な計算時間を
な計算時間を
な計算時間を
要する
要する
要する
要する
2.
計算間の並列性の把握
•
並列性:
–
複数の
CPU
へ分担させて
同時に実行しても正しい
計算結果が得られること
•
行列積の場合:
–
各
C[row][col]
の計算は
全て同時に実行して
OK
=
・
・
・
・
・
・
・
・
・
・
・
・
・・・
・・・
・・・
・・・
・
・
・
・
・・・
・・・
・・・
・・・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
=
・
・
・
・
・
・
・
・
・
・
・
・
・・・
・・・
・・・
・・・
・
・
・
・
=
・・・
・・・
・・・
・・・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
同時実行可能!
同時実行可能!
同時実行可能!
同時実行可能!
同時実行可能!
同時実行可能!
同時実行可能!
同時実行可能!
並列性を考えた計算の実例
•
領域分割計算
–
熱伝導シミュレーション
–
N
体問題・粒子シミュレーシ
ョン
–
有限要素法の連立一次方
程式解法
•
パラメータスウィープ計算
・モンテカルロ計算
–
気象予測
–
金融リスク計算
–
積分(面積)の近似解
–
生物データベース検索
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)多数の試行を
多数の試行を
多数の試行を
多数の試行を
多数の試行を
多数の試行を
多数の試行を
多数の試行を
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
相互作用
相互作用
相互作用
相互作用
相互作用
相互作用
相互作用
相互作用のない
のない
のない
のない
のない
のない
のない
のないor
or少ない
少ない
少ない
少ない
少ない
少ない
少ない
少ない
領域に分けて計算を
領域に分けて計算を
領域に分けて計算を
領域に分けて計算を
領域に分けて計算を
領域に分けて計算を
領域に分けて計算を
領域に分けて計算を
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列に実行する形
並列性で詰まったら(その1)
•
データ依存性
–
計算の順序に依って結果が変わる場合
•
for (i=0;i<N;i++) X[i+1] = f(X[i]);
•
打開策
–
並列の粒度を変えてみる
•
処理の呼び出し元自体を並列化できないか?
–
アルゴリズムを根本的に変える
•
データ依存性が少ないアルゴリズムを
誰かが作っているかもしれない
→
論文調査など
X[i]
X[i+1]
X[i+1]
X[i+2]
処理の大きさの単位
処理の大きさの単位
処理の大きさの単位
処理の大きさの単位
処理の大きさの単位
処理の大きさの単位
処理の大きさの単位
処理の大きさの単位
並列性で詰まったら(その2)
•
フロー依存性
–
前のフローに依って実行するかどうかが決まる場合
•
a = BEFORE();
•
if (a == 0) AFTER1(); else AFTER2();
•
打開策
–
投機的実行
•
a
の値に依らず
AFTER1(); AFTER2();
を先走って実行させる
•
a
が決まり次第、結果のどちらかを有効な値とする
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)BEFORE
AFTER1
AFTER2
3.
データ分割方法・粒度の比較検討
•
C[row][col]
の計算達を複数の
CPU
で
どのように分担すればいいか
••
時間のかかるネットワーク通信処理
時間のかかるネットワーク通信処理
を
できるだけ控えよう
–
ローカルメモリアクセス時間 << ネットワーク通信時間
–
データと計算作業をどのように分散させたら
プロセス間の
プロセス間のデータ通信回数・通信量が最少
データ通信回数・通信量が最少
に
なるか?
=
・
・
・
・
・
・
・
・
・
・
・
・
・・
・・
・・
・・
・
・
・
・
・
・
・
・
=
・・
・・
・・
・・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
分割①
1x1
分割(細切れ)
•
通信回数が甚大です(
4N
4N
22
)!!
–
データ通信に対して短い計算=非効率
–
もっと大きめに分割(分担)しましょう
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)=
こりゃあかんわ
こりゃあかんわ
こりゃあかんわ
こりゃあかんわ
…
分割②
A
横
B
縦ブロック分割
•
A
を横に分割、
B
は縦に分割、
C
を横に分割
–
分割はプロセス数分(=P、この図では4)
=
B
[0]
A[0]
C
A[1]
A[2]
A[3]
B
[1]
[2]
B
[3]
B
C C C
C C C C
C C C C
C C C C
分割③
A
横ブロック分割
•
A
を横に分割、
B
はコピー、
C
を横に分割
–
分割はプロセス数分
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)=
B
A[0]
A[0]×
×
×
×B=C[0]
A[1]
A[2]
A[3]
A[1]×
×
×
×B=C[1]
A[2]×
×
×
×B=C[2]
A[3]×
×
×
×B=C[3]
分割方法の比較
分割方法
通信回数
通信量
メモリ使用量
①
1x1
分割
4
NN
22
2
NN
33
+N
2
2N+1
②
A
横
B
縦ブロック分割
2
PP
22
-2
NN
22
(P+3)(P-1)/P
N
2
(2+1/P)/P
③
③
AA
横ブロック分割
横ブロック分割
3
PP
-3
NN
22
(P+2)(P-1)/P
N
2
(1+2/P)
P<<N
状況に応じてなにを重視するかで
最適な戦略を考えましょう
4. MPI
コード製作
1.
主計算ルーチンの切り出し
2. MPI
の定型句
3.
分割データ用メモリの確保
/
開放
4.
データの分配
/
収集
5.
分割データを処理する主計算ルーチン
6.
並列計算結果のテストコード
7.
実行時間を計測するコード
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)main() {
(1) MPI
初期化
(16) MPI
終了処理
(2) A, B, C
の確保・初期化
(4) num[], offset[]
の計算
(3)
計測①
(13)
計算結果のテスト
(8) matmul_sub_parallel(localA, B, N/nproc, N, localC);
(14)
②
-
①の表示
(15) A, B, C
の解放
(5) localA, localC
の確保
(6) A
の分配
(7) B
のコピー
(9) C
の収集
(10) localA, localC
の解放
(12)
計測②
(11) num[], offset[]
の解放
matmul-mpi.c
32
48
64
105
112
125
133
148
161
166
180
186
192
199
211
224
233
主計算ルーチンの切り出し
225 void matmul_sequential(const double *A,
226
const double *B,
227
const int size,
228
double *C) {
229
int row, col, k;
230
double sum;
231
for ( row = 0; row < size; row++ ) {
232
for ( col = 0; col < size; col++ ) {
233
sum = 0.0;
234
for ( k = 0; k < size; k++ ) {
235
sum += *(A + row * size + k)
236
* *(B + k * size + col);
237
}
238
*(C + row * size + col) = sum;
239
}
240
}
241 }
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)•
入出力を明確に
•
後でテストに使う
matmul_
sequential
A B size
C
MPI
の定型句を入れましょう(
1/2
)
static const int root = 0;
// Rank of the master process
MPI_Init(&argc, &argv);
// Initialize MPI system
int nproc;
// The number of processes being used
MPI_Comm_size(MPI_COMM_WORLD, &nproc);
// Calculate nproc
int rank;
// My process number
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
// Calculate rank
nproc=4
rank=0(root)
rank=1
rank=2
rank=3
P
P
P
P
char hostname[MPI_MAX_PROCESSOR_NAME];
int namelen;
MPI_Get_processor_name(hostname, &namelen);
// Hostname
fprintf(stdout, "[%d/%d] %s¥n", rank, nproc, hostname);
fflush(stdout);
// Output immediately
…
(並列コード)
…
MPI_Finalize();
// Finalize MPI system
MPI
の定型句を入れましょう(
2/2
)
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)nproc=4
rank=0 on node00 (CPU0)
rank=1 on node00 (CPU1)
rank=2 on node01 (CPU0)
rank=3 on node01 (CPU1)
P
P
P
P
確認:ちゃんと複数
CPU
コアを
使って動かせているか?
分割データ用メモリの確保
/
開放
int *num = (int *)calloc(sizeof(int), nproc);
int *offset = (int *)calloc(sizeof(int), nproc);
for ( int i = 0; i < nproc; i++ ) {
num[i] = (int)(N * N / nproc);
offset[i] = (int)(N * N / nproc) * i;
}
double *localA = (double *)calloc(sizeof(double), num[rank]);
double *localC = (double *)calloc(sizeof(double), num[rank]);
free(localA);
free(localC);
free(num);
free(offset);
A[0]
N
N/nproc
各プロセスは
各プロセスは
各プロセスは
各プロセスは
A
と
と
と
と
C
を横に
を横に
を横に
を横に
nproc
分割した部分配列を持つ
分割した部分配列を持つ
分割した部分配列を持つ
分割した部分配列を持つ
num[0]
N*N
0
N*N/nproc
offset[0]
管理テーブル(今回は割り切れる場合のみ対応)
A
の分配
ルート(
rank
が
0
のプロセス)が
MPI_Send(A+offset[i], num[i], MPI_DOUBLE, i, ...)
を
nproc
回繰返し,
各プロセスが次の受信を行う
MPI_Recv(localA, num[rank], MPI_DOUBLE, root, ...)
rank
0
1
2
3
A
localA
localA
localA
localA
MPI_Send
x4
MPI_Recv
MPI_Recv
MPI_Recv
MPI_Recv
A[0]
第三回 第三回 第三回
B
のコピー
ルートが
MPI_Send(B, N*N, MPI_DOUBLE, i, ...)
を
nproc-1
回繰返し,
各プロセスが次の受信を行う
MPI_Recv(B, N*N, MPI_DOUBLE, root, ...)
B
rank
0
1
2
3
B
B
B
B
MPI_Send
x3
C
の収集
全プロセスが、
MPI_Send(localC, num[rank], MPI_DOUBLE, root, ...)
を送信し、
ルートが受信を
nproc
回繰り返す
MPI_Recv(C+offset[i], num[i], MPI_DOUBLE, i, ...)
A[0]×
×
×B=C[0]
×
rank
0
1
2
3
C
localC
localC
localC
localC
MPI_Recv
x4
MPI_Send
MPI_Send
MPI_Send
MPI_Send
第三回 第三回 第三回
分割データを処理する主計算ルーチン
void matmul_sub_parallel(const double *A, const double *B,
const int rowsize, const int size, double *C) {
int row, col, k;
double sub;
for ( row = 0; row <
rowsize
; row++ ) {
for ( col = 0; col < size; col++ ) {
sub = 0.0;
for ( k = 0; k < size; k++ ) {
sub += *(A + row * size + k) * *(B + k * size + col);
}
*(C + row * size + col) = sub;
}
}
}
指定された行
指定された行
指定された行
指定された行
まで
まで
まで
まで
やれば
やれば
やれば
やれば
OK
テストコード(逐次の計算結果との比較)
double *testC = (double
*)calloc(sizeof(double), N * N);
matmul_sequential(A, B, N, testC);
double epsiron = 1.0e-5;
BOOLEAN isOK = TRUE;
int i;
for (i = 0;i < N * N;i++) {
double result = *(C + i);
double test = *(testC + i);
if (result > test) {
if ((result - test) > epsiron) {
isOK = FALSE; break;
}
} else {
if ((test - result) > epsiron) {
isOK = FALSE;
break;
}
}
free(testC);
if (isOK == FALSE) {
printf("ERROR: Result is NOT correct!!¥n");
} else {
printf("SUCCESS: Result is correct!!¥n");
}
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)結果が一つ
結果が一つ
結果が一つ
結果が一つでも
でも
でも
でも
違っていたらバグあり
違っていたらバグあり
違っていたらバグあり
違っていたらバグあり
実行時間を計測するコード
•
gettimeofday()
で現在時刻を取得
→
引き算
•
MPI_Barrier()
を使ってプロセス全体を
「よーいどん」させてフェアに測定しよう
MPI_Barrier(MPI_COMM_WORLD);
gettimeofday(&tv1, NULL);
// Do something;
MPI_Barrier(MPI_COMM_WORLD);
gettimeofday(&tv2, NULL);
double elapsed = 0.0;
elapsed += (double)(tv2.tv_sec - tv1.tv_sec);
elapsed += (double)((tv2.tv_usec - tv1.tv_usec) * 1e-6);
rank
0
1
2
3
さらに深く知りたい人は
•
「実践
MPI-2
メッセージパッシング・インタフェース
の上級者向け機能」
–
ウイリアム・グロップほか著、株式会社ピアソン・エデ
ュケーション、
2002
–
ISBN
:
4-89471-444-2
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)一通り
一通り
MPI
MPI
を使って並列プログラム
を使って並列プログラム
を書けるようになった人向け
を書けるようになった人向け
入出力の最適化・動的プロセス等
入出力の最適化・動的プロセス等
5.
コンパイル:
mpicc
–
MPI
ライブラリが自動的にリンクされる
–
gcc
のオプション(
-l
や
-o
)をそのまま使える
6.
実行:
mpirun
> mpirun –np
計算に使う
計算に使う
計算に使う
計算に使う
CPU
コア
コア総数
コア
コア
総数
総数
総数
./a.out
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C) LAN ソフト ソフト ソフト ソフト
ユーザ
ユーザ
ユーザ
ユーザ
クラスタ
クラスタ
クラスタ
クラスタ
並列計算の依頼
並列計算の依頼
並列計算の依頼
並列計算の依頼
複数
複数
複数
複数
CPU
を使って
を使って
を使って
を使って
並列に計算
並列に計算
並列に計算
並列に計算
1.001.86 3.38 4.84 4.87 0 2 4 6 8 10 12 14 16 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
速
度
向
上
率
速
度
向
上
率
速
度
向
上
率
速
度
向
上
率
nproc
Linear matmul-mpi.c 多項式近似7.
性能評価
並列プロセス数
vs.
速度向上
top - 10:24:31 up 88 days, 12:11, 3 users, load average: 0.76, 0.26, 0.32 Tasks: 108 total, 2 running, 106 sleeping, 0 stopped, 0 zombie
Cpu0 : 35.8% us, 27.5% sy, 0.0% ni, 36.7% id, 0.0% wa, 0.0% hi, 0.0% si Cpu1 : 43.9% us, 18.8% sy, 0.0% ni, 35.4% id, 0.0% wa, 0.4% hi, 1.3% si Cpu2 : 84.8% us, 15.2% sy, 0.0% ni, 0.0% id, 0.0% wa, 0.0% hi, 0.0% si Cpu3 : 33.9% us, 30.8% sy, 0.0% ni, 35.3% id, 0.0% wa, 0.0% hi, 0.0% si Mem: 4042060k total, 1508308k used, 2533752k free, 81608k buffers Swap: 2008116k total, 26192k used, 1981924k free, 1202768k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 18549 hi-wata 25 0 238m 30m 2876 R 100 0.8 0:03.29 matmul-mpi.exe 18550 hi-wata 16 0 204m 5980 2664 S 64 0.1 0:02.45 matmul-mpi.exe 18551 hi-wata 25 0 204m 5980 2668 S 63 0.1 0:02.46 matmul-mpi.exe 18552 hi-wata 16 0 204m 5980 2668 S 63 0.1 0:02.44 matmul-mpi.exe
休憩タイム
第三回 第三回 第三回
MPI
環境の構築
•
プロセスと通信の制御
–
例:
メッセージパッシング
ライブラリ
•
LAN
接続
•
セキュリティ情報の共有
•
ファイルの共有
プロセスと
プロセスと
プロセスと
プロセスと
通信の制御
通信の制御
通信の制御
通信の制御
LAN
NIS
NFS
クラスタの機能
クラスタの機能
クラスタの機能
クラスタの機能
OS
クラスタの機能
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)MPI
のソフトウェア実装「
OpenMPI
」
•
メリット:
–
CentOS4
で最初から導入済み
–
きれいにコンポーネント分け
されており,
チューニングや障害解析がやりやすい
–
複数ネットワークデバイスを自動認識
する
•
一斉に
SSH
で遠隔にアプリケーションを起動し,
プロセスと通信路を管理する
Platform Manager™
を使うと簡単!
クラスタハードウェアに
OS
OS
とミドルウェアを自動的にインストール
とミドルウェアを自動的にインストール
してくれるツールです
•
簡単!オールインワン・インタフェース
•
200
以上のワールドワイド・ユーザ企業
•
対応
HW: Dell, HP, IBM, SGI, Sun …
•
対応
OS: RHEL 3,4,5, SLES 9,10, CentOS 4.4-6
OS
OS
ミドルウェア
ミドルウェア
ミドルウェア
ミドルウェア
ミドルウェア
ミドルウェア
ミドルウェア
ミドルウェア
App App
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)クラスタ構築の流れ
①
Linux PC
に
Linux DVD .iso
ファイルをダウンロード
②
Linux PC
に
PM
をインストール
③
PM
を起動
④
PM:
クラスタイメージを作成
⑤
PM:
クラスタイメージをサーバへ配置
⑥ クラスタを運用開始!
LAN
イメージ配置
イメージ配置
イメージ配置
イメージ配置
イメージ配置
イメージ配置
イメージ配置
イメージ配置
PM
PM
MPI
②
③
④
⑤
⑥
①
ネットワーク
ネットワーク構成
構成
ノード数
ノード数
クラスタ名
クラスタ名
[New]
[New]
GUIで簡単クラスタ構築
詳しい資料は
詳しい資料は
詳しい資料は
詳しい資料は
弊社スタッフまで
弊社スタッフまで
弊社スタッフまで
弊社スタッフまで
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)VNC:
リモートデスクトップツール
VNC
クライアントの起動
http://www.realvnc.com/
遠隔に
遠隔に
遠隔に
コンパイル:
mpicc
–
MPI
ライブラリが自動的にリンクされる
–
gcc
のオプション(
-l
や
-o
)をそのまま使える
•
ホームディレクトリでコンパイル(推奨)
–
全ノードで共有されているため
> mpicc matmul-mpi.c
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)実行:
mpirun
•
マシンファイル
–
OpenMPI
で利用対象とするノードの情報
–
/usr/local/openmpi1.2.8-intel91/etc/openmpi-default-hostfile
node01 slots=2
←
←
←
←
ノード上のプロセッサ数
ノード上のプロセッサ数
ノード上のプロセッサ数
ノード上のプロセッサ数
node02 slots=2
node03 slots=2
node04 slots=2
> mpirun --hostfile
マシンファイルのパス
マシンファイルのパス
マシンファイルのパス
マシンファイルのパス
–np
計算に使う
計算に使う
計算に使う
計算に使う
CPU
コア総数
コア総数
コア総数
コア総数
./a.out
おまけ:
rank
割当て変更方法
•
--byslot
幅優先
•
--bynode
深さ優先
> mpirun --hostfile
マシンファイルのパス
マシンファイルのパス
マシンファイルのパス
マシンファイルのパス
–np
計算に使う
計算に使う
計算に使う
計算に使う
CPU
コア総数
コア総数
コア総数
コア総数
--
--byslot
byslot
./a.out
0 1
0 1
2 3
4 5
6 7
0
0
4
11
5
22
6
33
7
node01
node02
node03
node04
node01
node02
node03
node04
第三回 第三回 第三回 第三回MPI実践セミナー実践セミナー実践セミナー実践セミナー Copyright (C)画像ビューア:
GQView
S
休憩タイム
第三回 第三回 第三回