並列処理論2

Transcription

1 並列処理のためのプログラミング環境 1

2 並列処理プログラミング 解くべき問題 アルゴリズム 逐次型 並列型 プログラミング 逐次言語 拡張言語 並列言語 逐次言語 + 並列化ライブラリ 言語 並列化 コンパイラ 並列性解析 抽出 タスクスケジューリング マシンコード生成 OS 並列コンピュータ 2

3 並列処理プログラミング 解くべき問題 アルゴリズム 逐次型 並列型 プログラミング言語並列化コンパイラ 逐次言語拡張言語並列言語 並列化は行われていない 並列性解析 抽出タスクスケジューリング 逐次言語 + 並列化ライブラリ マシンコード生成 OS 並列コンピュータ 3

4 並列処理プログラミング 解くべき問題 アルゴリズム 逐次型 並列型 人手による 並列化が必要 プログラミング 逐次言語 拡張言語 並列言語 逐次言語 + 並列化ライブラリ 言語 並列化 コンパイラ 並列性解析 抽出 タスクスケジューリング マシンコード生成 OS 並列コンピュータ 4

5 並列処理プログラミング 解くべき問題 並列型アルゴリズムが必要 アルゴリズム 逐次型 並列型 プログラミング言語並列化コンパイラ 逐次言語拡張言語並列性解析 抽出タスクスケジューリング 並列言語逐次言語 + 並列化ライブラリ アルゴリズムの並列性以外の並列化は必要 マシンコード生成 OS 並列コンピュータ 5

6 並列処理プログラミング 解くべき問題 アルゴリズム 逐次型 並列型 並列化は行われていない プログラミング言語並列化コンパイラ 逐次言語拡張言語並列言語逐次言語 + 並列化ライブラリ 並列性解析 抽出 タスクスケジューリング 並列化のすべてをコンパイラが行う マシンコード生成 OS 並列コンピュータ 6

7 並列処理プログラミング 解くべき問題 アルゴリズムプログラミング言語並列化コンパイラ 逐次型逐次言語 並列性解析 抽出タスクスケジューリング 並列型 並列化が行われている 拡張言語並列言語逐次言語 + 並列化ライブラリ 残された並列化をコンパイラが行う マシンコード生成 OS 並列コンピュータ 7

8 並列処理プログラミング 解くべき問題 ( 一部 ) 並列化が行われている アルゴリズム 逐次型 並列化のための書換え 並列型 プログラミング 逐次言語 拡張言語 並列言語 逐次言語 + 並列化ライブラリ 言語 並列化 コンパイラ 並列性解析 抽出 タスクスケジューリング マシンコード生成 OS 並列コンピュータ 8

9 並列処理プログラミングモデル プログラミングモデル ( ソフトウェア的な通信モデル ) の観点からは次の二つに分類される. 共有変数型 ( 単一メモリ空間型 ) メッセージ転送型 9

10 共有変数型 異なるプロセッサ上のプロセス間で変数を共有共有変数を介してプロセス間通信 ポインタ変数などの扱いが楽 共有メモリ型や分散共有メモリ型並列計算機上で用いられることが多い物理的にメモリを共有する必要は必ずしも無い OS サポートなど 分散メモリ型並列計算機での実装では性能低下は大 代入 P0 P1 参照 共有変数 10

11 メッセージ転送型 異なるプロセッサ上のプロセス間での通信手段 メッセージ転送のみ変数のパッキングなどが必要 送信側と受信側のプロセッサが協調してデータ転送 分散メモリ型並列計算機上で用いられることが多い共有メモリ型並列計算機でも実現可能 共有メモリ上に通信チャネルを用意する P0 P1 send receive 11

12 プログラミングモデルと H/W の構成 ハードウェア構成とプログラミングモデルを無関係にしたい. ハードのメモリ制御 ( キャッシュ制御を含む ) 機構や通信制御機構 通信ライブラリ ソフトウェア分散共有メモリ コンパイラ パフォーマンス向上には H/W 構成に適したプログラミングが必要. -PGAS: Partitioned Global Address Space モデル例 ) UPC(Unified Parallel C), CAF(co-Array Fortran) 12

13 並列処理を可能とする OS 環境 並列コンピュータ上での並列処理を実現する OS 機能 プロセス間並列 ( マルチタスキング ) 単一 PE での複数プロセスの並行処理の発展形 プログラム中のタスク群を複数のプロセスに割り当て, それらを複数プロセッサで実行する. スレッド間並列 ( マルチスレッディング ) ひとつのプロセスをさらにスレッドに分割しそれらを複数 PE で実行する. プログラム中のタスク群はスレッド群に割り当て, それらを複数 PE で実行する. 13

14 プロセス間並列 例 ) 1PE での複数プロセスの並行処理 プロセス b プロセス a2 プロセス a1 時間 実行中 アイドルコンテキストスイッチ プロセス生成 14

15 プロセス間並列 例 ) 1PE での複数プロセスの並行処理 プロセス b プロセス a2 プロセス a1 時間 例 ) 2PE での複数プロセスの並列 / 並行処理 プロセス b プロセス a3 PE1 実行中 アイドルコンテキストスイッチ プロセス生成 プロセス a2 プロセス a1 時間 PE2 15

16 プロセス間並列 プロセスの生成 終了 待合せのための機能 fork(), exit(), wait() などの関数 プロセス間データ授受 (IPC) のための機能 データ転送 パイプ, ソケット, メッセージキュー など データ共有共有メモリ領域 : 複数プロセスのメモリ空間の一部をオーバーラップ 同期 シグナル, セマフォ など 各種操作のコストが大きい. プロセス生成, コンテキストスイッチ, 同期, 通信 16

17 スレッド間並列 ( マルチスレッド :MT) スレッド : 同一プロセス内で複数制御フロー ( スレッド ) を用意. 個別の制御フローを個別のスレッドに対応させる. スレッドを PE へのスケジュール単位とする. 同一プロセスのスレッドはアドレス空間を共有. メモリ管理の負荷が小さい 通信 同期のコストが小さい スレッド固有情報 ( プログラムカウンタ, スタックポインタ, レジスタセット ) がプロセス情報 ( アドレス空間, ユーザ ID,etc.) より少ない. スレッド生成や各種操作のコストが小さい. 17

18 スレッド間並列 ( マルチスレッド :MT) スレッド : プロセス b プロセス a スレッド1 スレッド3 スレッド2 スレッド1 PE1 PE2 時間 実行中 アイドルコンテキストスイッチ スレッド生成 18

19 並列プログラミング環境 逐次言語 + マルチタスキング 逐次言語 + マルチスレッド 逐次言語 + メッセージ通信ライブラリ例 ) MPI (Message Passing Interface) 逐次言語 + コンパイラディレクティブ (+α) 例 ) OpenMP,OpenACC 並列言語例 ) HPF (High Performance Fortran) 逐次言語 + 自動並列化コンパイラ 19

20 並列プログラミング環境 参考書 / 例題プログラムの出典 はじめての並列プログラミング 20

21 マルチタスキングによる並列処理 fork システムコールにより複数プロセスを立ち上げての並列処理 ( 並行処理 ) ( 親 ) プロセスが fork 関数を呼び出すと, 子プロセスが生成される. 子プロセス環境は親プロセスの環境が複製される. 親プロセスと子プロセスは fork 関数呼出しから戻ったところからそれぞれ実行を再開. fork 関数の戻り値は, 子プロセスでは 0 となり, 親プロセスでは子プロセスのプロセス ID となる. 子プロセスでは, 処理終了後 exit() システムコールなどでプロセスを終了する. 親プロセス, 子プロセス間では共有変数などを用いてデータの授受を行う. 21

22 マルチタスキング - 例題プログラム #include <sys/shm.h> #include <sys/types.h> #include <sys/ipc.h> #include <stdio.h> pid_t pid1, pid2; int shared_mem_id; int *shared_mem_ptr; int main() { int *rc1, *rc2; int arg1[2] = {1,5}, arg2[2] = {6,10}; int status; 和を部分和として二つのプロセスで求めるプログラム shared_mem_id=shmget(ipc_private, 2*sizeof(int),0666); shared_mem_ptr=shmat(shared_mem_id,0,0); rc1 = shared_mem_ptr; rc2 = (shared_mem_ptr+1); 続く 22

23 マルチタスキング - 例題プログラム if((pid1=fork())==0){ *rc1=sum(&arg1); exit(0); } if((pid2=fork())==0){ *rc2=sum(&arg2); exit(0); } } waitpid(pid1, status, 0); waitpid(pid2, status, 0); 和を部分和として二つのプロセスで求めるプログラム int sum(int *arg_ptr) { int min = *arg_ptr; int max = *(arg_ptr+1); int i, sum; for (i=min,sum =0;i<=max;i++) sum += i; return sum; } printf("%d %d n", *rc1,*rc2); printf("%d+..+%d=%d n", arg1[0],arg2[1], *rc1 + *rc2); 続く 23

24 マルチタスキング - 例題プログラム #include <sys/shm.h> #include <sys/types.h> #include <sys/ipc.h> #include <stdio.h> pid_t pid1, pid2; プロセスID 変数 int shared_mem_id; int *shared_mem_ptr; int main() { int *rc1, *rc2; int arg1[2] = {1,5}, arg2[2] = {6,10}; int status; 和を部分和として二つのプロセスで求めるプログラム ヘッダファイルの読み込み 共有変数管理のための変数 共有変数へのポインタ変数 共有変数領域 ID の確保 shared_mem_id=shmget(ipc_private, 2*sizeof(int),0666); shared_mem_ptr=shmat(shared_mem_id,0,0); rc1 = shared_mem_ptr; rc2 = (shared_mem_ptr+1); 共有変数領域開始アドレス 続く 24

25 マルチタスキング - 例題プログラム 子プロセスを生成 : 戻り値は子プロセスには 0 親プロセスには子プロセス ID if((pid1=fork())==0){ *rc1=sum(&arg1); exit(0); } 和を部分和として二つのプロセスで求めるプログラム 子プロセスなら sum を実行し結果を共有変数へ代入親プロセスは子プロセス ID を得る } if((pid2=fork())==0){ *rc2=sum(&arg2); exit(0); } waitpid(pid1, status, 0); waitpid(pid2, status, 0); 子プロセスなら sum を実行し結果を共有変数へ代入親プロセスは子プロセス ID を得る 子プロセスの終了を待つ 子プロセスの終了を待つ printf("%d %d n", *rc1,*rc2); printf("%d+..+%d=%d n", arg1[0],arg2[1], *rc1 + *rc2); 共有変数を参照する続く 25

26 マルチタスキング - 例題プログラム int sum(int *arg_ptr) { int min = *arg_ptr; int max = *(arg_ptr+1); int i, sum; 和を部分和として二つのプロセスで求めるプログラム } for (i=min, sum =0; i<= max; i++) sum += i; return sum; 26

27 マルチタスキングによる並列処理 プロセス間での 同期 ( セマフォ ): semop 関数など データ授受 : msgsnd/msgrcv 関数など 27

28 マルチスレッディングによる並列処理 スレッドライブラリを使用しスレッドコントロール スレッドライブラリはスレッドコントロールのための API を提供している. 28

29 MT- 例題プログラム #include <pthread.h> #include <stdio.h> extern int *sum(int *); pthread_t th1, th2; 和を部分和として二つのスレッドで求めるプログラム int main() { int *ps1, *ps2; int arg1[2]={1,5}, arg2[2] = {6,10}; pthread_create(&th1,null,(void*(*)(void*))sum,&arg1); pthread_create(&th2,null,(void*(*)(void*))sum,&arg2); pthread_join(th1, (void**)&ps1); pthread_join(th2, (void**)&ps2); } printf("%d+..+%d=%d n", arg1[0], arg2[1], *ps1+*ps2); free(ps1); free(ps2); 続く 29

30 MT- 例題プログラム int *sum(int *arg_ptr) { int lb = *arg_ptr; int ub = *(arg_ptr+1); int i, sum; int *p; 和を部分和として二つのスレッドで求めるプログラム for (i=lb, sum =0; i<= ub; i++) { sum += i;} } p =(int *)malloc(sizeof(int)); *p = sum; return p; 30

31 MT- 例題プログラム #include <pthread.h> #include <stdio.h> extern int *sum(int *); pthread_t th1, th2; スレッド ID 変数 int main() { int *ps1, *ps2; int arg1[2]={1,5}, arg2[2] = {6,10}; 和を部分和として二つのスレッドで求めるプログラム ヘッダファイルの読み込み スレッド開始関数への引数 二つのスレッド生成 スレッド開始関数 pthread_create(&th1,null,(void*(*)(void*))sum,&arg1); pthread_create(&th2,null,(void*(*)(void*))sum,&arg2); } pthread_join(th1, (void**)&ps1); pthread_join(th2, (void**)&ps2); スレッドの終了待ち スレッド終了状態 printf("%d+..+%d=%d n", arg1[0], arg2[1], *ps1+*ps2); free(ps1); free(ps2); 続く 31

32 MT- 例題プログラム int *sum(int *arg_ptr) { int lb = *arg_ptr; int ub = *(arg_ptr+1); int i, sum; int *p; 和を部分和として二つのスレッドで求めるプログラム スレッドローカルな変数 for (i=lb, sum =0; i<= ub; i++) { sum += i;} } p =(int *)malloc(sizeof(int)); *p = sum; return p; p が終了ステータスとして通知される pthread_exit(p); でも OK スレッド外からもアクセスできるように 32

33 マルチスレッディングによる並列処理 スレッド間の同期 相互排除 pthread_mutex_lock(&mt) pthread_mutex_unlock(&mt) pthread_mutex_trylock(&mt) mt は同期変数 : pthread_mutex_t mt 条件同期 pthread_cond_wait(&ct, &mt) pthread_cond_signal(&mt) pthread_cond_broadcast(&mt) ct は同期変数 : pthread_cond_t ct など 33

34 MT- 相互排除 #include <pthread.h> #include <stdio.h> extern int *sum(int *); pthread_t th1, th2; pthread_mutex_t mt = PTHREAD_MUTEX_INITIALIZER; int gsum; int main() { int *ps1, *ps2; int arg1[2]={1,5}, arg2[2] = {6,10}; 和を部分和として二つのスレッドで求めるプログラム または pthread_mutex_init(&mt, NULL); } pthread_create(&th1,null,(void*(*)(void*))sum,&arg1); pthread_create(&th2,null,(void*(*)(void*))sum,&arg2); pthread_join(th1, (void**)&ps1); pthread_join(th2, (void**)&ps2); printf("%d+..+%d=%d n", arg1[0], arg2[1], gsum); free(ps1); free(ps2); 続く 34

35 MT- 相互排除 int *sum(int *arg_ptr) { int lb = *arg_ptr; int ub = *(arg_ptr+1); int i, sum; 和を部分和として二つのスレッドで求めるプログラム for (i=lb, sum =0; i<= ub; i++) { sum += i;} pthread_mutex_lock(&mt); gsum=gsum+sum; pthread_mutex_unlock(&mt); } return 0; 35

36 MPI(Message-Passing Interface) メッセージ通信ライブラリ ( の API 仕様 ) プロセス間でのデータ授受のための通信関数のライブラリ ( 百数十 ) [1]. バージョン 1994 May MPI June MPI 3.1 MPI 4.0 複数プロセスが協調して動作する並列実行モデルプログラム開始時に複数プロセスが一斉に実行を開始し, 一斉に終了する (MPI-1) 例 ) mpirun np 8 my_program [1] MPI Forum 36

37 MPI(Message-Passing Interface) メッセージは次の三つの組で指定される 通信範囲を示すプロセスグループ ( コミュニケータ ) プロセスグループ中でのプロセスID( ランク ) 通信の識別子 ( タグ ) 37

38 MPI ー例題プログラム #include mpi.h int main(int argc, char **argv) { int myrank, error, buffer MPI_Status status; MPI_Init(&argc, &argv); プロセス間でデータを授受するプログラム MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0) { error = MPI_Send(&buffer, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD); } else if (myrank == 1) { error = MPI_Recv(&buffer, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); } MPI_Finalize(); } 38

39 MPI ー例題プログラム #include mpi.h int main(int argc, char **argv) { int myrank, error, buffer } MPI_Status status; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0) { MPI プログラムの全体の枠組み ヘッダファイルの読み込み MPI ライブラリの初期化 error = MPI_Send(&buffer, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD); } else if (myrank == 1) { error = MPI_Recv(&buffer, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); } MPI_Finalize(); MPIライブラリの終了処理 39

40 MPI ー例題プログラム #include mpi.h int main(int argc, char **argv) { int myrank, error, buffer MPI_Status status; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0) { error = MPI_Send(&buffer, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD); } else if (myrank == 1) { メッセージの送受信送受信で指定する情報 バッファの指定 : 先頭アドレス, 個数, 型 相手と文脈の指定 : ランク, タグ, コミュニケータ error = MPI_Recv(&buffer, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); } MPI_Finalize(); } 40

41 MPI ー例題プログラム #include mpi.h int main(int argc, char **argv) { int myrank, error, buffer MPI_Status status; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0) { error = MPI_Send(&buffer, 1, MPI_INT, } } else if (myrank == 1) { } 1, 1234, MPI_COMM_WORLD); error = MPI_Recv(&buffer, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); MPI_Finalize(); メッセージの送受信送受信で指定する情報 バッファの指定 : 先頭アドレス, 個数, 型 相手と文脈の指定 : ランク, タグ, コミュニケータ 受信状態 受信メッセージのランクやタグ ( ワイルドカード受信の際に利用 ) など 41

42 MPI ー例題プログラム #include mpi.h int main(int argc, char **argv) { int myrank, error, buffer MPI_Status status; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0) { error = MPI_Send(&buffer, 1, MPI_INT, } else if (myrank == 1) { プロセスの識別プログラム中の各プロセスにランクが付加されそれで区別する 自プロセスのランクの取得 自分のランクが 0 の場合 1, 1234, MPI_COMM_WORLD); 自分のランクが 1 の場合 error = MPI_Recv(&buffer, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); } MPI_Finalize(); } 42

43 MPI ー双方向通信例題プログラム 双方向送受信をしたい. 次のコードは動作するか? if (myrank == 0) { MPI_Send(&sb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD); MPI_Recv(&rb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD, &status); } else if (myrank == 1) { MPI_Send(&sb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD); MPI_Recv(&rb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); } ブロッキング send/receive のためデッドロック! 43

44 MPI ー双方向通信例題プログラム 双方向送受信をしたい. 次のコードは動作するか? if (myrank == 0) { MPI_Recv(&rb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD, &status); MPI_Send(&sb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD); } else if (myrank == 1) { MPI_Recv(&rb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); MPI_Send(&sb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD); } send/receive の順序を入れ替えてもだめ 44

45 MPI ー双方向通信例題プログラム 双方向送受信をしたい. 次のコードは動作するか? if (myrank == 0) { MPI_Send(&sb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD); MPI_Recv(&rb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD, &status); } else if (myrank == 1) { MPI_Recv(&rb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); MPI_Send(&sb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD); } 双方の順序を逆にする必要 45

46 MPI ー双方向通信例題プログラム ノンブロッキングの Isend と Wait if (myrank == 0) { MPI_Isend(&sb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD, &id); MPI_Recv(&rb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD, &rstatus); MPI_Wait(&id, &wstatus); } else if (myrank == 1) { MPI_Isend(&sb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &id); MPI_Recv(&rb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); MPI_Wait(&id, &wstatus); } Isend ではブロッキングせずに receive に移行 46

47 MPI ー双方向通信例題プログラム 双方向送受信を指示する関数 if (myrank == 0) { MPI_Sendrecv(&sb, 1, MPI_INT, 1, 1234, &rb, 1, MPI_INT, 1, 1234, MPI_COMM_WORLD, &status); } else if (myrank == 1) { } MPI_Sendrecv(&sb, 1, MPI_INT, 0, 1234, &rb, 1, MPI_INT, 0, 1234, MPI_COMM_WORLD, &status); 47

48 MPI ー集団通信関数 典型的な通信パターンに対応する集団通信関数 交換 MPI_Sendrecv ブロードキャスト MPI_Bcast gather MPI_Gather

49 MPI ー集団通信関数 典型的な通信パターンに対応する集団通信関数 scatter MPI_Scatter all gather MPI_Allgather all to all MPI_Alltoall 1234 abcd 1aA@ 2bB! 3cC% 4dD 49

50 MPI ー集団通信関数 集団通信関数の利点 send/receive の組み合わせより プログラムの意図が明確になる ハードウェアで集団通信の機能がある場合, それを利用し MPI 実装であれば通信効率が良い バリア同期関数 MPI_Barrier 50

51 MPI ーまとめ 分散メモリ型並列計算機向きの並列プログラムAPI MPICH2 [3],Open MPI [2] の実装が有名 参考書 MPI 並列プログラミング : P.Pacheco 著, 秋葉博訳 実践 MPI-2: W. Groppほか著畑崎隆雄訳 参考サイト [1] MPI Forum [2] [3] [4] 51

52 OpenMP 共有メモリ型並列計算機上での並列プログラミングのために, コンパイラ指示文, 実行時ライブラリ, 環境変数でベース言語 (C/C++, Fortran) を拡張する. バージョン 1997 Oct. Fortran ver Oct. C/C++ ver July ver Nov. ver. 4.5 並列実行 ( 同期 ) はコンパイラ指示文として記述 ループなどに対しては自動的な負荷分散が可能 52

53 OpenMP コンパイラ指示文 Fortran では directive!$omp... C では pragma #pragma omp... 指示文を無視すれば逐次実行可能 インクリメンタルに並列化が可能 プログラム開発が容易 逐次版と並列版が同じソースで管理できる 53

54 OpenMP ー実行モデル マルチスレッド上での fork-join モデル Parallel Region 複数のスレッドで重複して実行する部分を指定する #pragma omp parallel { sub(); マスタスレッド } fork マスタスレッド スレーブスレッド call sub() call sub() call sub() call sub() join マスタスレッド 54

55 OpenMP ー Parallel Region #pragma omp parallel { 和計算のプログラムスレッドプライベート変数 int chunk,start,end,psum; chunk = 100/omp_get_num_threads(); start = chunk*omp_get_thread_num(); end = start + chunk; psum = 0; for(i=start; i < end; i++) psum += a[i]; #pragma omp atomic sum += psum; } 55

56 OpenMP ー Parallel Region 和計算のプログラム #pragma omp parallel { int chunk,start,end,psum; スレッド数を得る関数 chunk = 100/omp_get_num_threads(); start = chunk*omp_get_thread_num(); end = start + chunk; スレッドIDを得る関数 psum = 0; for(i=start; i < end; i++) psum += a[i]; #pragma omp atomic sum += psum; } k = ceil(n/np) lb= k*(p-1)+1 ub= min(k*p,n) do i=lb,ub ループボディ enddo 56

57 OpenMP ー Parallel Region 和計算のプログラム #pragma omp parallel { int chunk,start,end,psum,i; chunk = ceil((float)100/omp_get_num_threads()); start = chunk*omp_get_thread_num(); end = start + chunk <100? start + chunk : 100; psum = 0; for(i=start; i < end; i++) psum += a[i]; #pragma omp atomic sum += psum; } k = ceil(n/np) lb= k*(p-1)+1 ub= min(k*p,n) do i=lb,ub ループボディ enddo 57

58 OpenMP ー変数の共有 int i; int j; #pragma omp parallel { int k; i =.. j =.. k =.. スレッド間シェアード変数 } スレッドプライベート変数 58

59 OpenMP ー変数の共有 int i; int j; #pragma omp parallel private(j) { int k; スレッド間シェアード変数 i =.. j =.. k =.. } スレッドプライベート変数 59

60 OpenMP ー Work sharing Parallel region 内で複数のスレッドで分担して実行する部分を指定する #pragma omp sections { #pragma omp section { sub1(); } #pragma omp section } { sub2(); } sections の最後でバリア同期 60

61 OpenMP ー Work sharing Parallel region 内で複数のスレッドで分担して実行する部分を指定する 並列ループ #pragma omp for for ( ; ; ) { } スケジューリング : スタティック, ダイナミック (chunk, guided) を指定可 schedule(static, チャンクサイズ ) schedule(dynamic, チャンクサイズ ) schedule(guided, チャンクサイズ ) schedule(runtime) for の最後でバリア同期 61

62 OpenMP ー Work sharing 並列ループ ループの制御変数は自動的にスレッドプライベート変数に #pragma omp for for (i=0; i<n; i++) a[i]=b[i]+c[i]; スレッドプライベート変数の明示が必要 #pragma omp for private(t) for (i=0; i<n; i++){ t=b[i]+c[i]; a[i]=t/2; } 62

63 OpenMP ー Work sharing 並列ループ ループの制御変数は自動的にスレッドプライベート変数に #pragma omp for for (i=0; i<n; i++) a[i]=b[i]+c[i]; #pragma omp for for (i=0; i<n; i++) for (j=0; j<n; j++) スレッドプライベート変数の明示が必要 private(j) a[i][j]=b[i][j]+c[i][j]; 63

64 OpenMP ー同期 バリア同期チーム内のスレッドがバリアに到達するまで待つ #pragma omp barrier クリティカルセクション #pragma omp critical { } アトミック命令メモリの更新をアトミックに行う #pragma omp atomic 文 (x++, x+=..., など ) マスタスレッドのみ実行他のスレッドは素通り #pragma omp master { } 64

65 OpenMP ー同期 単一のスレッドのみ実行他のスレッドはバリア同期で待っている #pragma omp single { } paralle for のボディの一部を逐次と同順で実行 #pragma omp for ordered... #pragma omp ordered { } メモリの一貫性保障 #pragma omp flush( 変数名 ) メモリコンシステンシモデルは weak consistency 65

66 OpenMP ー実行時ライブラリ ( 逐次内で ) 次の parallel region でのスレッド数を指定 omp_set_num_threads(int) parallel region 内で動作中のスレッド数を返す omp_get_num_threads() 利用できるスレッド数を返す omp_get_max_threads() スレッド id を返す omp_get_thread_num() 利用できるプロセッサ数を返す omp_get_num_procs() lock 関数 omp_set_lock(omp_lock_t) omp_unset_lock(omp_lock_t) 66

67 OpenMP ー環境変数 parallel region でのスレッド数を指定 OMP_NUM_THREADS 並列ループのスケジューリング方法を指定 OMP_SCHEDULE 67

68 OpenMP 共有メモリ型並列計算機向きの並列実行モデルと API インクリメンタルな並列化をサポート 参考書 OpenMP 入門北山洋幸著 C/C++ フ ロク ラマーのための OpenMP 並列フ ロク ラミンク ( 第 2 版 ) 菅原清文著 並列フ ロク ラミンク 入門 : サンフ ルフ ロク ラムで学ぶ OpenMP と OpenACC 片桐孝洋著 gcc(ver. 4.2~) でもサポート 68

69 OpenACC 主にアクセラレータ ( 例 :GPU) の並列プログラミングのために, コンパイラ指示文, 実行時ライブラリ, 環境変数でベース言語 (C/C++,Fortran) を拡張する. バージョン ( 原型 :PGI Accelerator Programming Model) 2011 Nov. ver Oct. ver Nov. ver. 2.6 並列実行 ( 同期 ) はコンパイラ指示文として記述 ループなどに対しては自動的な負荷分散が可能 69

70 OpenACC OpenMPと同じアプローチ コンパイラ指示文 指示文を無視すれば逐次実行可能 GPU 等のアクセラレータ特有の性質に対応 並列ループをオフロード ( アクセラレータに任す ) CPUメモリとGPUメモリ間でのデータ転送 CPU GPU メインメモリ デバイスモリ 70

71 OpenACC オフロードしたい並列ループの指定 while(err > s) { #pragma acc kernels for (i=0; i<n; i++){ } t[i]= a[i] ; #pragma acc kernels for (i=0:, i<n; i++){ } } a[i]= t[i] ; GPU 用コードの生成データ転送コードの生成 CPU->GPU: a[] GPU->CPU: t[] GPU 用コードの生成データ転送コードの生成 CPU->GPU: t[] GPU->CPU: a[] 71

72 OpenACC 明示的なデータ転送指定 #pragma acc data copy(a), create(t) while(err > s) { #pragma acc kernels for (i=0; i<n; i++){ } t[i]= a[i] ; #pragma acc kernels for (i=0:, i<n; i++){ } } a[i]= t[i] ; データ転送コードの生成 CPU->GPU: a[] while 前 GPU->CPU: a[] while 後 GPU 内に配置する t[] 72

73 OpenACC アクセラレータ用の並列実行モデルと API CUDA,OpenCL といった低レベルでの GPU プログラミングが不要 プログラムのポータビリティの向上 gcc(ver. 5.1~) でもサポート 73

74 HPF(High Performance Fortran) 分散メモリ並列計算機での科学技術計算を対象 分散メモリ上へのデータ分割配置に主眼を置く. データアクセスの局所性を高める. プロセッサ間通信を減らす. データ分割をプログラマが明示的に指示する. プログラムの SPMD 化や通信コードの挿入はコンパイラが行う. SPMD(Single Program Multiple Data Stream) : 各プロセッサは同一プログラムを実行するが, プロセッサIDなどに基づき異なるコード ( 異なるイタレーションや異なるプログラム部分など ) を実行するモデル. 74

75 HPF ーデータの分割配置 分散メモリ並列計算機でのデータの分散配置例 ) 配列変数 X(100) ブロック分割プロセッサ 1 X(1)~X(25) プロセッサ 2 X(26)~X(50) プロセッサ 3 X(51)~X(75) プロセッサ 4 X(76)~X(100) サイクリック分割プロセッサ 1 X(1),X(5)...X(97) プロセッサ 2 X(2),X(6)...X(98) プロセッサ 3 X(3),X(7)...X(99) プロセッサ 4 X(4),X(8)...X(100) データの分割方法の違いによって並列処理の効率に大きな影響が現れる. 75

76 HPF ーデータの分割配置 PROGRAM EXAMPLE1 PARAMETER(N=100) REAL X(N), Y(N)!HPF$ PROCESSORS P(4)!HPF$ DISTRIBUTE X(BLOCK) ONTO P!HPF$ DISTRIBUTE Y(BLOCK) ONTO P DO I=2,N-1 Y(I) = X(I-1)+X(I)+X(I+1) ENDDO プロセッサ 1 X(1:25) Y(1:25) プロセッサ 2 X(26:50) Y(26:50) 抽象プロセッサ配列宣言 抽象プロセッサへの データレイアウト指定 プロセッサ 3 X(51:75) Y(51:75) プロセッサ 4 X(76:100) Y(76:100) 76

77 HPF ー計算処理のプロセッサへの割り当て owner computes rule: 変数 X へ代入を行う代入文の計算は, その変数がローカルメモリに配置されているプロセッサ (X のオーナー ) が担当するという計算モデル. 先の例示プログラムでは : DO I=2,N-1 Y(I) = X(I-1)+X(I)+X(I+1) END DO プロセッサ 1 が I=2,25 を実行プロセッサ 2 が I=26,50 を実行プロセッサ 3 が I=51,75 を実行プロセッサ 4 が I=76,99 を実行 77

78 HPF ー SPMD コード コンパイラが IF 文からなる実行ガードを挿入し SPMD コードを生成. 各プロセッサは同一プログラムを実行しながら, 実際には異なる処理を行う. 先の例示プログラムでは, コンパイラが以下のようなコードを生成する. DO I=2,N-1 IF( Y(I) のオーナー ) THEN Y(I) = X(I-1)+X(I)+X(I+1) END DO 78

79 HPF ーデータの分割配置 ( 多次元配列 ) PROGRAM EXAMPLE2 PARAMETER(N=100) REAL Z(N,N)!HPF$ PROCESSORS P(4) 抽象プロセッサ配列宣言!HPF$ DISTRIBUTE Z(BLOCK,*) ONTO P 配列変数 Z 抽象プロセッサへの データレイアウト指定 プロセッサ 1 プロセッサ 2 プロセッサ 3 プロセッサ 4 79

80 HPF ーデータの分割配置 ( 多次元配列 )!HPF$ PROCESSORS P(4)!HPF$ PROCESSORS P(2,2) (BLOCK,*) (*,BLOCK) (BLOCK,BLOCK) (SYCLIC,*) (*,SYCLIC) (SYCLIC,BLOCK) 80

81 HPF ーデータの分割配置 ( 相互関係 )!HPF$ ALIGN A(I) WITH B(I) A B!HPF$ ALIGN A(I) WITH B(I+1) A B!HPF$ ALIGN A(I,J) WITH B(J,I) 転置!HPF$ ALIGN A(I,*) WITH C(I) 縮退!HPF$ ALIGN C(I) WITH B(I,*) 複製 81

82 HPF ープロセッサ間通信 先のプログラムで必要な通信 プロセッサ1が, Y(25) = X(24)+X(25)+X(26) プロセッサ2からを実行する際にプロセッサ間でデータの通信が必要データ配置プロセッサ1 X(1)~X(25) プロセッサ2 X(26)~X(50) プロセッサ3 X(51)~X(75) プロセッサ4 X(76)~X(100) プロセッサ2,3,4でも同様プロセッサ2が Y(26) = X(25)+X(26)+X(27) Y(50) = X(49)+X(50)+X(51) プロセッサ 3 が DO I=2,N-1 Y(I)=X(I-1)+X(I)+X(I+1) END DO Y(51) = X(50)+X(51)+X(52) Y(75) = X(74)+X(75)+X(76) プロセッサ4が Y(76) = X(75)+X(76)+X(77) 合計 6 回の通信が必要 82

83 HPF ープロセッサ間通信 DO I=2,N-1 Y(I)=X(I-1)+X(I)+X(I+1) END DO 例示プログラムで, データ分割配置がサイクリックの場合どのような通信が必要か? プロセッサ 1 X(1),X(5)...X(97) プロセッサ 2 X(2),X(6)...X(98) プロセッサ 3 X(3),X(7)...X(99) プロセッサ 4 X(4),X(8)...X(100) 非常に多くの通信が必要となる!!! 全てのプロセッサが一つの代入文で 2 回づつ (98X2 回!) Y(I) = X(I-1)+X(I)+X(I+1) データの分割配置の形態によって通信回数が大きく異なる. 実行効率に多大な影響 83

84 HPF ープロセッサ間での計算負荷の均等化 負荷分散の面からはサイクリック分割の方が良い場合 DO I = 1,100 ENDDO DO J = I,100 X(I,J) = X(I,J)/2 ENDDO J J I I ブロック分割 サイクリック分割 84

85 HPF データの分割配置はプログラマの知的作業とし, 残りの部分 (SPMD 化など ) をコンパイラに任せる. 科学技術計算分野ではそれなりの普及の兆し. 参考となるサイト HPF 推進協議会 XcalableMP 85