7.2.1 CoCoの概要

CoCoはSMP型並列計算機を対象計算機として、COINSの高水準中間表現HIR (High-level Intermediate Representation)上で、逐次プログラム表現から並列プログラム表現に自動的に変換する(図7.2-1の網掛け部分)。並列化されたHIRにはOpenMP指示文が付加されており、HIR to C変換系によりCプログラムに逆変換される。
粗粒度並列化コンパイラCoCoは、有効性評価で示すように、現状では必ずしも十分な粗粒度タスク水準の並列性を引き出しているとは言い難い。さらなる性能向上と機能強化に向けての課題は、当面、以下の通りである。
fig7.2.1.jpg
図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モジュールの使用にあたっての前提条件である。

この出力ファイルを以下のようにしてOmni-OpenMPコンパイラに与えれば良い。

  omcc xxx-cgparallel.c
詳しくは英語のドキュメントの 6. Parallelization for HIR を参照されたい。

7.2.3 CoCoの設計方針と制約事項

粗粒度並列化モジュールmdfは、HIR 上でプログラムを粗粒度タスクに分割する。各タスクは、 基本ブロック、ループ、サブルーチンなどである。分割された粗粒度タスク間の制御フロー情報 とデータ依存関係を粗粒度タスクフローグラフ(マクロフローグラフ)として保持し、そのグラフから 各タスクの実行開始条件を求める。
ここで、実行開始条件とは、「プログラム実行中に、どのような条件が揃えばそのタスクを実行 してよいか」ということを、タスクごとに論理式で表現したものである。
また、プログラム中のすべての粗粒度タスクが実行されるとは限らないので、プログラム実行時 に動的にタスクを割り当てる動的スケジューラが必要である。
本モジュールによって変換されたHIRは、並列実行制御のための並列プログラミングインタフェース OpenMPの指示文が挿入される。
以下は、CoCoの設計方針である。 現在の制約事項は、以下の通りである。

7.2.4 CoCoの処理の流れ

 CoCoの処理の流れを図7.2-2に示す。
fig7.2.2.jpg
図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 倍の速度向上が得られた。