並列・分散ソフトウェア.

並列・分散ソフトウェア

並列処理のためのソフトウェア開発アルゴリズムプログラミング言語並列化コンパイラ解くべき問題逐次型並列型逐次言語拡張言語
並列言語逐次言語+並列化ライブラリ並列化コンパイラ並列性解析・抽出タスクスケジューリングマシンコード生成 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 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 データの分割配置はプログラマの知的作業として残りの部分をコンパイラに任せる．科学技術計算分野ではそれなりの普及の兆し．
参考となるサイト HPF推進協議会

マルチタスキングによる並列処理 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 @!%\ 2bB! 3cC% 4dD\

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

MPIーまとめ並列プログラミング上級者向け模範実装としてのMPICHが有名([2]) 参考書
「MPI並列プログラミング」培風館 P.パチェコ著，秋葉博訳参考となるサイト [1] [2] [3]

OpenMP 共有メモリ型並列計算機上での並列プログラミングのために，コンパイラ指示文，実行時ライブラリ，環境変数によりベース言語(C, Fortran)を拡張する　1997 Oct. Fortran ver 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; }

和計算のプログラム #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

和計算のプログラム #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でコンパイル

wupwise

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

並列プログラミング現在では完全な自動並列化は困難
計算機アーキテクチャの違いをソフトで埋める努力がされており．違いを意識せずにプログラミングできる環境が整いつつある．共有メモリマシン上での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のデータアクセス可能条件）

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

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 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 時刻

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 時刻

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

データ到達条件の求め方 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」の講義資料ならびに本講義受講生の講義復習用資料として本多弘樹によって制作されたもので，その著作権は本多弘樹に属します．本講義の受講生が，本講義の復習に際し，本スライド閲覧するために本スライドをコピーすることを許可します．上記以外の目的のために，本スライドを閲覧・コピー・改変・配布することを禁じます．

並列・分散ソフトウェア.

Similar presentations

Presentation on theme: "並列・分散ソフトウェア."— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

並列・分散ソフトウェア.

Similar presentations

Presentation on theme: "並列・分散ソフトウェア."— Presentation transcript:

Similar presentations

About project

フィードバック