タスクスケジューリング 　　　.

Presentation on theme: "タスクスケジューリング 　　　."— Presentation transcript:

1 タスクスケジューリング 　　　

2 タスクスケジューリング タスクのプロセッサへのスケジューリング スケジューリングをいつ行うか： 各プロセッサで実行すべきタスクの決定
各プロセッサ上でのタスクの実行順序の決定 全タスク終了までの時間（実行時間）を短くする 　⇒負荷（計算・通信）の均一化 スケジューリングをいつ行うか： プログラム実行前に行うスタティックスケジューリング 実行すべきタスクと，その処理時間が実行前に得られる場合 →精度の良いスケジューリングが可能 プログラム実行時に行うダイナミックスケジューリング 実行すべきタスクがあらかじめ決まっていない，実行時間の変動が大きいなどの不確定性に対処できる

3 タスクスケジューリング（スタティック） 実行時間最小マルチプロセッサスケジューリング問題
次の前提で実行時間(スケジュール長)を最小にするようなスケジュールを求める問題 能力の等しいm台のプロセッサ 先行制約のあるn個のタスクからなるタスク集合T={T1,T2,...,Tn} 実行すべきタスクは既知 すべてのタスク(T={T1,T2,...,Tn})を実行する 各タスクの処理時間は既知 割込み無し(ノンプリエンプティブ) タスクの処理が開始されたら終了するまで中断されない

4 タスクスケジューリング（スタティック） タスクグラフ：タスク集合の性質を表現 入口ダミーノード 3 3 2 1 2 3 クリティカルパス 2
入口ダミーノード 3 3 2 1 2 3 クリティカルパス 2 1 6 4 先行制約 2 5 青数字：タスク処理時間 2 黒数字：タスク番号 1 8 7 出口ダミーノード 9

5 タスクスケジューリング（スタティック） タスクグラフ：タスク集合の性質を表現 入口ダミーノード 3 3 2 1 2 3 クリティカルパス 2
入口ダミーノード 3 3 2 1 2 3 クリティカルパス 2 1 6 4 先行制約 2 5 青数字：タスク処理時間 2 黒数字：タスク番号 1 8 7 出口ダミーノード 9

6 タスクスケジューリング（スタティック） クリティカルパス：tcr 3 3 1 2 2 3 2 1 4 6 2 5 2 8 1 7 9
各タスクから出口ノードへ至る最長パス 入口ノードのクリティカルパス 理想的な並列処理を行っても入口ノードのクリティカルパスより短い処理時間で並列処理を行うことはできない 3 3 1 2 2 3 2 1 4 6 2 5 2 8 1 7 9 タスクグラフ

7 タスクスケジューリング（スタティック） 実行時間最小マルチプロセッサスケジューリング問題 プロセッサ数 タスク処理時間 先行制約 複雑さ 1
最適解を求めることがきわめて難しい最適化問題 スケジューリング問題の複雑さ プロセッサ数 タスク処理時間 先行制約 複雑さ 1 任意 均一 ツリー O(n) 2 O(n2) 3 NP困難

8 タスクスケジューリング(スタティック) Huのアルゴリズム：問題1に対する最適解を与える 1.タスクにレベルを付加
　1.タスクにレベルを付加 　2.レベルの大きい順に 優先度リストを作成 　　 3,4,5,1,2,7,6,8,9,10 　3.先行タスクが終了し実行 　可能となったタスク中で 　優先度の高いものから 　空プロセッサへ割当て 　→リストスケジューリング 3 4 5 レベル3 1 2 7 レベル2 6 8 9 レベル1 レベル0 10 PE1 PE2 PE3 時刻

9 タスクスケジューリング(スタティック) Huのアルゴリズム：問題1に対する最適解を与える 1.タスクにレベルを付加
　1.タスクにレベルを付加 　2.レベルの大きい順に 優先度リストを作成 　　 3,4,5,1,2,7,6,8,9,10 　3.先行タスクが終了し実行 　可能となったタスク中で 　優先度の高いものから 　空プロセッサへ割当て 　→リストスケジューリング 3 4 5 レベル3 1 2 7 レベル2 6 8 9 レベル1 レベル0 10 PE1 3 PE2 4 PE3 5 時刻

10 タスクスケジューリング(スタティック) Huのアルゴリズム：問題1に対する最適解を与える 1.タスクにレベルを付加
　1.タスクにレベルを付加 　2.レベルの大きい順に 優先度リストを作成 　　 3,4,5,1,2,7,6,8,9,10 　3.先行タスクが終了し実行 　可能となったタスク中で 　優先度の高いものから 　空プロセッサへ割当て 　→リストスケジューリング 3 4 5 レベル3 1 2 7 レベル2 6 8 9 レベル1 レベル0 10 PE1 3 1 PE2 4 2 PE3 5 7 時刻

11 タスクスケジューリング(スタティック) Huのアルゴリズム：問題1に対する最適解を与える 1.タスクにレベルを付加
　1.タスクにレベルを付加 　2.レベルの大きい順に 優先度リストを作成 　　 3,4,5,1,2,7,6,8,9,10 　3.先行タスクが終了し実行 　可能となったタスク中で 　優先度の高いものから 　空プロセッサへ割当て 　→リストスケジューリング 3 4 5 レベル3 1 2 7 レベル2 6 8 9 レベル1 レベル0 10 PE1 3 1 6 PE2 4 2 8 PE3 5 7 9 時刻

12 タスクスケジューリング(スタティック) Huのアルゴリズム：問題1に対する最適解を与える 1.タスクにレベルを付加
　1.タスクにレベルを付加 　2.レベルの大きい順に 優先度リストを作成 　　 3,4,5,1,2,7,6,8,9,10 　3.先行タスクが終了し実行 　可能となったタスク中で 　優先度の高いものから 　空プロセッサへ割当て 　→リストスケジューリング 3 4 5 レベル3 1 2 7 レベル2 6 8 9 レベル1 レベル0 10 PE1 3 1 6 10 PE2 4 2 8 PE3 5 7 9 時刻

13 タスクスケジューリング(スタティック) 実行時間最小マルチプロセッサスケジューリング問題 プロセッサ数 タスク処理時間 先行制約 複雑さ 1
最適解を求めることがきわめて難しい最適化問題 スケジューリング問題の複雑さ プロセッサ数 タスク処理時間 先行制約 複雑さ 1 任意 均一 ツリー O(n) 2 O(n2) 3 NP困難

14 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム： 問題2に対する最適解を与える
1.タスクにレベルを付加 2.レベルの大きい順に 優先度リストを作成 　同一レベルのタスクAとBで 　Aの直接後続タスク集合が 　Bの直接後続タスク集合を包 　含する場合にはAの優先度を 　Bより高くする 3,2,1,5,6,4,7,8,9 3.リストスケジューリング 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 PE1 PE2 時刻

15 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム： 問題2に対する最適解を与える 1.タスクにレベルを付加 2.レベルの大きい順に 優先度リストを作成 　同一レベルのタスクAとBで 　Aの直接後続タスク集合が 　Bの直接後続タスク集合を包 　含する場合にはAの優先度を 　Bより高くする 　3,2,1,5,6,4,7,8,9 3.リストスケジューリング 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 3 PE1 PE2 2 時刻

16 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム： 問題2に対する最適解を与える 1.タスクにレベルを付加 2.レベルの大きい順に 優先度リストを作成 　同一レベルのタスクAとBで 　Aの直接後続タスク集合が 　Bの直接後続タスク集合を包 　含する場合にはAの優先度を 　Bより高くする 　3,2,1,5,6,4,7,8,9 3.リストスケジューリング 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 3 1 PE1 PE2 2 5 時刻

17 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム： 問題2に対する最適解を与える 1.タスクにレベルを付加 2.レベルの大きい順に 優先度リストを作成 　同一レベルのタスクAとBで 　Aの直接後続タスク集合が 　Bの直接後続タスク集合を包 　含する場合にはAの優先度を 　Bより高くする 3,2,1,5,6,4,7,8,9 3.リストスケジューリング 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 3 1 6 PE1 PE2 2 5 4 時刻

18 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム： 問題2に対する最適解を与える 1.タスクにレベルを付加 2.レベルの大きい順に 優先度リストを作成 　同一レベルのタスクAとBで 　Aの直接後続タスク集合が 　Bの直接後続タスク集合を包 　含する場合にはAの優先度を 　Bより高くする 3,2,1,5,6,4,7,8,9 3.リストスケジューリング 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 3 1 6 7 PE1 PE2 2 5 4 8 時刻

19 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム： 問題2に対する最適解を与える 1.タスクにレベルを付加 2.レベルの大きい順に 優先度リストを作成 　同一レベルのタスクAとBで 　Aの直接後続タスク集合が 　Bの直接後続タスク集合を包 　含する場合にはAの優先度を 　Bより高くする 3,2,1,5,6,4,7,8,9 3.リストスケジューリング 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 3 1 6 7 9 PE1 PE2 2 5 4 8 時刻

20 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム での優先度を採用しないと： 1, 2, 3, 4, 5, 6, 7, 8, 9 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 1 PE1 PE2 2 時刻

21 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム での優先度を採用しないと： 1, 2, 3, 4, 5, 6, 7, 8, 9 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 1 3 PE1 PE2 2 時刻

22 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム での優先度を採用しないと： 1, 2, 3, 4, 5, 6, 7, 8, 9 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 1 3 4 PE1 PE2 2 5 時刻

23 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム での優先度を採用しないと： 1, 2, 3, 4, 5, 6, 7, 8, 9 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 1 3 4 6 PE1 PE2 2 5 時刻

24 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム での優先度を採用しないと： 1, 2, 3, 4, 5, 6, 7, 8, 9 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 1 3 4 6 7 PE1 PE2 2 5 8 時刻

25 タスクスケジューリング(スタティック) Coffman & Grahamのアルゴリズム での優先度を採用しないと： 1, 2, 3, 4, 5, 6, 7, 8, 9 1 2 3 レベル3 4 5 6 レベル2 7 8 レベル1 レベル0 9 1 3 4 6 7 9 PE1 PE2 2 5 8 時刻

26 タスクスケジューリング(スタティック) 実行時間最小マルチプロセッサスケジューリング問題 プロセッサ数 タスク処理時間 先行制約 複雑さ 1
最適解を求めることがきわめて難しい最適化問題 スケジューリング問題の複雑さ プロセッサ数 タスク処理時間 先行制約 複雑さ 1 任意 均一 ツリー O(n) 2 O(n2) 3 NP困難

27 タスクスケジューリング(スタティック) クリティカルパス(CP)法： 問題3に対する近似解を与える 1.各タスクのCPを計算する
3.リストスケジューリング 　　 3 3 1 2 2 3 1 2 3 4 5 6 7 8 9 2 1 4 6 2 5 2 8 1 7 PE1 9 PE2 時刻

28 タスクスケジューリング(スタティック) クリティカルパス(CP)法： 問題3に対する近似解を与える 1.各タスクのCPを計算する 2.CPの大きい順に 　優先度リスト作成 　1,2,3,6,4,5,8,7 3.リストスケジューリング 　　 3 3 2 1 1 2 3 4 5 6 7 8 9 2 3 2 1 4 6 2 5 2 8 1 7 PE1 1 9 PE2 2 時刻

29 タスクスケジューリング(スタティック) クリティカルパス(CP)法： 問題3に対する近似解を与える 1.各タスクのCPを計算する 2.CPの大きい順に 　優先度リスト作成 　1,2,3,6,4,5,8,7 3.リストスケジューリング 　　 3 3 2 1 1 2 3 4 5 6 7 8 9 2 3 2 1 4 6 2 5 2 8 1 7 PE1 1 3 9 PE2 2 6 時刻

30 タスクスケジューリング(スタティック) クリティカルパス(CP)法： 問題3に対する近似解を与える 1.各タスクのCPを計算する 2.CPの大きい順に 　優先度リスト作成 　1,2,3,6,4,5,8,7 3.リストスケジューリング 　　 3 3 2 1 1 2 3 4 5 6 7 8 9 2 3 2 1 6 4 2 5 2 8 1 7 PE1 1 3 4 9 PE2 2 6 時刻

31 タスクスケジューリング(スタティック) クリティカルパス(CP)法： 問題3に対する近似解を与える 1.各タスクのCPを計算する 2.CPの大きい順に 　優先度リスト作成 　1,2,3,6,4,5,8,7 3.リストスケジューリング 　　 3 3 2 1 1 2 3 4 5 6 7 8 9 2 3 2 1 6 4 2 5 2 8 1 7 PE1 1 3 4 5 9 PE2 2 6 時刻

32 タスクスケジューリング(スタティック) クリティカルパス(CP)法： 問題3に対する近似解を与える 1.各タスクのCPを計算する 2.CPの大きい順に 　優先度リスト作成 　1,2,3,6,4,5,8,7 3.リストスケジューリング 　 3 3 2 1 1 2 3 4 5 6 7 8 9 2 3 2 1 6 4 2 5 2 1 8 7 PE1 1 3 4 5 8 9 PE2 2 6 7 時刻

33 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 4 5 10 40 7 8 6 30 9 1 PE1 PE2 時刻

34 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 4 5 10 40 7 8 6 30 9 1 PE1 1 PE2 時刻

35 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 4 5 10 40 7 8 6 30 9 1 PE1 1 2 PE2 3 時刻

36 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 7 8 6 30 9 1 PE1 1 2 PE2 3 6 時刻

37 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 7 8 6 30 9 1 PE1 1 2 4 PE2 3 6 時刻

38 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 7 8 6 30 9 1 PE1 1 2 4 PE2 3 6 5 時刻

39 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 7 8 6 30 9 1 PE1 1 2 4 PE2 3 6 5 時刻

40 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 6 7 8 30 9 1 PE1 1 2 4 7 PE2 3 6 5 8 時刻

41 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 6 7 8 30 9 1 PE1 1 2 4 7 PE2 3 6 5 8 時刻

42 タスクスケジューリング(スタティック) CP法等のリストスケジューリングでは 最適解が得られない例
クリティカルパス 優先度 1,2,4,5,7,8,3,6,9 リストスケジューリングでは実行可 能なタスクと空いているプロセッサ があれば割り当てを行なってしまう 1 1 2 1 2 3 1 2 3 4 5 6 7 8 9 64 63 12 61 11 41 31 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 4 7 9 73 PE2 3 6 5 8 時刻

43 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となる 1 1 2 1 2 3 20 20 4 5 10 40 7 8 6 30 9 1 PE1 PE2 時刻

44 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となるーNP 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 PE2 時刻

45 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となる 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 PE2 3 時刻

46 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となるーNP 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 PE2 3 時刻

47 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となるーNP 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 4 PE2 3 5 時刻

48 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となるーNP 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 4 7 PE2 3 5 8 時刻

49 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となるーNP 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 4 7 PE2 3 5 8 6 時刻

50 タスクスケジューリング(スタティック) 最適解は・・・ タスク3が終了しても6を割り当てない ところがミソ
最適解を得るためにはバックトラック をする全解探索が必要となるーNP 1 1 2 1 2 3 20 20 5 4 10 40 6 7 8 30 1 9 PE1 1 2 4 7 9 64 PE2 3 5 8 6 時刻

51 ループの並列実行方式

52 ループの並列実行方式－DOALL 定回ループ（ループ実行前に繰り返し回数が決まる）の並列実行方式 DOALL（forall）：
イタレーション間にまたがる依存関係（loop-carried dependencyデータ依存，制御依存）なし →イタレーション間での並列性を利用 各イタレーションのループボディ（一つもしくは複数）の処理をタスクとする 各イタレーションを異なるプロセッサに割当てて並列処理

53 ループの並列実行方式ーDOALL DOALL実行： do i=1,n a(i)= b(i)+c(i) d(i)= a(i)-3 enddo
doall i=1,n a(i)= b(i)+c(i) d(i)= a(i)-3 enddoall PE1: a(1)= b(1)+c(1) d(1)= a(1)-3 PE3: a(3)= b(3)+c(3) d(3)= a(3)-3 PE2: a(2)= b(2)+c(2) d(2)= a(2)-3 PE4: a(4)= b(4)+c(4) d(4)= a(4)-3

54 ループの並列実行方式ーDOALL DOALL実行 各プロセッサの動作： 割当てられたイタレーションを独自実行
全イタレーション完了後，他のプロセッサとバリア同期し，ループの次の処理へ進む 各イタレーション開始時における変数の初期値は全てのイタレーションにおいてループ開始直前の値とする

55 DOALLのスケジューリング（スタティック）
スタティックスケジューリング (1)各プロセッサにプロセッサ台数間隔のイタレー 　　ションを割当て（サイクリック割当て） do i= p, n, np ループボディ enddo p:プロセッサ番号（1～np） np:プロセッサ数 i,p,n,npはプロセッサのローカル(プライベート)変数 PE1: do i=1,n,8 PE2: do i=2,n,8 PE8: do i=8,n,8

56 DOALLのスケジューリング（スタティック）
スタティックスケジューリング (2)各プロセッサに連続したイタレーションを割当て （ブロック割当て） 　　 k = ceil(n/np) lb= k*(p-1)+1 　　 ub= min(k*p,n) 　　 do i=lb,ub 　　 ループボディ 　　　 enddo 切り上げ PE1: do i=1,30 PE2: do i=31,60 PE3: do i=61,90

57 DOALLのスケジューリング（スタティック）
スタティックスケジューリング（特にブロック割当て） →ループボディの処理量が一定でない場合， 　　負荷の不均衡が生じる ループボディにif文やループなどがある場合 例） i→ PE1 PE2 PE3 doall i=1,n do j = i,n a(i,j)=... enddo enddoall j ↓

58 DOALLのスケジューリング（スタティック）
スタティックスケジューリング（特にブロック割当て) →ループボディの処理量が一定でない場合，負荷のアンバランスが生じる ループボディにif文やループなどがある場合 例） i→ PE1 PE2 PE3 doall i=1,n do j = i,n a(i,j)=... enddo enddoall j ↓

59 DOALLのスケジューリング（ダイナミック）
ダイナミックスケジューリング （3）セルフスケジューリング ループ制御変数i(ローカル変数)を全プロセッサからアクセスできる共有変数　iglobalとする 各プロセッサは1イタレーションの処理を終了する毎にiglobalを更新し次のイタレーションを実行 lbl: （i=iglobal; iglobal=iglobal+1) if i>n exit ループボディ 　 goto lbl 不可分命令

60 DOALLのスケジューリング（ダイナミック）
ダイナミックスケジューリング （3）セルフスケジューリング 共有変数iglobalへのアクセスが集中 　　→そこがボトルネックとなり並列処理効果が低減

61 DOALLのスケジューリング（ダイナミック）
ダイナミックスケジューリング （4）チャンクスケジューリング 複数イタレーション単位で割当て →共有変数iglobalへのアクセス頻度を軽減 lbl: （j=iglobal; iglobal=iglobal+k) if j>n exit do i=j, min(j+k-1,n) ループボディ enddo 　 goto lbl

62 DOALLのスケジューリング（ダイナミック）
ダイナミックスケジューリング （4）チャンクスケジューリング タスクの粒度を大きくしている チャンクサイズが大きすぎると負荷アンバランスが生じる

63 DOALLのスケジューリング（ダイナミック）
ダイナミックスケジューリング （5）ガイデッドセルフスケジューリング 処理が進むにしたがってチャンクサイズを次第に小さくする →iglobalへのアクセス頻度を下げつつ負荷バランスを保つ タスク粒度を動的に変化させている

64 DOALLのスケジューリング（ダイナミック）
ダイナミックスケジューリング （5）ガイデッドセルフスケジューリング チャンクサイズ　k=ceil(nrem/np) 共有変数nremは未割り当てイタレーション数で初期値はn lbl: (k=ceil(nrem/np);nrem=nrem-k) if k=0 exit (j=iglobal; iglobal=iglobal+k) do i=j, j+k ループボディ enddo goto lbl

65 ループの並列実行方式ーDOACROSS イタレーション間にデータ依存がある場合DOALL不可 イタレーション間で同期しながら並列実行
イタレーション間で同期しながら並列実行　 do i=2,n a(i)= b(i)+c(i-1) c(i)= d(i)*a(i) e(i)= d(i)*5 enddo doacross i=2,n wait(sync, i-1) a(i)= b(i)+c(i-1) c(i)= d(i)*a(i) post(sync, i) e(i)= d(i)*5 enddoacross

66 ループの並列実行方式ーDOACROSS PE1 PE2 PE3
wait(sync, 1) a(2)= b(2)+c(1) c(2)= d(2)*a(2) post(sync, 2) e(2)= d(2)*5 PE2 wait(sync, 2) a(3)= b(3)+c(2) c(3)= d(3)*a(3) post(sync, 3) e(3)= d(3)*5 PE3 wait(sync, 3) a(4)= b(4)+c(3) c(4)= d(4)*a(4) post(sync, 4) e(4)= d(4)*5

67 ループリストラクチャリング

68 ループリストラクリャリング ループ構造を再構成する 技法 イタレーション間の先行制約を解消し並列ループとする
効率よい並列ループ実行を可能とする 技法 ループ交換 ループ分割 ネストを増やす 　　ストリップマイニング 　　サイクルシュリンキング ネストを減らす ループ融合 スカラ拡張

69 ループ交換 ループ交換（interchange) ネストループの外側と内側ループを入替え
例）DOALL可能なループを外側ループにする 　　　→オーバーヘッドの削減 (a)は(b)のようにインデックス j でDOALL可能 do i=2,n do j=1,n a(i,j)= a(i-1,j)+b(i,j) enddo enddo (a) do i=2,n doall j=1,n a(i,j)= a(i-1,j)+b(i,j) enddoall enddo (b)

70 ループ交換 DOALLをセルフスケジューリングする場合 (b)では：jglobalへのアクセス回数：n*(n-1) 　　　　　　バリア同期の回数：　　　 　(n-1) (b)は(c)のようにループ交換可能 (c)では： jglobalへのアクセス回数：n 　　　　　　バリア同期の回数：　　 　1 共有変数へのアクセスと同期回数を削減 do i=2,n doall j=1,n a(i,j)= a(i-1,j)+b(i,j) enddoall enddo (b) doall j=1,n do i=2,n a(i,j)= a(i-1,j)+b(i,j) enddo enddoall (c)

71 ループ分割 ループ分割(distribution) ひとつのループを複数ループに分割 (d)はイタレーション間データ依存によりDOALL不可
ループ分割すると(e)のようにDOALL可能となる do i=2,n a(i)= b(i)+c(i) d(i)=a(i-1)*4 enddo (d) doall i=2,n a(i)=b(i)+c(i) enddo d(i)=a(i-1)*4 (e)

72 ストリップマイニング ストリップマイニング(strip mining) 一重ループをネストループに変換
(f)はDOALL可能で プロセッサ4台にスタティックに連続割り当てるためにストリプマイニングし2重ループ化とすると(g)のように変換できる do i=1,128 a(i)= b(i)+2 enddo (f) doall i=1,4 do j=(i-1)*32+1,i*32 　　a(j)= b(j)+2 enddo enddoall (g)

73 ストリップマイニング さらに各プロセッサがベクトル処理できるとすると(h)のようになる doall i=1,4
do j=(i-1)*32+1,i*32 　　a(j)= b(j)+2 enddo enddoall (g) doall i=1,4 lb= (i-1)*32+1 ub=i*32 a(lb:ub)=b(lb:ub)+2 enddoall (h)

74 サイクルシュリンキング サイクルシュリンキング(cycle shrinking) 一重ループをネストループに変換
(i)はデータ依存のため全イタレーションでのDOALLは不可 (j)のように変換すると16イタレーション分のDOALLの繰り返しとすることが可能 do i=1,128 a(i+16)= a(i)+2 enddo (i) do i=1,128,16 doall j=i,i+16 　　a(j+16)= a(j)+2 enddoall enddo (j)

75 ループ融合 ループ融合(coalescing) ネストループを一重ループに変換 (k)はi,jどちらかでDOALL可能
(l)のように変換するとDOALLのイタレーション数を増やすことができる do i=1,4 do j=1,6 a(i,j)= b(i,j)+2 enddo (k) doall k=1,24 i=ceil(k/6) j=k-6*(i-1) a(i,j)= b(i,j)+2 enddoall (l)

76 スカラ拡張 スカラ拡張(expansion) イタレーション間のデータ依存を引き起こすスカラ変数を配列変数に変換しデータ依存を解消する
(m)のスカラ変数Xを配列変数xx(1:n)に一時的に置き換えることにより(n)のようにDOALL可能とする 配列変数とせずに(o)のように各プロセッサのローカル変数とする(プライベート化)ことも可能　 do i=1,n x=a(i)+b(i) c(i)= x+2 enddo (m) doall i=1,n xx(i)=a(i)+b(i) c(i)= xx(i)+2 enddoall x=xx(n) (n) doall i=1,n xlocal=a(i)+b(i) c(i)= xlocal+2 if (i=n) x=xlocal enddoall (o)