粗粒度タスクへの分解

粗粒度タスク並列処理では，はじめに入力となるコードを下記の3種類の粗粒度タ スク(Macro Task, MT)と呼ぶ並列処理単位に階層的に分割する[本多90,笠原92]．

・基本ブロック(Basic Block，BB)

・サブルーチンブロック(Subroutine Block，SB)

・繰り返しブロック(Repetition Block，RB)

基本ブロックは代入文や条件分岐の集合である．サブルーチンブロックは関数呼 び出しからなり，関数内の処理に対しても同様に粗粒度タスクが定義される．ま た，繰り返しブロックはループ処理からなり，ループ処理内に対して階層的に粗 粒度タスクが定義される．この繰り返しブロックは後のループ並列性解析により，

並列実行可能なループ(doall)もしくは並列実行不可能なループ(loop)として解析 される．

図3.2では，表3.1に示す12個の粗粒度タスクに分割される．表3.1中のbbが 基本ブロック，sbがサブルーチンブロックを示す．例えば，9行目や11行目の条 件式と43から47行目の算術代入文が基本ブロックとして，13行目から始まる関 数呼び出しがサブルーチンブロックとして分割される．また，13行目の関数呼び 出し内に対しても，階層的に粗粒度タスクに分割される．

3.3.2 粗粒度タスク間の並列性の抽出

粗粒度タスクへの分割後，全粗粒度タスク間のデータ依存，コントロールフロー を解析する．その結果を，マクロフローグラフ(Macro Flow Graph，MFG)として 表現する[本多90,笠原92]．

表3.1: Cコードと粗粒度タスクの対応関係 Cコード行数 粗粒度タスク名と番号

9-11行目 bb1

11行目 bb1-5

13-15行目 sb6

17-27行目 bb7

28-32行目 bb8

34-36行目 sb9

38行目 bb10

40行目 bb11

43-47行目 bb12

図3.2から生成されたマクロフローグラフを図3.4に示す．図中の各ノードが粗 粒度タスクを表し，ノード内の文字が粗粒度タスクの種類と番号を示す．ここで

のemt (End of Macro Task)はマクロフローグラフの終了を示し，擬似的なもので

ある．また，ノード間の実線エッジがデータ依存を，点線エッジがコントロール フローを示す．さらには，bbノード内に存在する小円は条件分岐を示す．

例えば，図3.1の27から41行目までのif then，else処理がbb7からbb10まで が該当するが，bb7小円からの左方向へのコントロールフローがthenパート(bb8, sb9, bb10)への分岐，右方向へのコントロールフローがelseパート(bb11)への分 岐を正しく表していることがわかる．この段階ではデータの流れのみを示してお り，粗粒度タスク間の並列性は表現していない．

マクロフローグラフの生成後，粗粒度タスク間の並列性を抽出するために，各 粗粒度タスク間のデータ依存とコントロールフローを考慮し，各粗粒度タスクが 最も早く実行可能になる条件である最早実行可能条件解析[本多90,笠原92]を行

図3.4: マクロフローグラフの例

う. その結果を粗粒度タスク間の並列性として表現したマクロタスクグラフ(Macro Task Graph，MTG)を生成する．

図3.4から最早実行可能条件解析を行い，生成したマクロタスクグラフを図3.5に 示す．マクロフローグラフと同様に，図中の各ノードが粗粒度タスクを表し，ノー ド内の小円が条件分岐，ノード間の実線エッジがデータ依存，点線エッジが拡張さ れたコントロール依存を示す[本多90,笠原92]．ここでの拡張されたコントロー ル依存とは，制御依存に加え，先行タスクの条件で実行されない場合の条件も含 むものである．

小円を起点とするデータ依存(例えば，bb7からbb8へのデータ依存エッジ)は データ依存とコントロールフローの両方を表している．また，エッジを束ねる実 線アークは，アークによって束ねられたエッジがAND関係にあることを表し，点 線アークはOR関係にあることを表し，矢印を持つエッジは条件分岐表すエッジ

図3.5: マクロタスクグラフの例

である．

例えば，bb8，sb9, bb11はOR関係にあり，さらにはbb8とsb9はAND関係に あるため，bb7からbb8(thenパート)に分岐した際には，bb8とbb9が並列実行可 能であることを示している．一方，bb11(elseパート)に分岐した際には，bb11の みの実行になるため，並列実行可能タスクは存在しない.