4.2 モデルベース開発ソフトウェアのマルチグレイン並
図4.1: モデルベース開発ソフトウェアのマルチグレイン並列処理のフロー
が逐次的に実行されなければならない．
そこで，下記のようにループ内のステートメント間のデータ依存関係に基づき，
使い回しのあるループ処理を検出し，ループ分割を行う．
step 1 ループをもつマクロタスクを探索する
step 2 step 1で見つかったそれぞれのループに対して，ステートメントレベルで依
存関係を解析する．
step 3 各ステートメント間に依存関係がない場合，ループ分割を行う
図4.2: 粗粒度タスク並列性がCコードに現れないSimulinkモデルの例
step1で図4.4.(a)のdoall1, doall3, doall5が抽出される．step2で各doallに対して，
ステートメント間の依存関係を解析する．step3でdoall3のステートメントに依存 関係がないため，図4.4.(b)に示すマクロタスクグラフのようにdoall3とdoall4を 生成する．このようにして，ステートメント間に基づきループ分割を行うことに より，画像処理等のモデルベース開発ソフトウェアの粗粒度タスク並列性を向上 することができる．
4.2.2 マルチグレイン並列性の利用のためのループ分割
画像処理等のモデルベース開発ソフトウェアにはループ構造が存在するため，
ループ並列処理による性能向上が期待できる．ただし，モデルベース開発では複 数のブロックを組み合わせてモデルを設計するために，自動生成コードでは複数 の並列化可能ループ，逐次ループ，関数呼び出しに処理負荷が分散する．そのた め，ループ並列処理のみでは十分な性能向上が期待できない．そこで，第3.3章の モデルベース開発粗粒度タスク並列処理手法に加えて，ループ並列処理を組み合 わせたマルチグレイン並列処理を行う．本節では粗粒度タスク並列処理をベース
1 void S1_step(void) 2 {
3 int32_T i;
4 for (i = 0; i < 589824; i++) {
5 S1_B.Gain[i] = (uint16_T)((uint32_T)S1_P.Gain_Gain * 6 S1_U.In1[i]);
7 }
8 S1_F1();
9 for (i = 0; i < 589824; i++) {
10 S1_Y.Out1[i] = (S1_B.y[i] > S1_P.Constant_Value);
11 S1_B.Gain1[i] = (uint16_T)((uint32_T)S1_P.Gain1_Gain * 12 S1_U.In1[i]);
13 }
14 S1_F2();
15 for (i = 0; i < 589824; i++) {
16 S1_Y.Out2[i] = (S1_B.y_l[i] > S1_P.Constant_Value_o);
17 } 18 }
図4.3: Embedded Coderを使って自動生成されたループ構造を持つCコード
図4.4: ループ構造を持つモデルベース開発ソフトウェアのマクロタスクグラフ
に，並列化可能ループをあらかじめイタレーション毎に分割し，独立した粗粒度 タスクとして扱う．これにより，分割されたループや逐次ループ，関数呼び出し，
分岐処理等の間で粗粒度タスク並列処理を可能となる．
マルチグレイン並列性の利用のためのループ分割は粗粒度タスク並列度Para [小幡03]を基に行う．
例として，図4.5のマクロタスクグラフのParaを求める．doallは並列実行可能 な繰り返しブロック(rb)を示し，loopは並列実行不可能なrbを示す．また，実線 エッジはデータ依存，太線はクリティカルパス，ノード内の数値は逐次処理相対 コストを表す．マクロタスクグラフ上の逐次処理コストは
Seq=15000+10000+17000+16000+3000+37000+2000=100000 (4.1)
太線上のクリティカルパス長は
CP=15000+3000+37000+2000=57000 (4.2) となる．したがって，粗粒度タスク並列度は
Para=100000/57000=1.75 (4.3)
となる．すなわち，従来のモデルベース開発アプリケーションの並列化手法に該 当する粗粒度タスク並列化では高々1.75倍までしか並列処理による性能向上が得 られない．そこで，スケジューリングするコア数に合わせて並列処理の効果があ る最小のコストTminを超えるコストになるように並列実行可能ループdoallを分 割し並列性を向上させる [小幡03]．4プロセッサコアをターゲットに並列化可能 ループの分割後のマクロタスクグラフの例を図4.6に示す．図4.5におけるdoall1，
doall2，doall6が4分割され，太字のクリティカルパスが変わっていることがわか
る．この際のクリティカルパス長は
CP=3750+2500+17000+2000=25250 (4.4) となる．したがって，分割後の粗粒度タスク並列度は
Para=100000/25250=3.96 (4.5)
となる．すなわち，並列実行可能なループを分割することで並列性を向上できる．
また，図4.5と図4.6のマクロタスクグラフを4プロセッサコアにスケジューリ ングを行った結果を図4.7に示す．図中の外枠がプロセッサコア資源，ノードがマ クロタスクを示し，ノードの長さがマクロタスクの実行時間を示す．すなわち，縦 軸の長さがスケジューリング長を示している．また，ノード間の矢印が同期命令 の方向を示す．並列実行可能ループ分割前のスケジューリング結果である図4.7.(a) では つのコア資源が有効活用できていない．例えば， に割り当てされてい
図4.5: 粗粒度タスク並列度の計算
るdoall6が全体の37%を占め，Core 3(プロセッサコア3)には並列実行可能な粗粒 度タスクがない．
一方，並列実行可能ループ分割後のスケジューリング結果である図4.7.(b)では すべてのコア資源が活用できている．例えば，融合ブロックであるblock3，loop4， 分割ループの間で並列実行が実現し，スケジューリング長が短くなっている．こ のようにして，マルチグレイン並列性を利用するために，あらかじめ並列実行可 能を分割し，粗粒度タスク並列処理を行うことで，多くのコア資源を活用するこ とが可能となる．
図4.6: 並列化可能ループの分割後の粗粒度タスク並列度の計算