### 1. 並列マシン用コード生成の概要

COINSの並列化の機能を利用して並列マシン用のコード生成をすることが出来る。 現在は、Xilinx社製のVertex-4という名前のFPGA上に複数のCPUコア（MicroBlazeマシン）を載せた実装 の上で動作確認をしただけであるが、今後は、Intel x86についても動作確認をする予定である。

Vertex-4上のMicroBlazeマシンで動作確認をする場合、 並列化は次の手順で行われる。

1. プラグマにより並列化の指示をする（人手）
2. HIRによる並列化可否の判定をする（コンパイラ）
3. プラグマで指定され、do-all型並列化可能と判定されたループに対して、 並列化のフレームワークに従ってHIRの並列化変換を行う（コンパイラ）
4. HIRからLIRに変換し、LIRからMicroBlazeのコードを生成する（コンパイラ）
5. ２台ないし４台のMicroBlazeを搭載したボードで並列実行する（人手介入）

他の機種についても同様のやり方でできる。

例えば次のプログラムを考える。

    #define nn 100000
    void kernel1()
    {
     float x[nn], y[nn];
     float zx[nn+11];
     float q, r, t;
     int k;
     kernel1_setup(nn, &q, &r, &t, x, y, zx);
     for ( k = 0; k < nn; k++ )
       x[k] = q + y[k] * (r * zx[k+10] + t * zx[k+11]);
    }

このプログラムに次のようなプラグマなどを差し込む。

    #include "coinParallelFramework.h"
    #define nn 100000
    void kernel1()
    {
     float x[nn], y[nn];
     float zx[nn+11];
     float q, r, t;
     int k;
     kernel1_setup(nn, &q, &r, &t, x, y, zx);
    #pragma parallel doAll
     for ( k = 0; k < nn; k++ )
       x[k] = q + y[k] * (r * zx[k+10] + t * zx[k+11]);
    }

このプログラムにコンパイラオプションでループ並列化の指示（-coins:parallelDoAll）をすることによって、 もしこのループが並列化可能であれば、並列化実行可能コードが生成される。 （実際にはmainプログラムなどにも挿入すべきプラグマがあったりするが、それについては後述する。）

コンパイラによる変換方式はほぼ固定であるが、実行環境に合わせて実際の並列実行を支援するのが、

    #include "coinParallelFramework.h"

および

    coinsParallelFramework.c

であり、それぞれは並列用のヘッダファイルとランタイムルーチンである。 coinsParallelFramework.h をインクルードする代わりに

    #include "coinParallelFrameworkInline.h"

とすると、オーバーヘッドの少ないインライン展開用のヘッダファイルが使われる。 これらのファイルは決められたフレームワークに従って、並列化部分を実装する者によって定義される。 ハードウェアやOSなど稼動環境が異なるものに対応するために、実行環境に依存する部分をコンパイラから分離してある。以下、上記のことがらについて説明する。

### 2. 並列化のフレームワーク

#### 2.1. フレームワークの設定

##### 並列化の多様性

並列実行のためには、一種の実行単位が必要である。これを今回はタスクと呼ぶことにする。 ひとつのタスクは複数の並列実行可能なスレッドによって実現される。「並列実行可能な」という 意味は「並列に（非決定的に）動作する可能性がある」ということである。

注意すべきことは次のとおりである。

- 並列実行の仕組みにはOSが介在するケースが多い。
  - pthread など
- ハードウェア環境をライブラリで隠して実現する場合もある。
  - PI 環境など
- この中間のものもある。

プロセッサやコアを直接指定して使う場合もあり、OS がプロセッサを仮想化して提供する場合もある。 汎用マシンの場合、多くは後者である。他のプロセスが動いている関係で、タスクとプロセッサの関係を固定しない スケジューリングの方が性能が高い。

メモリの共有についてもマルチプロセス環境ならば、共有メモリや分散メモリの枠組みを使うことになる。 またUnix に実装されているスレッドならば自然にヒープが共有されることになる。

このように並列化といっても実装レベルではいろいろなケースがあり、また性能のバランスも それぞれによって異なる。したがって、並列化についてこと細かにフレームワークを設定するべきではなく、 抽象度の高いフレームワークを提供することが望ましい。

##### 抽象度の高いフレームワーク

基本的なフレームワークは次のとおりとする。 （その各項目はpthreadでは何に対応するかを参考までに示す。）

- 初期化する。　 pthread_init
- フォークする。 pthread_create
- ジョインする。 pthread_join
- 通信する（データの交換をする）。
- 排他制御する。 pthread_mutex_lock

これらのフレームワークの設定で、もっとも重要なのは一般的であるかどうかである。 コンパイラならではの便利な機能は入れるべきと思われるが、それ以外は、敢えて変わったもの ではなく、一般的な枠組みであるべきである。ご覧になった方はわかるかと思われるが、上述の フレームワークはpthread library の基本的な機能を取り出しただけである。何故 pthread library ではないのかと言えば、組込みチップのように（OSレベルではなく）ハードウェアが 直接的に関与して実現することもできるようにするためである。一段低いレベルに設定し、 実行時ライブラリレベルで実現する並列計算機に必要と思われる機能を 最小限に絞って挙げたのである。

これだけであるとループのような並列化アルゴリズムが存在する場合でもそれなりの手間が必要と なってしまう。そこで、今回は、COINSのループ並列化が対象としている（つまり今回の対象である） do-all 型ループに関する簡単なフレームワークを用意する。

ループの並列化実行の前に

- 前処理

最後に

- 後処理

が必要であるが、それらは実行環境に合わせて予め準備すればよいからである。 フレームワークはdo-all型に限らずいろいろと考えることが できるが、ここではdo-all型に限定して具体化する。

##### フレームワークの活用場面

フレームワークを活用する場合として次の 2 つを想定した。

1. 直接利用

   ソースプログラムの中でフレームワークを直接利用するプログラムである。 pthread などを利用したプログラミングの経験者はこのような使い方をする かもしれない。もっともそのようなプログラムならば、pthread が利用できる環境であれば直接 pthread を利用するであろうが、 pthreadの使えない環境では、それに合わせてフレームワークを準備する 必要がある。

2. 間接利用

   自動並列化解析結果などを利用して（コンパイラで）並列化を実現する場合である。 解析結果を活用した並列化プログラムのターゲット（コンパイラの生成するコード）が このフレームワークを活用するものとなる。

#### 2.2．プログラムの並列化

##### ループ並列化の変換系

COINSのループ並列化プログラムは、

- HIRに対する並列化解析
- HIRの並列化変換（ループの正規化等）
- 変換されたHIRからのOpenMPプログラムの生成
- 並列化フレームワークに従った機械語コード（アセンブリ言語形式）や Cプログラムの生成

などからなる。HIRに対する並列化の解析と変換、および それからのOpenMPプログラム生成の内容は ループ並列化で説明されていることと同じである。

ここでは、並列化フレームワークに 従って、機械語コードやCプログラムを生成することについて述べる。

###### do all 型並列化プログラム

変換のイメージを例で示す。詳細はあとで説明することにして、 並列化の実行時ルーチンの一部の引数は ... と省略してある。

変換前

    #pragma parallel doAllFunc sub
    main()
    {
    #pragma parallel init
     ...
        sub();
     ...
    #pragma parallel end
    }

    sub()
    {
     ...
    #pragma parallel doAll
     for (i = 0; i < M; i++ )
         body_process(i);  /* ループボディのこと。擬似関数で示した。 */
     ...
    }

変換後

     main()
     {
      DECLARE_LOCAL_VARIABLES_OF_MAIN
      coinsNumberOfThreads = coinsThreadInit(...);
      ...
      sub();
      ...
      coinsThreadEnd();
    }

     sub()
    {
      ...
      {
       DECLARE_LOCAL_VARIABLES
       coinsThreadPreprocessForDoAllLoop(coinsNumberOfThreads, M, ...);
            /* 添字範囲の分割などを行う */
       for (_I = 1; I <= ( coinsNumberOfThreads - 1); _I = _I+1)
          coinsThreadForkForDoAll(I,&coinsThread[I], sub_loop_0, ...);
       body_process_for_master(...); /* マスタープロセスで分担する部分 */
       coinsThreadPostProcess(coinsNumberOfThreads, M);
      }
      ...
    }

    void *sub_loop_0( int _threadId, long _indexFrom, long _indexTo, ...)
     {
        DECLARE_LOCAL_VARIABLES_OF_SUB
        coinsThreadPreprocessForDoAllThread();
        SET_INITIAL_VALUES
        for( local_i = _indexFrom; local_i < _indexTo; local_i++ )
               body_process(local_i); /* スレーブプロセスで分担する部分 */
    　　RECORD_RETURN_VALUES
        coinsThreadPostprocessForDoAllThread();
        return;
    }

###### 変換に必要なこと

1. 一般ユーザがやること

   次のとおり。

   1. 自動並列化
      - ループを用いたプログラムを用意し、並列化オプションを付けてコンパイ ルする。その際フレームワークユーザが定義したファイルをインクルードする こと。
      - どのループを並列化するかはプラグマによって指定する。そ のためには、プログラマはプロファイルをとってホットスポットやコードサイ ズを把握する必要がある。
      - 自動並列化できればこれでおしまい。
      - メッセージなどから、並列化できない状況を把握し、プログラムを修正する。
   2. プラグマ指定のみによる並列化
      - 全部を自動並列化に任ることはしないで、ユーザ責任で並列化指定をする。 その際、並列化に必要な情報をプラグマで記述する。
      - リンクやロードをするためのリンカスクリプトを作成する。
2. フレームワークユーザがやること

   次のとおり。

   - 対象環境に合わせて、フレームワークのインスタンスを作成する。 例えば、pthread ライブラリがあれば pthreadライブラリ呼出しなどで定義する。（後述）
   - ブートストラップや HIR の INCLUDE 機能などがあれば、それで対応するのも良い。 inline展開を有効活用することも考える。
   - リンクやロードをするためのリンカスクリプトを提供する。
3. コンパイラがやること

   次のとおり。

   - フレームワークを活用したループ並列化プログラムを機械語コードまたはCプログラムとして生成する。

#### 2.3 並列化フレームワークの仕様

COINSの並列化フレームワークについて説明する。あげてある項目をすべてを実現 するのではなく、必要に応じて作成すればよいこととする。並列化のフレームワーク には、do-all型のループ並列化のフレームワークとその他のフレームワークがあるが、 以下ではdo-all型についてのみ説明する。

###### 変数定義

次の変数を宣言しておく必要がある。

- スレッドオブジェクト表

  coinsThread_t coinsThread[COINS_MAX_NUMBER_OF_THREADS];

- スレッド数

  int coinsNumberOfThreads;

###### 型宣言

- スレッドオブジェクトの型

  構造体で要素として

  int 型の識別子 ( マスタを0とした昇順の連番) id、

  を含むこと。

    　　coinsThread_t:

    　　  example:

        　typedef struct {
                int id;　　// スレッド ID であり、マスタが0で連番になっている。
                pthread_t th;　// pthread を利用する場合の例。
                pthread_barrier_t barrier; // pthread を利用する場合の例。
           } coinsThread_t;

- mutex lock 型

  mutx lock オブジェクトである。

          coinsThreadMutex_t;

          example:
           typedef coinsThreadMutex_t pthread_mutex_t; // pthread を利用する場合の例。

###### 関数定義

関数定義は、実行時に呼び出されるランタイムルーチンとして実現するものと、 コンパイル時にインライン展開できるものは展開してしまうもののの２種類を用意する。

- 全体の初期化

  プログラムの開始時に必要な初期化を行う。場合によってはスレッドを ここで起動する。引数 initType は次のことを区別するものとする。

  1. ロックもバリア同期も明に行わない。
  2. バリア同期を明に行う。
  3. ロックを明に行う。
  4. バリア同期もロックも明に行う。

        int coinsThreadInitiate(int initType);

- ループ並列化用の初期化

  １つのループの並列化に必要な初期化を行うとともに、実行環境に合わせて実際の 並列度を決めて返却値とする。

        int coinsThreadInit(int maxNumberOfThreads);

- 全体の終了

  プログラムの終了時に必要な処理を行う。場合によってはスレッドをここで終了する。

        void coinsThreadEnd();

- スレッド上で実行する関数のフォーク

         int coinsThreadFork(coinsThread_t *thread,
                             void *(*startRoutine)(void *),
                             void *argv);

- スレッド上で実行する関数のジョイン（終了待ち）

         int coinsThreadJoin(coinsThread_t *cth);

- スレッドオブジェクトの等価性チェック

         int coinsThreadEqual(coinsThread_t *cth1,
                              coinsThread_t *cth2);

- スレッドIDの取り出し

         int coinsThreadSelfId();

- スレッドオブジェクトの取り出し

         coinsThread_t * coinsThreadSelf();

###### 関数定義（ループ並列化）

- スレッドをフォークするループの前処理

         void coinsThreadPreprocessForDoAllLoop(
                                   int numberOfThreads,
                                   long loopLength,
                                   long *indexFrom,
                                   long *indexTo)

- スレッドをジョインした後の後処理

         void coinsThreadPostprocess(int numberOfThreads,
                                     int loopLength);

- フォークされたループ部分の前処理

         void coinsThreadPreprocessForDoAllThread();

- フォークされたループ部分の後処理

         void coinsThreadPostprocessForDoAllThread();

###### 関数（その他）

- スレッドの自主的終了

  スレッドの処理をこの関数をもって終了する。

         void coinsThreadExit();

- スレッドの強制終了

  指定したスレッドを強制終了させる。

         void coinsThreadCancel(coinsThread_t *cth);

- ロック

         int coinsThreadMutexLock(coinsThreadMutex_t *coinsMutex);

- ロックを試みる

         int coinsThreadMutexTryLock(coinsThreadMutex_t *coinsMutex);

- アンロック

         int coinsThreadMutexUnlock(coinsThreadMutex_t *coinsMutex);

### 3. 並列化の実装環境

#### 3.1. マルチコアに対応した参照実装

マルチコアの機種に対するTMDを作成し、COINS既存部のループ並列化解析結果 に基づいて、並列実行用の機械命令を生成できるようにした。 具体的には次のとおりである。

- ソフトCPUコアが実装可能なFPGA開発ボードを実機として、その開発 環境を整備した。具体的にはXilinx社製のVertex-4なるFPGA上に複数のCPUコ アを載せた実装を用意した。
- CPUコアとしては MicroBlazeを活用した。
- MicroBlaze用TMDを実現した。
- すべての変数およびスタックフレームも共有メモリ（DDR-SDRAM）上に置 く方式でハードウェア設計を行った。
- この環境に合わせたループ並列化を実現するために、並列化フレームワーク に合わせて並列化実行可能コードを生成し、それをFPGA開発ボードにダウンロードし、 実行可能であることを確認した。

#### 3.2. 参照実装によるテスト

上記の参照実装を利用し、実際に並列実行を行わせて、その効果を確認した。 具体的には次のとおりである。

- do-all型ループ並列化が可能なプログラムを用意し、プラグマを付けた。
- MicroBlaze用フレームワークをOSを使わない実行時ルーチンとして実装した。
- do-all型ループ並列化可能なプログラムをコンパイルし、MicroBlaze 用フレームワークとリンクし、MicroBlaze上で並列動作するプログラムを生成 した。
- do-all型ループ並列化可能なプログラムとして画像処理プログラムを用意し、 それによる並列化実験を行った。
- リバモアループをC言語化した上で並列化コードを生成し、並列化実行を確 認した。

この実験により、３つのMicroBlazeプロセッサを１チップに載せたものでは、 Laplacian filterのようなメモリアクセスの負荷が演算の負荷にくらべて 相対的に大きくないプログラムであれば、それなりの実行性能（Laplacian filterで2.9倍）が得られ、オーバーヘッドの少ない並列化が実現できることを 確認できた。

### 4. 並列化向けのHIR変換

#### 4.１．並列化するループの選択

ここで述べるHIR並列化は、並列化のフレームワークに 合わせた並列化実行時ルーチンを用いることにより、OpenMPコンパイラなどを使わなくても、 ループを並列実行可能にするための変換を行うものである。すなわち、この変換を 行ったHIRからバックエンドで生成した機械語コードや、hir2cで生成したCプログラムは、 並列化実行時ルーチンと合わせてリンクすることにより、並列実行可能となる。

並列化変換は

1. ループ解析
2. HIRに対するOpenMP向け指示文挿入やinduction変数正規化などの変換
3. OpenMP向け指示文とソースに記入された並列化pragmaに合わせて、 機械語コードないしCプログラムを生成

の３つの段階を経て行う。

この変換ははdo-all型の並列化に限定し、集合体としては配列だけを 対象としており、構造体や共用体を含むループは並列化の対象としない。上記の1と2は COINSのループ並列化の章で 説明されているので、以下では3の並列化変換について説明する。

並列化変換の対象とする副プログラムは、次のいずれかのプラグマによって指定す る。

        #pragma parallel doAllFunc f1 f2 ... fn

これによって f1 f2 ... fn を並列化変換の対象とする。

        #pragma parallel doAllFuncAll

これによって コンパイル単位内のすべての副プログラムを並列化変換の対象とする。

（無差別にループ解析をすると、並列化の対象としない副プログラムに大きいものがあ る場合、無用な並列化解析に長大な時間がかかる。）

並列化するループもすべてプラグマで指定する。 解析によって並列化可能と判定されても プラグマで並列化の指定がなければ並列化しない。 （ループ解析は並列化可否を判定するものであって、並列化によって高速化される可能性までは判定しない。）

並列化するループは、次のような、並列化(doAll)または強制並列化(forceDoAll)を表すpragma

        #pragma parallel doAll
        #pragma parallel forceDoAll ....

のいずれかの指定の直後にある forループとする。

        #pragma parallel doAll

の直後のループでも、ループ解析によって並列化可能と判定されなかった場合には並列化されない。

        #pragma parallel forceDoAll ....

は、ループ解析で並列化可能と判定されなくても並列化する指定であり、 .... の部分でprivate, last private, reductionの各指定を次のように与える。

        #pragma parallel forceDoAll private (x1 x2 ... ) lastPrivate (y1 y2 ...) \
           (reduction ((op1 z1 v1) (op2 z2 v2) ... )

ここで、x1, x2, ... はprivate変数名、y1, y2, ... はlast private変数名、z1, z2, ... はreduction変数名で、op1, op2, ... はreductionの演算子を"+", "*", "-" , "max", "min", "maxIndex", "minIndex"のいずれか の文字列定数によって表すとする。v1, v2, ... は演算子として "maxIndex", "minIndex" のいずれかを指定したときにのみ必要な もので、１次元の配列変数を表す。ループ解析の結果とforceDoAllの指定内容が 合わない場合はforceDoAllのプラグマで指定された内容が優先する。 forceDoAllの詳しい説明はあとで述べる。

変数指定のないprivate指定 (private )、変数指定のないlastPrivate指定 (lastPrivate )、 reduction項目の指定のないreduction指定 (reduction ) は省略できる。

並列化用プラグマの構文は次の通りである。

    pragmaForParallelization →
        #pragma parallel init
      | #pragma parallel end
      | #pragma parallel doAllFunc  SubprogramSequence
      | #pragma parallel doAllFuncAll
      | #pragma parallel doAll
      | #pragma parallel forceDoAll ParallelSpecSequence
    SubprogramSequence →
        subprogramId
      | subprogramId SubprogramSequence
    ParallelSpecSequence →
        ParallelSpec ParallelSpecSequence
      | ε
    ParallelSpec →
        (private VariableSequence)
      | (lastPrivate VariableSequence)
      | (reduction ReductionSpecSequence)
    VariableSequence →
        variableId VariableSequence
      | ε
    ReductionSpecSequence →
       ReductionSpec ReductionSequence
      | ε
    ReductionSpec →
        (Operator1 variableId)
      | (Operator2 variableId arrayId)
    Operator1 →
        "+" | "*" | "-" | "max" | "min"
    Operator2 →
        "maxIndex" | "minIndex"

#### 4.2．スレッドによる並列化

並列化されたループは、複数のスレッドで実行されることになる。その個々のスレッド が実行するプログラムは、１つの副プログラムの形をとるようにする。そうするために、 並列化するループの各々を変形し、１つの副プログラムとして分離する。

今回実現するdo-all型の並列化では、スレッドを起動する側のプログラムが１つあり、 それを親 (master) と呼ぶことにし、起動されたスレッドを子 (slave) と呼ぶことにする。スレッドの合流処 理は親が行う。スレッドには0, 1, 2, 3, ... のスレッド番号がついていて、 スレッドとスレッド番号の対応付けは親が行う。do-all型の 並列化では、各スレッドは（正規化された）induction変数の重なり合わない値域に対す る処理を実行する。その値域分割は、偶数、奇数というような分け方をするのではなく、 ある始値からある終値までの間の整数値全部というような分け方をするものとする。

#### 4.3．並列化ループの副プログラム化

各スレッドに対応する副プログラムでは、スレッド間で共有される大域メモリとスレッ ドごとに個別に持つ局所メモリが利用できる。大域変数は大域メモリに置き、ヒープも大 域メモリにとる。スタックフレームは、通常は局所メモリに置くが、大域メモリに置くこ とができる場合もある。スタックフレームを大域メモリに置くときは、スレッドごとに別 領域となるように割り付る。このようなメモリ配置は、OSやローダー、あるいはスレッド 起動のプログラムが行う。

スレッドごとに別物とする変数も、並列化変換の際に、それをスレッド番号を添字とす る配列、あるいは大域メモリのスレッド別領域を指すポインタとして表現すれば、大域メ モリに置くことができる。局所メモリの少ないマシンでは、do-all型ループで値の設定さ れる配列は大域メモリに置かれていることが望ましい。

並列化副プログラムへのデータ受け渡しは、大域変数または引数によって行う。受け渡 しにはデータのコピーを必要とする場合と必要としない場合がある。そのやりかたを検討 するために、並列化変換の前と後における変数の置き場所と表現方法について整理する。ここで、右 端の＊印は、後で述べる制約事項により、今回の実現では除外するものを示す。 置き場所や変数表現が変換前と変換後で異なるものについては、副プログラム生成時に変換後に必 要とする変数の宣言を生成する。ただし、＃のついた書き戻し操作は、後述する技法 により不要となるので、それに対する宣言も不要となる。

###### 置き場所ないし変数表現

    　　並列化変換前　　　　　　並列化変換後
    　private
    　　局所変数　　　　　　　　局所変数
    　　大域スカラー変数　　　　局所変数
    　　大域配列　　　　　　　　スレッド別大域配列
    　　　　　　　　　　　　　　（スレッドごとに別領域に置かれる）
    　　仮引数　　　　　　　　　局所変数　＊
    　last private
    　　局所スカラー変数　　　　局所スカラー変数（書き戻し＃）
    　　局所配列　　　　　　　　スレッド別大域配列（書き戻し＃）
    　　大域スカラー変数　　　　局所スカラー変数（書き戻し＃）
    　　大域配列　　　　　　　　スレッド別大域配列（書き戻し＃）
    　　ポインタでない仮引数　　スレッド別大域変数（書き戻し＃）　＊
    　　ポインタ仮引数　　　　　スレッド別大域変数（書き戻し＃）　＊
    　　配列仮引数　　　　　　　Cにはない　＊
    　reduction
    　　局所変数　　　　　　　　局所変数＋値受け取り用大域変数（合成）
    　　大域変数　　　　　　　　局所変数＋値受け取り用大域変数（合成）
    　　ポインタでない仮引数　　局所変数＋値受け取り用大域変数（合成）　＊
    　その他の変数
    　　ループの入り口ブロックでLiveInするもの（値参照のみ）
    　　　局所スカラー変数　　　大域スカラー変数（書き写し）
    　　　局所配列　　　　　　　大域ポインタ変数（アドレス設定）
    　　　　　　　　　　　　　　または大域変数（書き写し）
    　　　大域変数　　　　　　　大域変数
    　　　値渡し仮引数　　　　　大域変数（書き写し）
    　　　参照渡し仮引数　　　　大域ポインタ変数（参照値設定）
    　　　配列仮引数　　　　　　Cにはない　＊
    　　ループの出口ブロックでLiveOutするもの（値設定あり）
    　　　局所変数　　　　　　　大域ポインタ変数（アドレス設定）
    　　　　　　　　　　　　　　または大域変数（書き戻し）
    　　　大域変数　　　　　　　大域変数
    　　　値渡し仮引数　　　　　大域変数（書き戻し）
    　　　参照渡し仮引数　　　　大域ポインタ変数（参照値設定）
    　　　配列仮引数　　　　　　Cにはない　＊
    　　LiveInもLiveOutもしないもの
    　　　局所変数　　　　　　　局所変数
    　　　大域変数　　　　　　　大域変数
    　　　仮引数　　　　　　　　仮引数

###### 制約

今回の並列化対象はCプログラムであり、次の処理を含むループは並列化の対象に入ら ないものとする。（ただし、強制並列化ではその限りでない。）

- ポイント先への代入
- ポインタ仮引数の参照
- 仮引数への値の代入
- ループ内でヒープ領域を取得
- 配列仮引数に対する値の設定、参照
- 構造体や共用体の出現
- first private変数, shared変数の出現
- 数学関数以外（副作用なしと宣言されているもの以外）の副プログラム呼び出し

###### プラグマによる制約の緩和

1. 配列仮引数

   C言語では配列仮引数の第１添字の範囲を限定しないので、配列仮引数を使うループは 副作用のおそれがあるとして並列化の対象から除外しているが、副作用のおそれがないと プラグマで指定すれば、除外しない。

           #pragma optControl safeArray var1 var2 ...

   という形のプラグマを与えると、配列変数var1, var2, ... の添字がそれらの変数に割り 当てられたメモリ領域を逸脱するような値をとることはないと宣言されたとみなされ、こ れらの配列を含むループは並列化の対象となる。このプラグマは、指定する変数 var1, var2, ... と同じスコープで指定しなければならない。仮引数の場合は対応する副プログ ラムの中で与える。大域配列と局所配列のみを含むループはもともと並列化の対象として いるが、それらに対して上記プラグマを指定しても差し支えない（最適化に関する制約が 緩和されることがあり得る）。

2. 副作用なし関数

   副プログラムは一般に副作用を伴うとして、数学関数以外の副プログラム呼び出しを含 むループは並列化の対象から除外しているが、

           #pragma optControl functionsWithoutSideEffect func1 func2 ...

   という形のプラグマで指定した関数 func1, func2, ... は副作用がないと見なして、それ を呼び出すループは並列化の対象とする。このプラグマは、コンパイル単位の先頭部分、 すなわち関数定義の外側で与える必要がある。C言語の場合、もともと副作用がないと 見なしている数学関数は、「JIS X3010-1993 (ISO/IEC 9899:1990) プログラム言語C」 に記載されている次のものである。

           acos, asin, atan, atan2, cos, sin, tan, cosh, sinh, tanh,
           exp, frexp, ldexp, log, log10, modf, pow, sqrt, ceil, fabs, floor, fmod

   副作用なしと宣言されている関数と同名の副プログラムを副作用ありと宣言しなおすには 次のプラグマを使う。

           #pragma optControl functionsWithSideEffect func1 func2 ...

###### 制御情報の受け渡し

並列化フレームワークでは、次の情報を大域変数としてスレッド間で共有する。

- スレッド数 (coinsNumberOfThreads)
- スレッド識別子配列 (coinsThreadIdArray[最大スレッド数])

最大スレッド数は、コンパイル時のコマンドで

      -coins:parallelDoAll=4

のように、parallelDoAllのパラメータとして指定する。スレッド数は、最大スレッド数の範囲内 でループごとに並列化実行時ルーチンで定める。スレッド識別子は、coinsThreadId() という関数で求めることができるが、通常、プログラムの走行開始時に求めてスレッド 識別配列にスレッド番号順に入れておき、何度も求める必要がないようにする。

ループに対応して生成された副プログラムには、次の情報を引数として渡す。

- スレッド番号（スレッド識別子配列のインデックス）
- induction変数の始値と終値
- reduction変数の書き戻し先

その他の情報は大域変数として渡す。

###### 計算データの受け渡し

- 上記で書き写しの表示のあるものはスレッド起動時に起動する側（親）から 起動される側（子）へデータをコピーして渡す。
- 上記で書き戻しの表示のあるものはスレッド終了時に子から親へ データをコピーして戻す。
- 上記でアドレス設定、参照値設定の表示のあるものは、スレッド起動時に 起動する側（親）が起動される側（子）へアドレスや値を設定して渡す。
- 書き写し、書き戻し、アドレス設定、参照値設定のいずれの表示もないものに対しては データの授受を行わない。
- スレッド個別領域（スレッドの局所変数やスレッド別大域変数）への 書き写しは、大域変数または仮引数として受け取ったデータを子が スレッド個別領域にコピーして使う。
- スレッド個別領域からの書き戻しは、大域変数または仮引数として受け取った アドレスに子が書き込みを行う。
- 親の局所変数からスレッド間共有の大域変数への書き写しは親が行う。
- 局所変数をそのアドレスを表す大域ポインタ変数に変換した場合、その 局所変数の設定・参照は、大域ポインタ変数のポイント先に対する設定・参照 におきかえる。大域ポインタ変数へのアドレス設定は親が行う。
- 局所変数のアドレスを引数または大域ポインタ変数として渡すのは、 スタックフレームをスレッド別大域メモリに置く場合に限って使える 方法であり、スタックフレームを局所メモリに置く場合は、ポインタ ではなく局所変数と同じ型の大域変数を割り付けて、書き写し、書き戻し の操作を行う必要がある。
- Last privateなスカラー変数の書き戻しは、最後のスレッド（induction変数の 最後の値を含む値域を担当するスレッド）でのみ子が行う。そのために 親の変数アドレスを引数として子に渡す。 実際には、最後のスレッド番号に対応するスレッドを親が担当すること により、＃印のついた書き戻し操作を不要となるようにする。
- Last privateな配列では、スレッド別大域変数から親の配列への書き戻しを 親が行う。それを子が行う場合は、親の局所配列が書き戻し先であればその 配列のアドレスを引数として子へ渡す。
- Reduction変数は、スレッドごとの算出値を受け取るスレッド別大域変数 （スレッド番号を添字とする配列）を用意し、親は子に書き戻し先の アドレスを引数として渡す。子は局所変数を使って担当添字範囲のreduction 値を計算し、渡された書き戻し先に算出値を書き込む。親は合流点で 各スレッドでの値から全体の値を合成する。合成の仕方は演算子に よって異なる。
- 子におけるreduction変数の初期値は、演算子が +, - であれば０、* であれば １とする。
- Induction変数の子における初期値は、正規化されたinduction変数の始値 にステップ値をかけたものに変換前のinduction変数の初期値を加えた ものとして計算する。 正規化されたinduction変数は0, 1, 2, ... というように変化するものとする。

#### 4.4．使い方

##### プログラムの構成

mainプログラムを含むコンパイル単位ならびに並列化対象のループを含むコンパイル 単位は、並列化フレームワークに基づくinclude用ヘッダファイル をincludeしなければならない。このincludeに先だって、mainを含むコンパイル単位には

        #ifndef MAIN
        #define MAIN
        #endif

という定義文がなければならない。mainを含まないコンパイル単位には、上記定義文が あってはならない。 これは、includeされる大域変数を実体を定義するものとするか、外部参照するものとするかの区別ができるようにするためである。

並列化されたプログラムを実行するには、生成されたオブジェクトプログラムまたは hir2cで生成されたCプログラムに対して、並列化フレームワークに基づく並列化実行時 ルーチンを合わせてリンクしなければならない。

##### プラグマの挿入

並列化するループの実行に先立つ位置に（mainプログラムの先頭部に）

        #pragma parallel init

が１つだけなければならない。また、並列化するループがすべて終了している位置に （mainプログラムの終わり部分に）

        #pragma parallel end

が１つだけなければならない。 並列化するループを含む副プログラムを、コンパイル単位の先頭部分で（大域宣言の 部分で）

        #pragma parallel doAllFunc f1 f2 ... fn
        #pragma parallel doAllFuncAll

のいずれかの方法で指定する。

並列化するループの前に

        #pragma parallel doAll
        #pragma parallel forceDoAll ...

のいずれかのプラグマを置く。そのプラグマの後ろで最初に出会ったforループが並列化 対象となる。

プラグマは複数行に分けないで１行に書く。

##### コンパイルコマンドでの指定

コンパイルするときに

        -coins:parallelDoAll=m
        -coins:parallelDoAll=m,hir2c

のいずれかの形で並列化の指示を行う。mは最大並列度を表す整数値で、=mを省略する と2となる。hir2cを指定すると、並列化したHIRからCプログラムを生成する。それは ソースプログラムファイルが xx.c で与えられていると xxx-loop.c というファイルとし て生成される。

コンパイルコマンドで parallelDoAll を指定しないと、並列化プラグマが挿入されていても並 列化されない。

##### 強制並列化

プラグマで

        #pragma parallel forceDoAll (private x1 x2 ... ) (lastPrivate y1 y2 ...)
           (reduction ((op1 z1 v1) (op2 z2 v2) ... )

と指定したループは、ループ解析で並列化可能と判定されていなくても並列化する。し たがって、前記の制約条件に必ずしも合っていなくても、ユーザ責任で並列化する。そ のため、次の諸点を守らなければならない。

- private, lastPrivate, reductionの指定は遺漏無く正確に指定する。 （この指定がループ解析の結果と合っていなくても、pragmaでの 指定の通りに並列化する。）
- private変数としては、相互干渉を防ぐためにスレッドごとに個別に持つ変数のうち、 ループ内での値がループの外では参照されないものを指定する。
- Last-private (lastPrivate) 変数としては、スレッドごとに個別に持つべき変数のうち、ループ最終回の値がループ の外で参照されるものを指定する。
- Reduction変数としては、配列要素の値の総和("+")、初期値から配列要素の値を 差し引く演算("-")、配列要素の値を掛け合わせる演算("*")、最大値("max")、 最小値("min")、最大値をとるときの配列添字値("maxIndex")、 最小値をとるときの配列添字値("minIndex")の算出値を入れる変数を指定する。 maxIndex、minIndexを指定するときは、その添字のつく配列をもう１つのパラメータと して指定する。その配列は１次元配列でなければならない。（後述の例参照）
- ループのinduction変数は正規化されていなければならない。 （0, 1, 2, ... というように、始値が0で増分値が1でなければならない。）
- Reduction変数が指定されている場合、演算子に合わせてその値を 　算出する文がループ内になければならない。
- １つのループ内のreduction変数の数は当面２までとする。

#### 4.5. 並列化フレームワークに基づくinclude用ヘッダファイル

並列化用のヘッダファイルには、

        coinsParallelFramework.h
        coinsParallelFrameworkInline.h

の２つがある。それらの違いは、後者はインライン展開によってオーバーヘッドを少なく している点である。それ以外の内容は同じなので、ここでは前者のpthread版をあげる。 それらのヘッダファイルで宣言されているものの実体を定義することは、実行環境に 合わせて並列化フレームワークを実現する人に任されている。

    /* coinsParallelFramework.h  pthread version */

    #ifndef COINS_PARALLEL_FRAMEWORK_H
    #define COINS_PARALLEL_FRAMEWORK_H

    #ifndef COINS_MAX_NUMBER_OF_THREADS
    #define COINS_MAX_NUMBER_OF_THREADS 4
    #endif

    #ifdef MAIN
    #define Extern
    #else
    #define Extern extern
    #endif

    #include <sys/types.h>

    /** typedef struct __pthread_t {char __dummy;} *pthread_t; /* defined in type.h */

    typedef struct {
      int id;
      pthread_t th;
    } coinsThread_t;

    typedef struct {
      int id, from, to, step;
    } coinsThreadLoopParam;

    Extern coinsThread_t coinsThread[COINS_MAX_NUMBER_OF_THREADS];

    Extern int coinsThreadInit( int numberOfMaximumThreads);

    Extern int coinsThreadFork(coinsThread_t *thread,
                         void *(*startRoutine)(void *), void *argv);
    Extern int coinsThreadJoin(coinsThread_t *cth);

    Extern int coinsThreadEqual(coinsThread_t *cth1, coinsThread_t *cth2);

    Extern int coinsThreadSelfId();

    Extern coinsThread_t * coinsThreadSelf();

    Extern int coinsNumberOfThreads;
    Extern int coinsThreadEnd();
    Extern int coinsThreadIdArray[COINS_MAX_NUMBER_OF_THREADS];
    Extern int coinsThreadSelfIdOfMaster;
    Extern void
    coinsThreadPreprocessForDoAllLoop(int numberOfThreads,
                    long loopLength, long *indexFrom, long *indexTo);
    Extern void coinsThreadPostprocess(int totalNumberOfThreads,
                    long loopLength);
    Extern int coinsThreadForkForDoAll(coinsThread_t *thread,
                    void *(*startRoutine)(int, long, long, void*, void *),
                    int threadId, long indexFrom, long indexTo, void*, void* );
    Extern void coinsThreadPreprocessForDoAllThread();

    Extern void coinsThreadPostprocessForDoAllThread();

    #endif

#### 4.6. 例

##### 4.6.1 ループ解析に基づく並列化

###### ソースプログラム

    /* lparallel7.c test loop parallel for CoinsEmb with last private and reduction */
    /*   Variable x used in a loop is declared as local and other arrays are declared as global */
    #pragma parallel doAllFunc main

    #ifndef MAIN
    #define MAIN
    #endif

    #include "coinParallelFramework.h"

    int printf(char*, ...);
    float c[50],z[50][100];
    int k;

    int main(){
      float x[50];
      int i,j,n;
      float sum;
    #pragma parallel init
      n=50;k=0;
    #pragma parallel doAll
      for (i=0; i<n ; i++) {
        x[0]=0 ;
        x[1]=10 ;
        for (j=2; j<50 ; j++) {
          x[j] = (x[j-1] + x[j-2])/2
          z[i][k] = x[j] ;
        }
        k=k+2;
      }
      printf(" = %d\n", k);
    #pragma parallel doAll
      sum = 0.0;
      for (i = 0; i < n; i++) {
        sum = sum + x[i];
      }
    #pragma parallel end
      printf("sum = %f\n", sum);
    }

###### ループ解析に基づく変換結果のC表現

    # 1 "lparallel7-loop.c"
    # 1 "<built-in>"
    # 1 "<command line>"
    # 1 "lparallel7-loop.c"
    # 55 "lparallel7-loop.c"
    struct __pthread_t {
    char __dummy;
     };
    struct ____5 {
    int id;
    struct __pthread_t * th;
     };
    struct ____6 {
    int id;
    int from;
    int to;
    int step;
     };
     struct ____5 coinsThread[4];
    extern int coinsThreadInit ( int ) ;
    extern int coinsThreadFork ( struct ____5 * ,void * (* )( void * ),void * ) ;
    extern int coinsThreadJoin ( struct ____5 * ) ;
    extern int coinsThreadEqual ( struct ____5 * ,struct ____5 * ) ;
    extern int coinsThreadSelfId ( ) ;
    extern struct ____5 * coinsThreadSelf ( ) ;
     int coinsNumberOfThreads;
    extern int coinsThreadEnd ( ) ;
     int coinsThreadIdArray[4];
     int coinsThreadSelfIdOfMaster;
    extern void coinsThreadPreprocessForDoAllLoop ( int ,long ,long * ,long * ) ;
    extern void coinsThreadPostprocess ( int ,long ) ;
    extern int coinsThreadForkForDoAll ( struct ____5 * ,void * (* )( int ,long ,long ,void * ,void * ),int ,long ,long ,void * ,void * ) ;
    extern void coinsThreadPreprocessForDoAllThread ( ) ;
    extern void coinsThreadPostprocessForDoAllThread ( ) ;
    extern int printf ( char * , ... ) ;
     float c[50];
     float z[50][100];
     int k;
     int main ( ) ;
     void * main_loop_0 ( int ,long ,long ,void * ,void * ) ;
     int _k_global_0;
     void * main_loop_1 ( int ,long ,long ,float * ,void * ) ;
     int _n_global_0;
     float * _x_global_0;
    int main( )
    {
        float x[50];
        int i;
        int j;
        int n;
        float sum;
        int _var1;
        long _index_from_0[4];
        long _index_to_0[4];
        long _I_0;
        long _index_from_1[4];
        long _index_to_1[4];
        long _I_1;
        float _sum_receiver_0[4];
        int _indexR_0;
        coinsNumberOfThreads = coinsThreadInit( (int )4);
        n = (int )50;
        k = (int )0;

        {
            {
                i = (int )0;
            }
            coinsThreadPreprocessForDoAllLoop( coinsNumberOfThreads,(long )(n),((_index_from_0)),((_index_to_0)));
            {
                _k_global_0 = k;
            }
            for ( _I_0 = (int )0;(_I_0) < (((coinsNumberOfThreads) - ((int )1))); _I_0 = ((_I_0) + ((int )1)))
            {
                coinsThreadForkForDoAll( (&(coinsThread[_I_0])),main_loop_0,coinsThreadIdArray[_I_0],_index_from_0[_I_0],_index_to_0[_I_0],(int )0,(int )0);
            }
            _lab17:;
    #pragma omp parallel for lastprivate(x,k,i) private(j)

            for ( i = _index_from_0[((coinsNumberOfThreads) - ((int )1))];(i) < (_index_to_0[((coinsNumberOfThreads) - ((int )1))]); i = ((i) + ((int )1)))
            {
                k = ((((int )2) * (i)) + ((int )0));
                x[(int )0] = (float )((int )0);
                x[(int )1] = (float )((int )10);
                for ( j = (int )2;(j) < ((int )50); j = ((j) + ((int )1)))
                {
    _lab22:;
                    {
                        x[j] = (((x[((j) - ((int )1))]) + (x[((j) - ((int )2))]))) / ((float )((int )2));
                        z[i][k] = x[j];
    _lab23:;
                    }
                }
                _lab24:;
    _lab25:;
            }
            _lab29:;
            coinsThreadPostprocess( coinsNumberOfThreads,n);
        }
        k = ((((int )2) * (i)) + ((int )0));
        (&(printf))( (("k = %d \n")),k);

        sum = (float )((double )0.0);
        {
            {
                i = (int )0;
            }
            coinsThreadPreprocessForDoAllLoop( coinsNumberOfThreads,(long )(n),((_index_from_1)),((_index_to_1)));
            {
                _n_global_0 = n;
                _x_global_0 = ((x));
            }
            for ( _I_1 = (int )0;(_I_1) < (((coinsNumberOfThreads) - ((int )1))); _I_1 = ((_I_1) + ((int )1)))
            {
                coinsThreadForkForDoAll( (&(coinsThread[_I_1])),main_loop_1,coinsThreadIdArray[_I_1],_index_from_1[_I_1],_index_to_1[_I_1],(&(_sum_receiver_0[_I_1])),(int )0);
            }
            _lab47:;
    #pragma omp parallel for reduction(+:sum)

            for ( i = _index_from_1[((coinsNumberOfThreads) - ((int )1))];(i) < (_index_to_1[((coinsNumberOfThreads) - ((int )1))]); i = ((i) + ((int )1)))
            {
                sum = ((sum) + (x[i]));
    _lab51:;
            }
            _lab55:;
            coinsThreadPostprocess( coinsNumberOfThreads,n);
            for ( _indexR_0 = (int )0;(_indexR_0) < (((coinsNumberOfThreads) - ((int )1))); _indexR_0 = ((_indexR_0) + ((int )1)))
            {
                sum = ((sum) + (_sum_receiver_0[_indexR_0]));
            }
            _lab69:;
        }

        coinsThreadEnd();
        (&(printf))( (("sum = %f \n")),(double )(sum));
    }
    void * main_loop_0( int _threadId_0,long _indexFrom_0,long _indexTo_0,void * _voidPtr_0,void * _voidPtr_1 )
    {
        int i;
        int n;
        int k_0;
        float x[50];
        int j;
        coinsThreadPreprocessForDoAllThread();
        k_0 = _k_global_0;
        {
            i = (int )0;
        }
        for ( i = _indexFrom_0;(i) < (_indexTo_0); i = ((i) + ((int )1)))
        {
            k_0 = ((((int )2) * (i)) + ((int )0));
            x[(int )0] = (float )((int )0);
            x[(int )1] = (float )((int )10);
            for ( j = (int )2;(j) < ((int )50); j = ((j) + ((int )1)))
            {
    _lab34:;
                {
                    x[j] = (((x[((j) - ((int )1))]) + (x[((j) - ((int )2))]))) / ((float )((int )2));
                    z[i][k_0] = x[j];
    _lab35:;
                }
            }
            _lab36:;
    _lab37:;
        }
        _lab41:;
        coinsThreadPostprocessForDoAllThread();
    }
    void * main_loop_1( int _threadId_0,long _indexFrom_0,long _indexTo_0,float * sum_0,void * _voidPtr_0 )
    {
        int i;
        float sum;
        coinsThreadPreprocessForDoAllThread();
        sum = (float )0.0;
        {
            i = (int )0;
        }
        for ( i = _indexFrom_0;(i) < (_indexTo_0); i = ((i) + ((int )1)))
        {
            sum = ((sum) + ((_x_global_0)[i]));
    _lab59:;
        }
        _lab63:;
        (*(sum_0)) = sum;
        coinsThreadPostprocessForDoAllThread();
    }

##### 4.6.2 強制並列化による並列化の例

###### ソースプログラム

    /* lparaForce1.c test forceDoAll */
    #pragma parallel doAllFunc main

    #ifndef MAIN
    #define MAIN
    #endif

    #include "coinsParallelFramework.h"

    int printf(char*, ...);
    int c[50],z[50][100];
    int k;

    int main()
    {
      int x[50];
      int i,j,n;
      int sum;
      int max, min, maxInx, minInx;
    #pragma parallel init
      n=50;
      k=100;
    #pragma parallel doAll
      sum = 0;
      for (i=0; i<n ; i++) {
        x[i]= k + i;
        c[i]= i * i;
        k=k-2;
        sum = sum + x[i];
      }
      printf("k = %d sum = %d \n" k, sum);
    #pragma parallel forceDoAll (private ) (lastPrivate ) (reduction ("max" max) ("min" min))
      max = x[0];
      min = x[0];
      for (i = 0; i < n; i++) {
       if (x[i] > max)
         max = x[i];
       if (x[i] < min)
         min = x[i];
      }
      printf("max = %d min = %d \n" max, min);
      maxInx = 2;
      minInx = 2;
      max = x[2];
      min = x[2];
    #pragma parallel forceDoAll (private ) (lastPrivate ) (reduction ("maxIndex" maxInx x) ("minIndex" minInx x))
      for (i = 0; i < n; i++) {
       if (x[i] > max) {
         max = x[i];
         maxInx = i;
       }
       if (x[i] < min) {
         min = x[i];
         minInx = i;
       }
      }
      sum = c[0];
      for (i = 1; i < n; i++) {   /* Loop with no pragma */
        sum = sum + c[i];
      }
      printf("maxInx = %d minInx = %d sum = %d\n" maxInx, minInx, sum);
    #pragma parallel end
      return 0;
    }

###### 強制並列化による変換結果のC表現

    # 1 "lparaForce1-loop.c"
    # 1 "lt;built-in>"
    # 1 "lt;command line>"
    # 1 "lparaForce1-loop.c"
    # 55 "lparaForce1-loop.c"
    struct __pthread_t {
    char __dummy;
     };
    struct ____5 {
    int id;
    struct __pthread_t * th;
     };
    struct ____6 {
    int id;
    int from;
    int to;
    int step;
     };
     struct ____5 coinsThread[4];
    extern int coinsThreadInit ( int ) ;
    extern int coinsThreadFork ( struct ____5 * ,void * (* )( void * ),void * ) ;
    extern int coinsThreadJoin ( struct ____5 * ) ;
    extern int coinsThreadEqual ( struct ____5 * ,struct ____5 * ) ;
    extern int coinsThreadSelfId ( ) ;
    extern struct ____5 * coinsThreadSelf ( ) ;
     int coinsNumberOfThreads;
    extern int coinsThreadEnd ( ) ;
     int coinsThreadIdArray[4];
     int coinsThreadSelfIdOfMaster;
    extern void coinsThreadPreprocessForDoAllLoop ( int ,long ,long * ,long * ) ;
    extern void coinsThreadPostprocess ( int ,long ) ;
    extern int coinsThreadForkForDoAll ( struct ____5 * ,void * (* )( int ,long ,long ,void * ,void * ),int ,long ,long ,void * ,void * ) ;
    extern void coinsThreadPreprocessForDoAllThread ( ) ;
    extern void coinsThreadPostprocessForDoAllThread ( ) ;
    extern int printf ( char * , ... ) ;
     int c[50];
     int z[50][100];
     int k;
     int main ( ) ;
     void * main_loop_0 ( int ,long ,long ,int * ,void * ) ;
     int _k_global_0;
     int * _x_global_0;
     void * main_loop_1 ( int ,long ,long ,int * ,int * ) ;
     int _max_global_0;
     int _min_global_0;
     int _n_global_0;
     int * _x_global_1;
     void * main_loop_2 ( int ,long ,long ,int * ,int * ) ;
     int _minInx_global_0;
     int _maxInx_global_0;
     int _n_global_1;
     int * _x_global_2;
     int _max_global_1;
     int _min_global_1;
    int main( )
    {
        int x[50];
        int i;
        int j;
        int n;
        int sum;
        int max;
        int min;
        int maxInx;
        int minInx;
        int _var1;
        long _index_from_0[4];
        long _index_to_0[4];
        long _I_0;
        int _sum_receiver_0[4];
        int _indexR_0;
        long _index_from_1[4];
        long _index_to_1[4];
        long _I_1;
        int _max_receiver_0[4];
        int _min_receiver_0[4];
        int _indexR_1;
        int _indexR_2;
        long _index_from_2[4];
        long _index_to_2[4];
        long _I_2;
        int _minInx_receiver_0[4];
        int _maxInx_receiver_0[4];
        int _indexR_3;
        int _indexR_4;
        coinsNumberOfThreads = coinsThreadInit( (int )4);
        n = (int )50;
        k = (int )100;

        sum = (int )0;
        {
            {
                i = (int )0;
            }
            coinsThreadPreprocessForDoAllLoop( coinsNumberOfThreads,(long )(n),((_index_from_0)),((_index_to_0)));
            {
                _x_global_0 = ((x));
                _k_global_0 = k;
            }
            for ( _I_0 = (int )0;(_I_0) < (((coinsNumberOfThreads) - ((int )1))); _I_0 = ((_I_0) + ((int )1)))
            {
                coinsThreadForkForDoAll( (&(coinsThread[_I_0])),main_loop_0,coinsThreadIdArray[_I_0],_index_from_0[_I_0],_index_to_0[_I_0],(&(_sum_receiver_0[_I_0])),(int )0);
            }
            _lab33:;
    #pragma omp parallel for lastprivate(i,k) reduction(+:sum)

            for ( i = _index_from_0[((coinsNumberOfThreads) - ((int )1))];(i) < (_index_to_0[((coinsNumberOfThreads) - ((int )1))]); i = ((i) + ((int )1)))
            {
                k = ((((int )-2) * (i)) + ((int )100));
                x[i] = ((k) + (i));
                c[i] = (i) * (i);
                sum = ((sum) + (x[i]));
    _lab37:;
            }
            _lab41:;
            coinsThreadPostprocess( coinsNumberOfThreads,n);
            for ( _indexR_0 = (int )0;(_indexR_0) < (((coinsNumberOfThreads) - ((int )1))); _indexR_0 = ((_indexR_0) + ((int )1)))
            {
                sum = ((sum) + (_sum_receiver_0[_indexR_0]));
            }
            _lab55:;
        }
        k = ((((int )-2) * (i)) + ((int )100));
        (&(printf))( (("k = %d sum = %d \n"k,sum);

        max = x[(int )0];
        min = x[(int )0];
        {
            {
                i = (int )1;
            }
            coinsThreadPreprocessForDoAllLoop( coinsNumberOfThreads,(long )(n),((_index_from_1)),((_index_to_1)));
            {
                _n_global_0 = n;
                _x_global_1 = ((x));
                _max_global_0 = max;
                _min_global_0 = min;
            }
            for ( _I_1 = (int )0;(_I_1) < (((coinsNumberOfThreads) - ((int )1))); _I_1 = ((_I_1) + ((int )1)))
            {
                coinsThreadForkForDoAll( (&(coinsThread[_I_1])),main_loop_1,coinsThreadIdArray[_I_1],_index_from_1[_I_1],_index_to_1[_I_1],(&(_max_receiver_0[_I_1])),(&(_min_receiver_0[_I_1])));
            }
            _lab59:;

            for ( i = _index_from_1[((coinsNumberOfThreads) - ((int )1))];(i) < (_index_to_1[((coinsNumberOfThreads) - ((int )1))]); i = ((i) + ((int )1)))
            {
                if ((x[i]) > (max))
                {
    _lab63:;
                    {
                        max = x[i];
                    }
                }
                if ((x[i]) < (min))
                {
    _lab66:;
                    {
                        min = x[i];
                    }
                }
    _lab69:;
            }
            _lab73:;
            coinsThreadPostprocess( coinsNumberOfThreads,n);
            for ( _indexR_1 = (int )0;(_indexR_1) < (((coinsNumberOfThreads) - ((int )1))); _indexR_1 = ((_indexR_1) + ((int )1)))
            {
                if ((_max_receiver_0[_indexR_1]) > (max))
                {
                    max = _max_receiver_0[_indexR_1];
                }
            }
            _lab96:;
            for ( _indexR_2 = (int )0;(_indexR_2) < (((coinsNumberOfThreads) - ((int )1))); _indexR_2 = ((_indexR_2) + ((int )1)))
            {
                if ((_min_receiver_0[_indexR_2]) < (min))
                {
                    min = _min_receiver_0[_indexR_2];
                }
            }
            _lab103:;
        }
        (&(printf))( (("max = %d min = %d \n"max,min);
        maxInx = (int )2;
        minInx = (int )2;
        max = x[(int )2];
        min = x[(int )2];

        {
            {
                i = (int )0;
            }
            coinsThreadPreprocessForDoAllLoop( coinsNumberOfThreads,(long )(n),((_index_from_2)),((_index_to_2)));
            {
                _n_global_1 = n;
                _x_global_2 = ((x));
                _max_global_1 = max;
                _min_global_1 = min;
                _minInx_global_0 = minInx;
                _maxInx_global_0 = maxInx;
            }
            for ( _I_2 = (int )0;(_I_2) < (((coinsNumberOfThreads) - ((int )1))); _I_2 = ((_I_2) + ((int )1)))
            {
                coinsThreadForkForDoAll( (&(coinsThread[_I_2])),main_loop_2,coinsThreadIdArray[_I_2],_index_from_2[_I_2],_index_to_2[_I_2],(&(_minInx_receiver_0[_I_2])),(&(_maxInx_receiver_0[_I_2])));
            }
            _lab107:;

            for ( i = _index_from_2[((coinsNumberOfThreads) - ((int )1))];(i) < (_index_to_2[((coinsNumberOfThreads) - ((int )1))]); i = ((i) + ((int )1)))
            {
                if ((x[i]) > (max))
                {
    _lab111:;
                    {
                        max = x[i];
                        maxInx = i;
                    }
                }
                if ((x[i]) < (min))
                {
    _lab114:;
                    {
                        min = x[i];
                        minInx = i;
                    }
                }
    _lab117:;
            }
            _lab121:;
            coinsThreadPostprocess( coinsNumberOfThreads,n);
            for ( _indexR_3 = (int )0;(_indexR_3) < (((coinsNumberOfThreads) - ((int )1))); _indexR_3 = ((_indexR_3) + ((int )1)))
            {
                if ((x[_minInx_receiver_0[_indexR_3]]) < (x[minInx]))
                {
                    minInx = _minInx_receiver_0[_indexR_3];
                }
            }
            _lab144:;
            for ( _indexR_4 = (int )0;(_indexR_4) < (((coinsNumberOfThreads) - ((int )1))); _indexR_4 = ((_indexR_4) + ((int )1)))
            {
                if ((x[_maxInx_receiver_0[_indexR_4]]) > (x[maxInx]))
                {
                    maxInx = _maxInx_receiver_0[_indexR_4];
                }
            }
            _lab151:;
        }
        sum = c[(int )0];
        for ( i = (int )1;(i) < (n); i = ((i) + ((int )1)))
        {
            sum = ((sum) + (c[i]));
        }
        _lab28:;
        (&(printf))( (("maxInx = %d minInx = %d sum = %d\n"maxInx,minInx,sum);

        coinsThreadEnd();
        return (int )0;
    }
    void * main_loop_0( int _threadId_0,long _indexFrom_0,long _indexTo_0,int * sum_0,void * _voidPtr_0 )
    {
        int i;
        int n;
        int k_0;
        int sum;
        coinsThreadPreprocessForDoAllThread();
        sum = (int )0;
        k_0 = _k_global_0;
        {
            i = (int )0;
        }
        for ( i = _indexFrom_0;(i) < (_indexTo_0); i = ((i) + ((int )1)))
        {
            k_0 = ((((int )-2) * (i)) + ((int )100));
            (_x_global_0)[i] = ((k_0) + (i));
            c[i] = (i) * (i);
            sum = ((sum) + ((_x_global_0)[i]));
    _lab45:;
        }
        _lab49:;
        (*(sum_0)) = sum;
        coinsThreadPostprocessForDoAllThread();
    }
    void * main_loop_1( int _threadId_0,long _indexFrom_0,long _indexTo_0,int * max_0,int * min_0 )
    {
        int i;
        int max;
        int min;
        coinsThreadPreprocessForDoAllThread();
        max = (int )0;
        min = (int )0;
        max = _max_global_0;
        min = _min_global_0;
        {
            i = (int )1;
        }
        for ( i = _indexFrom_0;(i) < (_indexTo_0); i = ((i) + ((int )1)))
        {
            if (((_x_global_1)[i]) > (max))
            {
    _lab77:;
                {
                    max = (_x_global_1)[i];
                }
            }
            if (((_x_global_1)[i]) < (min))
            {
    _lab80:;
                {
                    min = (_x_global_1)[i];
                }
            }
    _lab83:;
        }
        _lab87:;
        (*(max_0)) = max;
        (*(min_0)) = min;
        coinsThreadPostprocessForDoAllThread();
    }
    void * main_loop_2( int _threadId_0,long _indexFrom_0,long _indexTo_0,int * minInx_0,int * maxInx_0 )
    {
        int i;
        int maxInx;
        int minInx;
        coinsThreadPreprocessForDoAllThread();
        minInx = _indexFrom_0;
        maxInx = _indexFrom_0;
        {
            i = (int )0;
        }
        for ( i = _indexFrom_0;(i) < (_indexTo_0); i = ((i) + ((int )1)))
        {
            if (((_x_global_2)[i]) > (_max_global_1))
            {
    _lab125:;
                {
                    _max_global_1 = (_x_global_2)[i];
                    maxInx = i;
                }
            }
            if (((_x_global_2)[i]) < (_min_global_1))
            {
    _lab128:;
                {
                    _min_global_1 = (_x_global_2)[i];
                    minInx = i;
                }
            }
    _lab131:;
        }
        _lab135:;
        (*(minInx_0)) = minInx;
        (*(maxInx_0)) = maxInx;
        coinsThreadPostprocessForDoAllThread();
    }