並列・分散ソフトウェア

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

並列処理のためのソフトウェア開発 人手による 並列化が必要 アルゴリズム プログラミング 言語 並列化は行われていない 並列化 コンパイラ 解くべき問題 人手による 並列化が必要 アルゴリズム 逐次型 並列型 プログラミング 言語 逐次言語 拡張言語 並列言語 逐次言語+並列化ライブラリ 並列化は行われていない 並列化 コンパイラ 並列性解析・抽出 タスクスケジューリング マシンコード生成 OS 並列処理マシン

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

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

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

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

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

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

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

プログラミングモデルとH/Wの構成 ハードウェアの構成とプログラミングモデルは無関係になりつつある． ハードのメモリ制御(キャッシュ制御を含む)機構や通信制御機構 通信ライブラリ ソフトウェア分散共有メモリ コンパイラ パフォーマンス向上にはH/W構成に適したプログラミングが必要．

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

プロセス間並列 例)単一プロセッサでの二つのプロセスの並行処理 実行中 プロセスb アイドル プロセスa2 コンテクスト スイッチ プロセス生成 時間

プロセス間並列 例)単一プロセッサでの二つのプロセスの並行処理 例)2プロセッサでの並列処理 実行中 プロセスb アイドル プロセスa2 コンテクスト スイッチ プロセスa1 プロセス生成 時間 プロセスb プロセッサ1 プロセスa3 プロセスa2 プロセッサ2 プロセスa1 時間

プロセス間並列 プロセスの生成・終了・待ち合わせ機能 fork(), exit(), wait()などの関数 プロセス間でのデータの授受(IPC)のための機能 プロセス間データ転送 パイプやソケット，メッセージキューなど プロセス間データ共有 共有メモリ領域：各プロセスのメモリ空間の一部をオーバーラップさせ共有メモリ領域を提供 プロセス間同期 シグナル，セマフォなど プロセスによる並列処理では各種操作(プロセス生成，コンテクストスイッチ，同期や通信)のコストが大きい．

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

スレッド間並列(マルチスレッド:MT) スレッド： 実際のスレッドのプロセッサへの割当は もう少し複雑 プロセスb スレッド1 プロセッサ1 スレッド3 プロセスa スレッド2 プロセッサ2 スレッド1 実行中 時間 アイドル 　実際のスレッドのプロセッサへの割当は もう少し複雑 　　 コンテクスト スイッチ スレッド生成

並列プログラミングの方法 並列言語 例) HPF (High Performance Fortran) 逐次言語 + メッセージ通信ライブラリ 例) MPI (Messaga-Passing Interface) 逐次言語 + マルチタスキング 逐次言語 + スレッドライブラリ 例) pthread スレッド機能が組み込まれた逐次言語 　 例) Java 逐次言語 + コンパイラディレクティブ(+α) 例) OpenMP 逐次言語 + 自動並列化コンパイラ

並列プログラミングの方法 　参考書/例題プログラムの出典 　 　bit 1998年6月号別冊/共立出版 　　「はじめての並列プログラミング｣

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

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) データの分割方法の違いによって並列処理の効率に大きな影響が現れる．

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)

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 を実行

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

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

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

!HPF$ ALIGN A(I) WITH B(I) !HPF$ ALIGN A(I) WITH B(I+1) !HPF$ ALIGN A(I,J) WITH B(J,I) 転置 !HPF$ ALIGN A(I,*) WITH C(I)　　　縮退 !HPF$ ALIGN C(I) WITH B(I,*)　　　複製

HPFープロセッサ間通信 先の例示プログラムで必要な通信 プロセッサ1が， Y(25) = X(24)+X(25)+X(26) を実行する際にプロセッサ間でデータの通信が必要 データ配置　プロセッサ1 X(1)～X(25) 　　　　　　　　プロセッサ2 X(26)～X(50) 　　　　　　　　プロセッサ3 X(51)～X(75) 　　　　　　　　プロセッサ4 X(76)～X(100) プロセッサ2,3,4でも同様(どのような通信が必要か？) プロセッサ2から プロセッサ2が Y(26) = X(25)+X(26)+X(27) Y(50) = X(49)+X(50)+X(51) プロセッサ3が 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回の通信が必要

HPFープロセッサ間通信 例示プログラムで，データ分割配置がサイクリックの場合どのような通信が必要か? プロセッサ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)

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

HPF データの分割配置はプログラマの知的作業として残りの部分をコンパイラに任せる． 科学技術計算分野ではそれなりの普及の兆し． 参考となるサイト http://www.hpfpc.jp/ HPF推進協議会 http://www.tokyo.rist.or.jp/jahpf/ http://dacnet.rice.edu/Depts/CRPC/HPFF/

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

マルチタスキング－例題プログラム 和を部分和として二つの プロセスで求めるプログラム 続く #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); 続く

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

マルチタスキング－例題プログラム 和を部分和として二つの プロセスで求めるプログラム ヘッダファイルの読み込み プロセスID変数 #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); ヘッダファイルの読み込み プロセスID変数 共有変数管理のための変数 共有変数へのポインタ変数 共有変数領域IDの確保 共有変数領域開始アドレス 続く

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

マルチタスキング－例題プログラム 和を部分和として二つの プロセスで求めるプログラム 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; }

マルチタスキングによる並列処理 プロセス間での同期のためにセマフォを実現するsemop関数などや，データ授受のためのmsgsnd/msgrcv関数などもある． SMPシステムでの単一プログラムの並列処理では，次に紹介するマルチスレッドによる方法の方が一般的．

マルチスレッドプログラミング スレッドライブラリを使用してじかにスレッドのコントロールをしての並列プログラミング． スレッドライブラリはスレッドコントロールのためのAPIを提供している． スレッドライブラリはいくつか存在するが，定番はpthread．

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); } 続く

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; }

MT－例題プログラム 和を部分和として二つの スレッドで求めるプログラム ヘッダファイルの読み込み スレッドID変数 #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); } ヘッダファイルの読み込み スレッドID変数 二つのスレッド生成 スレッド開始関数への引数 スレッド開始関数 スレッドの終了待ち スレッド終了状態 続く

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

マルチスレッドプログラミング スレッド間の同期 相互排除 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 など

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_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);　 } または pthread_mutex_init(&mt, NULL); 続く

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; }

MT－条件同期 pthread_mutex_t mt = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t ct = PTHREAD_COND_INITIALIZER; int flag; または pthread_cond_init(&ct, NULL); thread 0 ... pthread_mutex_lock(&mt); flag = 1; pthread_mutex_unlock(&mt); pthread_cond_signal(ct); thread 1 ... pthread_mutex_lock(&mt); whiel(flag == 0){ pthread_cond_wait(&ct, &mt); } pthread_mutex_unlock(&mt);

マルチスレッドプログラミング かなり玄人向けの方法 他の方法で並列プログラミングするとしても，スレッドのメカニズムは理解しておくほうが良い． 参考書 ｢実践マルチスレッドプログラミング｣アスキー出版局 S.Kleimanら/岩本信一訳　 「Pスレッドプログラミング」ピアソン・エデュケーション B.Lewisら/岩本信一訳　など

MPI(Messaga-Passing Interface) メッセージ通信ライブラリ(のAPI仕様) プロセス間でのデータのやり取りで使用される通信関数のライブラリ(百数十)． 　　1994 May MPI-1.0 　　1995 June MPI-1.1 　　1997 June MPI-2.0, MPI-1.2 複数プロセスが協調して動作する並列実行モデル プログラム開始時に複数プロセスが一斉に実行を開始し，一斉に終了する(MPI-1) 例) mpirun –np 8 my_program

MPI(Messaga-Passing Interface) デッドロックなどに対してはプログラマが注意を払わなくてはならない メッセージは次の三つの組で指定される 通信を行う範囲を示すプロセスグループ(コミュニケータ) その中でのプロセスのID(ランク) タグ

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();

MPIー例題プログラム MPIプログラムの全体の枠組み ヘッダファイルの読み込み MPIライブラリの初期化 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(); ヘッダファイルの読み込み MPIライブラリの初期化 MPIライブラリの終了処理

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(); バッファの指定：先頭アドレス,個数,型 相手と文脈の指定：ランク,タグ,コミュニケータ

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(); バッファの指定：先頭アドレス,個数,型 相手と文脈の指定：ランク,タグ,コミュニケータ 受信状態 受信メッセージのランクやタグ(ワイルドカード受信の際に利用)など

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(); 自プロセスのランクの取得 自分のランクが0の場合 自分のランクが1の場合

MPIー双方向通信例題プログラム 双方向送受信の場合，以下のコードは動作するか？ ブロッキングsend/receiveのためデッドロック！ 　双方向送受信の場合，以下のコードは動作するか？ 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) { 0, 1234, MPI_COMM_WORLD); 0, 1234, MPI_COMM_WORLD, &status); } ブロッキングsend/receiveのためデッドロック！

MPIー双方向通信例題プログラム 双方向送受信の場合，以下のコードは動作するか？ send/receiveの順序を入れ替えてもだめ 　双方向送受信の場合，以下のコードは動作するか？ 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) { 0, 1234, MPI_COMM_WORLD, &status); 0, 1234, MPI_COMM_WORLD); } send/receiveの順序を入れ替えてもだめ

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) { 0, 1234, MPI_COMM_WORLD, &status); 0, 1234, MPI_COMM_WORLD); } 双方の順序を逆にする必要

MPIー双方向通信例題プログラム ノンブロッキングのIsendとWait Isendではブロッキングせずにreceiveに移行 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) { 0, 1234, MPI_COMM_WORLD, &id); 0, 1234, MPI_COMM_WORLD, &status); MPI_Wait(&id, &wstatus); } Isendではブロッキングせずにreceiveに移行

MPIー双方向通信例題プログラム 双方向送受信を指示する関数 if (myrank == 0) { 　双方向送受信を指示する関数 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); }

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

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

MPIー集団通信関数 集団通信関数の利点 send/receiveの組み合わせより プログラムの意図がわかりやすい ハードウェアで集団通信の機能がある場合それが利用される(可能性がある)ので通信効率が良い 同期関数としてはバリアが用意されている MPI_Barrier

MPIーまとめ 並列プログラミング上級者向け 模範実装としてのMPICHが有名([2]) 参考書 「MPI並列プログラミング」培風館 P.パチェコ著，秋葉博訳 参考となるサイト [1] http://www.mpi-forum.org/ [2] http://www.mcs.anl.gov/mpi/ [3] http://www.ppc.nec.co.jp/mpi-j/

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

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

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

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; }

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; } スレッド数を得る関数 スレッドIDを得る関数 k = ceil(n/np) lb= k*(p-1)+1 ub= min(k*p,n) do i=lb,ub ループボディ enddo

OpenMPーParallel Region 和計算のプログラム #pragma omp parallel { int chunk,start,end,psum; chunk = ceil((float)100/omp_get_num_threads()); start = chunk*omp_get_thread_num(); end = start + chunk <10 ? start + chunk : 10; 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

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

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

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

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

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++){ t=b[i]+c[i]; a[i]=t/2; } private(t)

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++) 　　a[i][j]=b[i][j]+c[i][j]; private(j)

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

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

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)

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

OpenMPー実行例 マシン Sun Ultra80, 4CPU(USII 450M 4M-L2), 2Gメモリ (SunOS 5.8 7/01) 対象プログラム Spec CFP2000とSpecOMPから swim, mgrid, wupwise, apsi, applu 入力データ CFP2000のdata/ref/input/*.in

OpenMPー実行例 コンパイラ Sun Forte f95 逐次，自動並列化，OpenMPのコンパイルが可能 Visual KAP for OpenMP 逐次プログラムを自動並列化しOpenMPで出力 コンパイル方法 逐次 S: CFP2000をForteで逐次コンパイル 並列 P: CFP2000をForteで自動並列化コンパイル K: CFP2000をKAPで自動並列化（OpenMP化） 　 Forteでコンパイル O: SpecOMPをForteでコンパイル

swim

mgrid

wupwise

applu

apsi

OpenMP 共有メモリ計算機向きの並列実行モデルとAPIを与えている 並列プログラムからのインクリメンタルな並列化をサポートしている 参考書 「Parallel Programming in OpenMP」 Morgan Kaufmann Publishers, R. Chandraほか著 参考となるサイト http://www.openmp.org/

並列プログラミング 現在では完全な自動並列化は困難 計算機アーキテクチャの違いをソフトで埋める努力がされており．違いを意識せずにプログラミングできる環境が整いつつある． 共有メモリマシン上でのMPI 分散メモリマシン上でのOpenMP パフォーマンスを追及するのであれば，並列計算機のアーキテクチャを理解した上でのプログラミングが必要 当然並列アルゴリズムの考案も必要

マクロデータフロー(MDF)処理 マクロデータフロー処理 実行すべきタスクがif文などにより実行時に決定されるタスク集合に対する並列処理方式 実行すべきタスクが決定されているタスク集合の並列処理に比べ，以下の二点に工夫が必要となる． プログラムの並列性(各タスク間の先行制約)の検出とその表現 スケジューリング スケジューリング等のオーバーヘッドが大いため，基本ブロックやループなど大きい粒度(粗粒度)でタスクを構成する

マクロデータフロー処理 粗粒度並列処理（マクロデータフロー処理)とは・・・ コンパイル時 プログラムをマクロタスク(MT)に分割 制御フローとデータ依存解析 並列性検出(先行制約検出） 並列性を実行開始条件として表現 先行制約が解消した(必要データが揃った)MTをプロセッサへ動的に割当て実行

マクロデータフロー処理 実行時 スケジューラが： マクロタスクの実行開始条件を検査 条件が成立したマクロタスクをプロセッサへ割当て プロセッサ： マクロタスクの実行状況(終了，分岐方向)の報告

マクロデータフロー処理 コンパイル時： プログラムをMTに分割 制御フロー/データ依存解析 マクロフローグラフで表現 マクロフローグラフ 実行時： スケジューラ 各MTの実行開始条件を随時検査 条件が成立したMTをプロセッサに割当て プロセッサ MT終了や分岐方向をスケジューラに通知 マクロフローグラフ 1 2 3 4 5 6 7 8 データ依存 制御フロー 条件分岐 マクロタスク

並列性の検出と表現 タスク間の制御フローと データ依存を解析する マクロフローグラフ(MFG)： 制御フローグラフとデー タ依存グラフを統合した グラフ MFGの制御フローエッジ にはサイクルが無いと仮 定する ＭＴ１ ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ１ タスク ＭＴ7 ＭＴ8 条件分岐 データ依存 ＭＴ9 制御フロー

並列性の検出と表現 タスク間の制御依存を 解析する プログラム依存グラフ： 制御依存とデータ依存 を統合して表現したグラ フ ＭＴ0 ＭＴ10 タスク間の制御依存を 解析する プログラム依存グラフ： 制御依存とデータ依存 を統合して表現したグラ フ ＭＴ１ ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ１ タスク ＭＴ7 ＭＴ8 条件分岐 データ依存 ＭＴ9 制御依存

並列性の検出と表現 ＭＴ0 ＭＴ10 ＭＴ１ ＭＴ１ ＭＴ2 ＭＴ2 ＭＴ3 ＭＴ3 ＭＴ4 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 ＭＴ7 ＭＴ8 ＭＴ9 ＭＴ9

実行開始条件 プログラム依存グラフ(PDG)の問題点： PDFはタスク間の先行制約を表現している しかし，並列実行の際タスクの実行をいつ開始してよいかは表現されていない たとえばMT7はいつ(どのような条件が成立したら)実行開始してよいか？ ＭＴ0 ＭＴ10 ＭＴ１ ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 ＭＴ9

実行開始条件 全てのタスクが実行されるタスク集合では あるタスクの全ての先行タスクが終了すればそのタスクの実行を開始してよい たとえば，タスク7は3, 5, 6が終了した時点で実行開始可能 すなわち，データ依存による先行制約がタスクの実行を開始してよい時点を表現している 3 3 2 1 2 3 2 1 6 4 2 5 2 1 8 7 9

実行開始条件 ＭＴ0 MT7はいつ(どのような条件が成立したら)実行を開始してよいか？ 　　(MT2が3に分岐)　かつ 　　(MT1が終了)　かつ 　　(MT5が終了) 　　したとき実行開始可能． これでよいか？ ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 ＭＴ9 ＭＴ10

実行開始条件 MT7が実行される場合で MT5が実行されない場合も ある ＭＴ0 ＭＴ10 ＭＴ１ ＭＴ１ ＭＴ2 ＭＴ2 ＭＴ3 ＭＴ3 ＭＴ4 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 ＭＴ7 ＭＴ8 ＭＴ9 ＭＴ9

実行開始条件 MT7はいつ実行を開始してよいか？ 　(MT2が3に分岐)　かつ 　(MT1が終了)　かつ 　(MT5が終了） したとき実行開始可能. この条件では，MT5が実行されない場合でもMT5の終了を待ちつづけることとなる． →MT7は永遠に実行できない ＭＴ0 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 ＭＴ9 ＭＴ10

実行開始条件 MT7はいつ実行を開始してよいか？ 　(MT2が3に分岐)　かつ 　(MT1が実行されるなら 　　　　MT1が終了)　かつ 　(MT5が実行されるなら 　　　　MT5が終了） したとき実行開始可能 としなければならない ＭＴ0 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 ＭＴ9 ＭＴ10

実行開始条件 前述の 　　(MT2が3に分岐)∧ 　　(MT1が実行されるならMT1が終了)∧ 　　(MT5が実行されるならMT5が終了） という条件の 　　(MT5が実行されるならMT5が終了） は 　　((MT5が実行されないことが確定する)∨ 　　　　　　　　　　　　　　　　　　　　　　(MT5が終了)) とできる 制御依存とデータ依存による先行制約だけではいつタスクの実行を開始してよいかを表現し得ない． タスクが実行されないことが確定する条件が必要

実行確定条件と制御依存 MTjの実行確定条件： MTjが制御依存するMTから MTjが逆支配するMTへの <分岐方向決定>の論理和 MT2がMT1に制御依存している： 制御フローグラフ上で次の関係が成立 MT1からMT2へ至るパス上の全て のMTがMT2に逆支配されている MT1はMT2に逆支配されていない MT2がMT1に制御依存しているとは： MT1によってMT2を「実行する」ことが決定される MT2の実行確定条件: 1-a∨2-b MT1 MTa MTb MT2 出口

非実行確定条件と補制御依存 MTkの非実行確定条件： MTkが補制御依存するMTから MTkへ至らないパスへの <分岐方向決定>の論理和 MT2がMT1に補制御依存している： 制御フローグラフ上で次の関係が成立 MT1は入口からMT2へ至るパス上にあり MT1は入口からMT2に至るパス外のMTへの分岐を持つ MT2がMT1 に補制御依存しているとは： MT1によってMT2を「実行しない」ことが決定される MT2の非実行確定条件： 1-c 入口 MT1 MTc MT2 出口

実行開始条件 ((MT5が実行されないことが確定する)は (MT2が8に分岐)∨ (MT3が6に分岐)∨ (MT4が6に分岐) ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 MT1に対するデータアクセス可能条件 ＭＴ7 ＭＴ8 MT5の非実行確定条件 (2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) ＭＴ9 MT７の実行確定条件 MT1に対するデータアクセス可能条件

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧ 　　　　　　　　　　　　　（MTiのデータアクセス可能条件）

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） 　MT6の実行開始条件 1 2 3 4 5 6 7 8

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） 　MT6の実行開始条件 1 2 3 4 5 6 7 8

<MT2終了>∨(MT2の非実行確定条件) 実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 <MT終了>と<分岐方向決定>の論理変数を項とする論理式 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） <MT2終了>∨(MT2の非実行確定条件) 　MT6の実行開始条件 1 2 3 4 5 6 7 8

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） 　MT6の実行開始条件 1 2 3 4 5 6 7 8

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） 　MT6の実行開始条件 1 2 3 4 5 6 7 8

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） 　MT6の実行開始条件 1 2 3 4 5 6 7 8

実行開始条件 各MTが実行可能となる(先行制約が解消される)ための条件 MTiの実行開始条件＝ 　　（MTiの実行確定条件）∧（MTiのデータアクセス可能条件） 　MT6の実行開始条件 1 2 3 4 5 6 7 8

スケジューリング スケジューリングにおいてはスケジューラが実行開始条件を更新・検査しながら，ダイナミックにタスクをプロセッサに割当て． スケジューラ：　実行開始条件を評価．条件がtrueとなっているタスク(レディタスク)をアイドルプロセッサに割当てることを繰り返す 各プロセッサ：　割当てられたタスクを実行．分岐方向が決定した際やタスクの実行を終了した際にそのことをスケジューラに通知する スケジューラの機能は特定のプロセッサが集中的に行うか(集中スケジューリング)，各プロセッサが行なうか(分散スケジューリング)のいずれかが考えられる．

スケジューリング PE1 PE2 1 PE3 2 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 実行可能 実行可能 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 ＭＴ9 PE2 1 PE3 2 時刻

スケジューリング PE1 PE2 1 PE3 2 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 ＭＴ9 PE2 1 PE3 2 時刻

スケジューリング PE1 PE2 1 PE3 2 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 ＭＴ9 PE2 1 PE3 2 時刻

スケジューリング PE1 PE2 1 3 PE3 2 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 実行可能 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 ＭＴ9 PE2 1 3 PE3 2 時刻

スケジューリング PE1 PE2 1 3 PE3 2 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 ＭＴ9 PE2 1 3 PE3 2 時刻

スケジューリング PE1 PE2 1 3 4 PE3 2 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 実行可能 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 ＭＴ9 PE2 1 3 4 PE3 2 時刻

スケジューリング PE1 7 PE2 1 3 4 PE3 2 6 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 実行可能 ＭＴ4 実行可能 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 7 ＭＴ9 PE2 1 3 4 PE3 2 6 時刻

スケジューリング PE1 7 9 PE2 1 3 4 PE3 2 6 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 実行可能 ＭＴ7 ＭＴ8 PE1 7 9 ＭＴ9 PE2 1 3 4 PE3 2 6 時刻

スケジューリング PE1 7 9 PE2 1 3 4 PE3 2 6 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 7 9 ＭＴ9 PE2 1 3 4 PE3 2 6 時刻

スケジューリング PE1 7 9 PE2 1 3 4 PE3 2 6 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 ＭＴ7 ＭＴ8 PE1 7 9 ＭＴ9 PE2 1 3 4 PE3 2 6 時刻

スケジューリング PE1 7 9 PE2 1 3 4 PE3 2 6 1:true 2:ture 3:(2-3)∧1 4:(3-4)∧((2-8)∨3) 5:(4-5)∧((2-8)∨(3-6)∨4)∧2 6:((3-6)∨(4-6))∧((2-8)∨3) 7:(2-3)∧1∧((2-8)∨(3-6)∨(4-6)∨5)) 8:(2-8)∧1 9:((2-8)∨7)∧((2-3)∨8)) 10:((2-8)∨(4-5)∨6)∧9 ＭＴ1 ＭＴ2 ＭＴ3 ＭＴ4 ＭＴ5 ＭＴ6 全実行終了 ＭＴ7 ＭＴ8 PE1 7 9 ＭＴ9 PE2 1 3 4 PE3 2 6 時刻

分散メモリ型並列計算機での実現 分散メモリシステム上でのMDFでは： MT間データ授受にメッセージパッシングを用いる 　⇒送信・受信のプロセッサを決定しなくてはならない 変数定義は複数 　⇒どの定義での値を参照すべきか実行時に定まる MT間データ授受関係（変数の定義・参照）の表現が必要 実行開始条件はこれを表現していない あるMTで使用する変数の値を定義 するMTを求めるための方式 　　　データ到達条件 SDSMによる方法も ありうる・・・ 1 a=,c= b= 2 b= 3 c= 4 5 a=,c= =a,b,c 6 7 8

データ到達条件 MTjでのMTiに到達しうる定義(する値)がMTiに実際に到達する条件は： MTjが実行される (実行確定条件） MTjでの定義をkillしうるいかなるMTも実行されない （非実行確定条件） 　　　 start MTj a=, Killer a= a= Killer MTi =a

データ到達条件 MTiに到達する「変数vへの定義」を持つMT集合をDとする MTj∈Dでのvへの定義をkillする定義を持つMT集合をKとする MTiでのvの値が，MTjで定義した値となることが確定する条件 実行時にデータ到達条件が成立するのは，Dの中のただひとつのMTのみ データ到達条件が成立したMTからデータ転送すればよい MTiでのvに対するMTｊのデータ到達条件 （MTjの実行確定条件）∧ （ K中のいかなるMTも実行されない条件） （ K中の各MTの非実行確定条件の論理積）

データ到達条件 MT6でのa,b,cに関するデータ到達条件： 1 a=,c= b= 2 b= 3 c= a=,c= 4 5 =a,b,c 6 7 8

データ到達条件 MT6でのa,b,cに関するデータ到達条件： 1 a=,c= b= 2 b= 3 c= a=,c= 4 5 =a,b,c 6 7 8

データ到達条件 MT6でのa,b,cに関するデータ到達条件： 1 a=,c= b= 2 b= 3 c= a=,c= 4 5 =a,b,c 6 7 8

データ到達条件の求め方 MTiでのvに対するMTｊのデータ到達条件 （MTjの実行確定条件）∧ （ K中の各マクロタスクの非実行確定条件の論理積） 実行確定条件と非実行開始条件を求めればよい ただし，冗長な条件が含まれてしまう 1 a=,c= b= 2 b= 3 c= a=,c= 4 5 =a,b,c 6 7 8

データ到達条件の求め方 MTiでのvに対するMTｊのデータ到達条件 （MTjの実行確定条件）∧ （ K中の各マクロタスクの非実行確定条件の論理積） MTiからMTjに向けて遡る MTの全ての出側エッジに到達した際には入側エッジから遡りを続行 K中のMTまたはMTjに達した際には遡りを停止 それ以上遡れない状態でK中のMT以外に到達した分岐エッジによる分岐条件の論理積が第二項となる start MTj a=,c= a=,c= Killer a=,c= Killer MTi =a,b,c

データ到達条件を用いたMDF コンパイル時にデータ到達条件を求める 実行時にスケジューラは： MTiをプロセッサPiに割当てる際に，データ到達条件を検査 データ到達条件が成立したMTjがプロセッサPjに割当てられている場合，Piにデータ受信，Pjにデータ送信を指示

マクロデータフロー処理 ループレベル並列性を越える自動並列処理方式として注目される 経済産業省ミレニアムプロジェクト(平成12-14) 「アドバンスト並列化コンパイラプロジェクト」 階層的なマクロデータフロー処理の実用化 従来の自動並列処理に比べ最大10倍の性能を達成

本スライドの著作権について 本スライドは，電気通信大学大学院情報システム学研究科で，平成15年度前期に開講される｢並列処理論2」の講義資料ならびに本講義受講生の講義復習用資料として本多弘樹によって制作されたもので，その著作権は本多弘樹に属します． 本講義の受講生が，本講義の復習に際し，本スライド閲覧するために本スライドをコピーすることを許可します． 上記以外の目的のために，本スライドを閲覧・コピー・改変・配布することを禁じます．