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

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

1 並列・分散ソフトウェア(2)

2 MPI (Message-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

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

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

5 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ライブラリの終了処理

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

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

8 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の場合

9 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のためデッドロック！

10 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の順序を入れ替えてもだめ

11 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); } 双方の順序を逆にする必要

12 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に移行

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

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

15 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\

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

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

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

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

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

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

22 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

23 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

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

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

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

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

28 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)

29 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)

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

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

32 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)

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

34 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

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

36 swim

37 mgrid

38 wupwise

39 applu

40 apsi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58 実行確定条件と制御依存 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 出口

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

60 実行開始条件 ((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に対するデータアクセス可能条件

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

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

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

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

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

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

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

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

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

70 スケジューリング 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 時刻

71 スケジューリング 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 時刻

72 スケジューリング 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 時刻

73 スケジューリング 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 時刻

74 スケジューリング 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 時刻

75 スケジューリング 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 時刻

76 スケジューリング 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 時刻

77 スケジューリング 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 時刻

78 スケジューリング 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 時刻

79 スケジューリング 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 時刻

80 スケジューリング 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 時刻

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

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

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

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

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

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

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

88 データ到達条件の求め方 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

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

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