7.1.1　ループ並列化の概要

1. OpenMP指示文を追加したCソースプログラムとして出力することが出来る。
   それを、既存のOpenMPコンパイラを通すことにより、並列に実行させることができる。
2. LIRに変換し、並列マシン向けのの目的コードを生成することが出来る。

並列化は、コンパイラだけでは完結しない。コンパイラでは、並列実行するための 指示文の挿入や、並列実行のための制御ルーチンの呼び出し文を追加するにとどまる。 実際に並列実行させるには、言うまでもないことであるが

• 並列実行の機能を持つコンピュータ
• 並列実行の制御を行うOS、あるいは並列実行制御ルーチン

並列化の対象としたのは次のループである。

• ループ内に入出力を含なまい。
• ループ外飛び出しやループ飛び込みがない。
• ユーザ定義関数（手続き）呼び出しがない。
• 構造体とポインタは解析対象外とする。ただし、FORTRANの実装では COMMONや複素数を構造体として表現しているので、その 表現の構造体要素は解析対象とする。

プログラム全体の中で、並列化できる部分は限られている。 また、並列化して効果があるか否かを判定することは、 ループ反復数などの情報がなければできない。したがって、 入力されたプログラムを完全に自動並列化することは困難なので、 7.1.3.1小節で説明するように、並列化対象を含む副プログラムと、 その中で並列化の候補とするループを指示文（プラグマ）で 指定する必要がある。

実装されているのは、ループ繰り返しの（do-all型）並列実行の判定だけであるが、 そのために開発したデータフロー解析情報を使えば、以下のような応用を実装するのも比較的容易であると思われる。
　たとえば、最内側ループの解析ではベクトル型の文並列化可否（ループ分割）の判定処理が可能である。 解析したフローグラフのパスに付随する参照領域から、変数と配列についてのデータ依存グラフの構築が可能であり、これを用いるとさらに広範囲なプログラム変換の可能性を探ることができる。さらに解析情報をサブプログラムの外へ渡すことを可能とすれば、モジュール間の並列化解析の研究にも活用可能である。

7.1.2　ループの解析と並列化変換

7.1.2.1　解析と並列化変換の方針

ループのi回目の実行とｊ回目の実行で（ただしi≠j）の定義と使用、または定義と定義で同じ領域をアクセスする 可能性を検出した場合は、原則として並列化不可能と判定する。 ただし、それだけで判定すると、並列化不可能と判定されるものが多くなりすぎる。

そこで、並列化可能と判定するループを増やすために、以下のような基本的な並列化変換を行う．

1. 基本インダクション変数変換

         i = i + 定数
   

   の代入文で表現される基本インダクション変数はループ繰返しに線形であると判断した場合は、 「初期値、増分値、ループ繰返し回数」を用いる式に変形し、独立な演算に変形する。
2. 　リダクション命令の適用

         ｓ＝ｓ＋＜ｓを含まない式＞
   

   の代入文で表現される総和計算は、リダクション命令を適用できる。
   このようなリダクション命令を適用できると判断した場合は、OpenMP 指示文にそのリダクション命令を指定して並列化する。
3. private化
   ループ内で使用するデータは、ループ本体で先立って定義され、ループ繰返しをまたぐ値を定義・使用することが無いと判定 した場合は、一つの変数（または配列）を繰返し回数ごとに一時的に用意するprivate化を行う。

以下、データフロー解析に用いた参照領域を説明し、各処理方式の概要を示す。

7.1.2.2　データの参照領域の解析

7.1.2.2.1　参照領域情報

• 可能性使用（USE）
  　ある範囲（フローグラフのパス）で、使用される可能性のあるデータ
• 可能性露出使用（EUSE：Exposed USE）
  　ある範囲（フローグラフのパス）で、定義に先立って使用される可能性のあるデータ
• 可能性定義（MOD：MODified）
  　ある範囲（フローグラフのパス）で、更新される可能性のあるデータ
• 確定定義（DDEF：Definitely Defined）
  　ある範囲（フローグラフのパス）で、必ず更新されるデータ

これらの領域は、次のような関係になる。

　　　可能性使用　⊆　可能性露出使用
　　　可能性定義　⊆　確定定義

7.1.2.2.2　配列の添え字の正規化

添え字式は次のように分類される。

1. ループ不変
   1. 範囲なし（ある一つの要素、内側ループ不変）　[定数または、ループ不変式]
   2. 範囲付き（内側ループ可変）
      1. 内側ループのインダクション式　[ループ不変初期値，ループ不変終値，ループ不変増分値]
      2. 上記以外の内側ループ可変　USE、EUSE、MODは全要素、DDEFは空
2. ループ可変
   1. 範囲なし（ある一つの要素、内側ループ不変）
      1. インダクション式　[ループ不変初期値，ループ不変終値，ループ不変増分値]
      2. 上記以外（ループ繰返しに非線形で可変、間接インデックスなど）　USE、EUSE、MODは全要素、DDEFは空
   2. 範囲付き（内側ループ可変）
      1. 多次元配列で、ある一つの次元がインダクション式で、それ以外の次元は範囲付ループ不変
      2. 上記以外　解析不可能　USE、EUSE、MODは全要素、DDEFは空
3. ループ範囲可変（例外的）　初期値か終値がインダクション式であるインダクション範囲
   　 [ループ不変初期値，ループ可変終値，ループ不変増分値]　または[ループ可変初期値，ループ不変終値，ループ不変増分値]
   　 さらに[ループ可変初期値]や[ループ可変終値]は、[ループ不変初期値，ループ不変終値，ループ不変増分値]の組で表現する．

　これらの分類をより細密にして、各領域集合の加減算や積演算を定義すると、解析精度が高くすることができる。 これらの添え字の正規化のために、インダクション変数を検出し、標準化する。

7.1.2.3　基本インダクション変数の検出と変換

7.1.2.3.1　変換可能な基本インダクション変数

1. 定義文はループ繰返し部の中にはただ一つ
2. 定義文はループ出口（解析対象ループは唯一つの出口を持つ）を支配

ここで検出したインダクション変数に対して、初期値設定用に作った処理系定義の変数と、 その定義式より見つけた増分値をテーブルに登録しておく。これらのインダクションテーブルは、 ループ単位の処理なのでループテーブルに接続する。

7.1.2.3.2　インダクション変数変換

   基本インダクション変数＝e＊増分値＋初期値の一時的な変数

図7.1-1　基準インダクション変数の導入

その後、置き換えた基本インダクション定義文を繰返し部の先頭に移動する。
定義文から再帰性を除去しても、他の使用に対してループ繰越しフロー依存があると並列化できないため、 全てのフロー依存がループ独立となるよう繰返し部の先頭に移動する。
このとき、もともとループ独立なフロー依存がある場合は、その基本インダクション変数の使用を 「基本インダクション変数＋増分値」で置き換える。これは、導入した基準インダクション変数eの 初期値が０であるためである。図7.1-1の例だと、図7.1-2のようになって、iやjにかかわる全ての フロー依存はループ独立となり、インダクション変数変換が終わる。
この過程で、全ての基本インダクション変数とそれらを用いたインダクション式は初期値と増分値 で表現することが可能となり、配列の添え字式に対してはインダクション式であることと、その [初期値,増分値，終値]の組をテーブルに保存する。

図7.1-2　定義文の移動と使用の置き換え

7.1.2.3.3　リダクション命令適用の検出

• その変数に対する代入は、対象ループ内で唯一でループ出口を支配している。
• 左辺変数の型はfloat、double、int、long、unsigned など数値を保持ずるもの。
• 代入左辺からの定義使用連鎖は唯一、同じ代入文の右辺式のただ一箇所に届く。
  （ｓ= s+s+a[i]は対象外ということ。）
  　これが基本インダクション変数より、厳しい条件である。
• 加算と乗算、減算を対象とする。

7.1.2.4　参照領域情報の解析

7.1.2.4.1　文における参照領域

7.1.2.4.2　基本ブロックにおける参照領域

  USE(s1:s2)   ←　USE(s1)＋USE(s2)
  EUSE(s1:s2)　←　EUSE(s1)＋( EUSE(s2)−DDEF(s1) )
  MOD(s1:s2)　←　MOD（s1）＋MOD（s2）
  DDEF(s1:s2) ←　DDEF（s1）＋DDEF（s2）

  a = a + c　…　/s1/　　USE(s1)=EUSE(s1)={a,c}，MOD(s1)=DDEF(s1)={a}
  b = c + d　…　/s2/　　USE(s2)=EUSE(s2)={c,d}，MOD(s2)=DDEF(s1)={b}
  a = b + c　…　/s3/  　USE(s3)=EUSE(s3)={b,c}，MOD(s3)=DDEF(s1)={a}

  EUSE(s1:s2) ← EUSE(s1)＋( EUSE(s2)−DDEF(s1) )={a,c}+( {c,d}−{a} ) = {a,c,d}

  DDEF(s1:s2) ←　DDEF(s1)＋DDEF(s2) = {a,b}　となるため、
  EUSE(s1:s2:s3) ← EUSE(s1:s2)＋( EUSE(s3)−DDEF(s1:s2) )= {a,c,d}+({b,c}−{a,b}) = {a,c,d}

図7.1-3　基本ブロックの参照領域

7.1.2.4.3　最内側ループi回目の参照領域

図7.1-4　条件分岐の参照領域の統合

図7.1-5　連接する参照領域の統合

制御フローグラフの基本ブロックごとの参照領域を、これらの2種類の統合処理を施して、 並列化を判定する当該ループのあるi回目の参照領域を計算する。

7.1.2.4.4　並列化判定対象ループ全回の参照領域

7.1.2.4.5 内側にループを含むループの解析

図7.1-6　内側ループ不変添え字の分類

図7.1-7　内側インダクション添え字式の分類

内側にループを含むループの並列化可否を判定する場合は、内側ループの参照領域をまとめる必要がある。 内側ループのある１回の参照領域と、それから導かれる全回の参照領域はすでに計算されている。 原理的には連接する基本ブロックの統合と同じである。図7.1-8に示す。

図7.1-8　外側ループ解析時の内側ループの参照領域の展開

内側ループi回目のEUSEを求めるのに、0回目から(i-1)回目までのDDEFの和集合を除き、 それを内側ループの全回で加えたものが、一つ外側から見た内側ループブロックにおける露出使用となる。
このようにして、展開した内側ループの参照領域を、並列化可否判定対象としている外側ループの最内部の 参照領域とまとめる。これは、4.4節の基本ブロック間の統合と等しい。 内側ループを一つの基本ブロックのように扱うわけである。
その様子を図7.1-9に示す。

図7.1-9　内側にループを持つループの参照領域のまとめ

この解析により、内側ループでは繰越し依存関係にあったものが、外側ループから見ると、 private化することにより並列化可能と判断できる場合がある。7.1.2.6節に例を示す。

7.1.2.4.6 関数（手続き）全体の参照領域

• 他の関数（手続き呼出し）

  このファイルの参照領域が閉じたものか、そうでないのかを表すために必要である。呼び出しているユーザ定義関数の 種類と名称を並べる。

• 仮引数に関する情報

  関数全体を解析した結果のUSEとEUSEの参照領域にある仮引数の領域と、MODとDDEFの各参照領域では アドレス渡しの仮引数(Cだと配列名称、Fortranだと仮引数全て)の領域を並べる。

• グローバルデータに関する参照領域

  関数全体を解析した結果のUSE、EUSE、MOD、DDEFの各参照領域で、グローバルデータの領域を並べる。

7.1.2.4.7 領域の演算

7.1.2.5 並列化可否の判定

7.1.2.5.1 変数に関する判定

 (a) EUSEi　∩　MODi ≠｛Φ｝　　ループ繰越しフロー依存がある。
 (b) USEi　∩　MODi ≠｛Φ｝　　　ループ繰越し逆依存がある。
 (c) MODi ≠｛Φ｝　　　　　　　　ループ繰越し出力依存がある。

図7.1-10　変数のループ繰越し依存関係

ループ繰越し依存関係のうち、private化することによって、ループ繰越し出力依存とループ繰越し逆依存は解消できる。 ただし、private化することができるのは、ループ繰越しフロー依存が無い場合だけである。図7.1-10の例では、 ループ繰越しフロー依存があるためprivate化することはできない。図7.1-11にprivate化により並列化可能となる例を示す。

図7.1-11　変数のprivate化によってループ繰越し逆依存と出力依存を解消する例

ループ繰越し依存を検出しても、リダクション命令を用いることにより並列に実行できることがテーブルに登録されている場合は、 並列化不可能要因からはずし、OpenMPの指示文にリダクション命令に関するオプションを加える。
ループ不変な添え字式でアクセスされる配列要素は、ここに示した単純変数と同様に扱うが、配列の要素単位でprivate化 する手段が無く、配列全体をprivate化する場合のオーバヘッドが大きくなることから、private化による並列化は行わず、 並列化不可能と判断している。

7.1.2.5.2 配列に関する領域参照領域とループ繰越し依存

7.1.2.6 解析とソースプログラム生成の実行例

図7.1-12　内側ループの参照領域と並列化可否判定結果

次に外側ループの解析のために内側ループの情報を展開する。EUSE以外はそのまま全回繰返しの領域 になるよう和集合をとる。 EUSEについては、

図7.1-13　内側ループの参照領域の展開

最後に外側ループの最内部と内側ループ部の参照領域を図7.1-14のように統合して、外側ループの並列化可否を判定する。

図7.1-14　参照領域の統合と外側ループ並列化可否の判定

外側ループの最内部の配列xの要素x[0]とx[1]への定義文があり、これらがMODとDDEFになる。連接する参照領域の統合で、

  EUSE外側ループi回目＝EUSE内側ループ−DDEF最内部

  EUSE外側ループi回目＝ {Φ}

  MOD外側ループi回目＝MOD最内部＋MOD内側ループ

  MOD外側ループi回目＝ { x[0:n-1:1] } (範囲付きループ不変)

  EUSE外側ループi回目　≠　MOD外側ループi回目

  USE外側ループi回目＝{ x[0:n-1:1] } (範囲付きループ不変)

図7.1-15に並列実行のためのOpenMP指示文を挿入した出力ソースプログラムを示す。

図7.1-15　生成するC+OpenMP指示文のソースプログラム

7.1.2.7 解析・変換の実現方法とツールとしてのモジュール化

• サブプログラム単位のループ解析
• サブプログラム単位のループ変換
• サブプログラム単位の OpenMP 化
• サブプログラム単位のデータアクセス領域解析

7.1.3 OpenMPコンパイラとの連携

7.1.3.1 並列化候補の指定

並列化候補の指定では、コンパイル単位の先頭部分で、まず並列化候補を含む ルーチン（関数）を次の形で指定する。

    #pragma parallel doAllFunc func1 func2 ...

    #pragma parallel doAllFuncAll

    #pragma parallel doAll

7.1.3.2 並列化されたCプログラムの生成

   java coins.driver.Driver -coins:parallelDoAll=OpenMP foo.c

例として、次のプログラム

#pragma parallel doAllFunc main
int printf(char*, ...);
int k, c[50];
main() 
{
  int x[50];
  int i, j, n, sum;
  n = 50;
  k = 100;
  sum = 0;
#pragma parallel doAll
  for (i = 0; i < n; i++) {
    x[i] = k + i;
    c[i] = i * i;
    k = k - 2;
    sum = sum + x[i];
  }
  for (j = 0; j < n; j++)
    printf("x[%d]=%d c[%d]=%d", j, x[j], j, c[j]);
  printf("\nk = %d sum = %d \n", k, sum);
  return 0;
}

extern int printf ( char * , ... ) ;
 int k, c[50];
int main( )
{
    int x[50];
    int i, j, n, sum;
    n = 50;
    k = 100;
    sum = 0;

#pragma omp parallel for lastprivate(k,i) reduction(+:sum)
    for ( i = 0;i < n; i = i + 1)
    {
        k = (-2) * i + 100;
        {
            x[i] = k + i;
            c[i] = i * i;
            sum = sum + x[i];
        }
    }
    _lab4:;
    k = (-2) * i + 100;
    for ( j = 0;j < n; j = j + 1)
    {
        (&(printf))( ("x[%d]=%d c[%d]=%d"),j,x[j],j,c[j]);
    }
    _lab8:;
    (&(printf))( ("\nk = %d sum = %d \n"),k,sum);
    return 0;
}

7.1.3.3 並列化された実行モジュールの生成

  java coins.lparallel.LoopPara -coins:hir2c foo.c

7.1.4 並列マシン用の目的コード生成