7.2.1 CoCoの概要
CoCoはSMP型並列計算機を対象計算機として、COINSの高水準中間表現HIR (High-level Intermediate Representation)上で、逐次プログラム表現から並列プログラム表現に自動的に変換する(図7.2-1の網掛け部分)。並列化されたHIRにはOpenMP指示文が付加されており、HIR to C変換系によりCプログラムに逆変換される。
粗粒度並列化コンパイラCoCoは、有効性評価で示すように、現状では必ずしも十分な粗粒度タスク水準の並列性を引き出しているとは言い難い。さらなる性能向上と機能強化に向けての課題は、当面、以下の通りである。
- 階層サブルーチンの粗粒度並列化
- Do-allループの適切な並列粒度分割
- 適切なスレッド割当てアルゴリズム

図7.2-1 CoCoの位置づけ
7.2.2 CoCoの使い方
CoCoは、粗粒度並列化モジュールmdf (Macro Data Flow Module)として実装されている。mdfは、
入力された逐次のCプログラムに対して、COINSの高水準中間表現HIR上でSMP型並列計算機向け
粗粒度並列化を行う。 並列化されたHIRはバックエンドを利用せずに、HIR to Cトランスレータを利用
して並列実行可能なCプログラムに逆変換する。
以下は、mdfモジュールの使用にあたっての前提条件である。
- HIR上でのSMP 向け粗粒度並列化を行う。
- モジュール名はmdf、パッケージはcoins/mdfである。
- COINSコンパイラドライバに対して、-coins:coarseGrainParallel(または cgParallel)
というオプションで起動する。
- mdf はHIR to C を用いてC プログラムに逆変換する。
- 出力ファイルは、xxx.c に対してxxx-cgparallel.c である。
この出力ファイルを以下のようにしてOmni-OpenMPコンパイラに与えれば良い。
omcc xxx-cgparallel.c
詳しくは英語のドキュメントの
6. Parallelization for HIR
を参照されたい。
7.2.3 CoCoの設計方針と制約事項
粗粒度並列化モジュールmdfは、HIR 上でプログラムを粗粒度タスクに分割する。各タスクは、
基本ブロック、ループ、サブルーチンなどである。分割された粗粒度タスク間の制御フロー情報
とデータ依存関係を粗粒度タスクフローグラフ(マクロフローグラフ)として保持し、そのグラフから
各タスクの実行開始条件を求める。
ここで、実行開始条件とは、「プログラム実行中に、どのような条件が揃えばそのタスクを実行
してよいか」ということを、タスクごとに論理式で表現したものである。
また、プログラム中のすべての粗粒度タスクが実行されるとは限らないので、プログラム実行時
に動的にタスクを割り当てる動的スケジューラが必要である。
本モジュールによって変換されたHIRは、並列実行制御のための並列プログラミングインタフェース
OpenMPの指示文が挿入される。
以下は、CoCoの設計方針である。
- 並列化コンパイラ開発基盤としてCOINSを利用する。
- HIR水準で基本ブロック情報をもとに、Cプログラムを粗粒度タスクに分割する。
- 並列性抽出には、タスク間の実行開始条件を用いる。
- 実行可能タスクは、動的スケジューラによって各プロセッサに割り当てられる。
- 並列実行のために、プログラムの構造をswitch-case文に変換する。
- タスクプライベートに使用される変数は、プロセッサプライベートな変数とする。
- 並列プログラムの可搬性を考慮し、OpenMPの指示文を利用する。
- OpenMP指示文をコメントとして含むHIRをCプログラムに逆変換する。
- Cプログラムへの変換過程で、動的スケジューリングルーチンを付加する。
- 生成されたCプログラムを、OpenMPコンパイラを介して並列実行する。
現在の制約事項は、以下の通りである。
- プログラム中のループは1つのマクロタスクとする。
- HIRの予約語以外のループは認識していない(goto文で作られているループなど)。
- exit関数でプログラムが終了する際に、プログラムの出口を認識できていない。
- 依存関係のないタスクは、プログラマが意図した通りの順序では実行されない。
7.2.4 CoCoの処理の流れ
CoCoの処理の流れを図7.2-2に示す。

図7.2-2 CoCoの処理の流れ
7.2.4.1 並列実行プログラムへの変換
CoCoは、HIR レベルでプログラムの構造を解析し並列性を抽出したあと、プログラムの構造を
変換してC言語に逆変換する。
プログラムの構造は、入力された逐次のものから、1つの粗粒度タスクと1つのcase文が対応するようなC言語の
switch-case文に変換する。
また、CoCoでは、プログラムの並列実行の方法としてOpenMPを利用した。OpenMPとは、
プログラム並列化指示文を統一するための規格である。OpenMPの指示文は、CやFortran
といったプログラミング言語のプラグマとして定義されている。
7.2.4.2 OpenMP指示文の挿入
switch-case文への構造変換によって、入力された逐次プログラムは粗粒度タスク単位で実行される
プログラムに変換される。
ここでは、プログラムを並列に実行するためのOpenMP指示文の挿入について述べる。
OpenMPには、ループの並列実行を指示する #pragma omp forや、ブロック単位での並列実行を
行う #pramga omp section 等が定義されている。しかし、CoCoではあらかじめプログラムを
粗粒度タスクに分割しており、さらにスケジューリング処理も規定している。そこで、並列化のために
挿入するOpenMP指示文は #pragma omp parallelのみとした。
#pragma omp parallel指示文は、 あらかじめ環境変数等で指定された数のスレッドを作成し、
プログラムをスレッドの数だけ並列に実行するという指示文である。この指示文を、プログラム全体
を覆うループの外側に挿入することにより、粗粒度タスクの並列処理を実現する。
プログラムが並列に実行されることにより、スケジューラデータへの排他アクセスが必要となる。
そこでOpenMPのライブラリ関数を用いてロック・アンロックを実現する。この関数をスケジューラへの
アクセス操作の前後に挿入することにより、スケジューラデータへの排他アクセスが可能になる。
なお、OpenMP指示文そのものはプラグマであるので、そのプラグマを解釈できないコンパイラは
単にコメント文と認識するが、ライブラリ関数の利用はリンカでのエラーの原因となり得る。そこで、
ライブラリ関数使用の前後に #ifdef を挿入することにより、OpenMPコンパイラ以外のコンパイラ
でもコンパイルできるように配慮した。
7.2.4.3 粗粒度タスクスケジューラ
粗粒度タスク水準のマクロフローグラフで表された全ての粗粒度タスクが、実行可能とは限らない。
プログラムの実行時に各タスクの実行開始条件の評価を行い、実行可能なタスクを動的にプロセッサ
に割り当てるスケジューラが必要となる。
タスクを動的にスケジューリングするためには、プログラム実行時にスケジューラに対して開始条件の
変更を伝えなければならない。例えば、あるタスクが終了した際には、その条件分岐先のタスクおよび
非実行が確定するタスクをスケジューラに伝える必要がある。
スケジューラは、伝えられた変更を各タスクの実行開始条件に反映する。同変更を反映した結果、
実行開始条件が真となったタスクは、実行可能タスクとしてプロセッサに割り当てる。実行可能タスク
はキューに入れられ、各プロセッサはキューの先頭から次に実行するタスクを獲得し、実行する。
7.2.5 CoCoの評価
以下に示すSMP型並列計算機環境において、SPEC95ベンチマークプログラムのswim および
tomcatvを用いてCoCoの性能評価を行った。
OS Solaris 8
プロセッサ Sun UltraSPARC2(450MHz)x 4、メモリ1GB
Javaコンパイラ JDK 1.4.2
Cコンパイラ gcc 2.95.3
OpenMP Omni OpenMP Compiler 1.4
プロセッサ並列実行時において逐次実行時に比べて、swimについては約1.9 倍、tomcatvについては
約1.7 倍の速度向上が得られた。