3.5 モデルベース開発ソフトウェアのための粗粒度タス
ないスタティックタスクスケジューリングが適用できるようにマクロタスク融合を 適用する．提案する手法ではコントロールフローが表現されているマクロフロー グラフから条件分岐ノードを検出する．このとき，条件分岐ノードはノードを始 点とする複数のコントロールフローをもつノードのことである．条件分岐ノード の検出後，条件分岐ノードの後支配節(Post Dominator)から条件分岐の集合を探索 する．後支配節とは各ノードから最終ノードまでに到達する際に，必ず通る節の 集合である．すなわち後支配節を解析することで，条件分岐が集約する条件分岐 出口ノードを検出することができる．このようにして，条件分岐ノードと条件分 岐出口ノードを検出し，融合することで分岐のないマクロフローグラフ及びマク ロタスクグラフを生成する．下記にマクロタスク融合のアルゴリズムを示す．
step 1 マクロフローグラフからノードを始点として複数のコントロールフローを
持つ条件分岐ノードを探索する
step 2 step 1で見つかったそれぞれの条件分岐ノードに対して，step 3-6を適用する
step 3 条件分岐ノードの後支配節にあるノードを探索する
step 4 条件分岐ノード自身を除く最小の後支配節を条件分岐出口ノードとして定
義する
step 5 条件分岐ノードから条件分岐出口ノードまでを単一の粗粒度タスクに融合
する
step 6 融合された粗粒度タスクをBlockとして再定義する
例として，図3.12に条件分岐隠蔽のためのマクロタスク融合の過程を示す．図
3.12.(a)はマクロタスク融合を行う前のマクロフローグラフである．小円が示す条
件分岐がbb1とbb8に存在する．step1でコントロールフローを複数持つbb1とbb8
が条件分岐ノードして検出される．step2でbb1とbb8に対して，step3-6が適用さ れる．bb1において，step3で後支配節が
pdom(1) ={1,4,5,6,7,8,10,11} (3.1) と検出される．この際，step4で条件分岐ノード自身(bb1)を除く最小ノードであ るbb4が条件分岐出口ノードとして定義される．step5でbb1からbb4が融合され る．step6で融合された粗粒度タスクがBlockとして再定義され，図3.12.(b)が得 られる．同様にstep1で検出された図3.12.(b)におけるbb5(図3.12.(a)ではbb8)に 対して，step3-6を適用する．bb5においてstep3で後支配節が
pdom(5) ={5,7,8} (3.2)
と検出され，条件分岐ノードを除く最小ノードであるbb7が条件分岐ノードとし て定義される．step5でbb5からbb7が融合され，step6で図3.12.(c)が得られる．
このようにして，条件分岐を隠蔽したマクロフローグラフが形成される．これに 対して，最早実行可能条件解析を適用すると，図3.12.(d)のようなデータ依存エッ ジのみで構成されるマクロタスクグラフが得られる．このようにして，マクロタ スク融合を行うことで，条件分岐を持つソフトウェアにスタティックタスクスケ ジューリングが適用可能となる．
3.5.2 粒度調整のためのヒューリスティックマクロタスク融合
細かなタスクが多数存在する場合，スタティックタスクスケジューリングの際，
データ転送や同期が余計に発生してしまうスケジューリングになる場合(図3.13)が
ある．3.3.3節で前述したように，OSCAR自動並列化コンパイラのスタティックタ
スクスケジューリングではCP法を基にした複数のヒューリスティックスケジュー リングから成り立つ．そのため，実行可能なタスクを起点としたパス長を基にス ケジュールされる．
図3.12: 条件分岐隠蔽のためのマクロタスク融合の適用例
ここで，図3.13.(a)のようなツリー形状のマクロタスクグラフのスタティックタ スクスケジューリングを例として挙げる．各粗粒度タスク中の数字は相対的な実 行時間を示している．始めに，先行タスクがなく，実行可能なタスクはbb1, bb3,
bb7, bb9が挙げられる．このときの各タスクを起点としたパス長は190, 190, 189,
189となる．これに対して，2コア向けにスタティックタスクスケジューリングを 行うと，パス長が最も大きいbb1, bb3が各コアに割り当てられる．bb1, bb3の実 行が終了後，後続タスクであるsb2, sb4が割り当てられる．また，別々のコアで実 行したsb2とsb4の結果をbb5で利用するために，ss0(synchronization sends to core 0)と示しているようにコア0への同期フラグの送信が追加される．bb5の開始前に sr1(synchronization receives from core 1)でコア1からの同期フラグが信が追加され る．同様にして，別々のコアで実行されたsb8とsb10の結果をbb11で利用するた めに，sb8終了時にss1でコア1への同期フラグの送信，bb11開始時にsr0でコア0 からの同期フラグの受信が追加される．しかしながら，図3.13.(a)では各ツリーコ ストが均衡するため，bb1, bb3, sb2, sb4, bb5, sb6とbb7, sb8, bb9, sb10, bb11，sb12 を各コアで実行する方が，同期回数の面から効率的となる．
そこで，このようなツリー形状が別々のヒューリスティックタスクスケジューリ ングにより別コアに割り当ってしまわないように，ヒューリスティックマクロタス ク融合[笠原92]により，図3.14に示す(a)直線形状と(b)ツリー形状を検出し，部 分グラフにおける最小並列処理時間と，同一コアプロセッサ上で処理する場合の シーケンシャル時間を比較して融合する．ブロックレベル並列化[TFL15]におい
ても，図3.14(a)に示すような直線形状の融合を行うが，これはスケジューリング
時間の削減が目的である．一方，本手法ではオーバーヘッドの削減が目的であり，
図3.14(a)の形状のみではなく，図3.14(b)のような形状に対して粗粒度タスクの処
理時間を考慮して行う．
図3.14ではMTi，MTjの処理時間をti，tjとし，MTi，MTjの間のデータ転送時 間をMTi j とする．図3.14.(a)ではMTiとMTjが別々のコアプロセッサで実行され る場合は処理時間には最小並列処理時間がti+tj +ti jになる．一方，同一コアプロ セッサで実行される場合にはシーケンシャル時間がti+tjとなる．したがって，常 にシーケンシャル時間の方が短くなるため，直線形状の2つの粗粒度タスクは常 に融合する．一方，図3.14.(b)では最小並列処理時間がmin(max(ti,tj+tjk), max(ti +tik,tj)) +tkとなり，シーケンシャル時間がti+tj+tkとなる．そのため，
min(max(ti,tj+tjk),max(ti+tik,tj)) +tk<ti+tj+tk (3.3) すなわち，
min(max(ti,tj+tjk),max(ti+tik,tj))<ti+tj (3.4) を満たす場合，ツリー形状の3つの粗粒度タスクを融合する．
このようにして，ヒューリスティックマクロタスク融合により，並列性を損なわ ない範囲で粗粒度タスクを融合することにより，粗粒度タスク並列処理のオーバー ヘッドを削減する．
図3.13.(a)のマクロタスクグラフに図3.14.(a)の直線形状を融合した場合のマク
ロタスクグラフを図 に示す．図中の が融合されたブロックを示して
図 3.13: ヒューリスティックタスクスケジューリングにより通信が発生してしま う例
いる．次に図3.14.(b)に示すツリー形状を融合すると，図3.15.(b)に示すマクロタ スクグラフが生成される．このようにして，繰り返しヒューリスティックマクロ タスク融合を行うことにより，あらかじめ粗粒度タスクのグルーピングが実現し
た．図3.15.(b)に対して，OSCAR自動並列化コンパイラのスタティックタスクス
ケジューリングを行うと図3.15.(c)に示すスケジューリング結果となる．このスケ ジューリング結果では同期命令が1回分になり，図3.13.(b)と比較して，効率的な スケジューリング結果となっている．
図3.14: ヒューリスティックマクロタスク融合パターン