並列言語 WTC(Work-Time C)の言語仕様

Work-Timeモデルをサポートした拡張C言語である. Work-Time Cは, 並列再帰や並列に動作するサブルーチンの並列呼び出し ,パイプライン処理などを行なう複雑なPRAMアルゴリズムを論理的に簡潔に 記述できることを目標として設計された. またC言語に対する拡張は必要最小限にとどめた. 追加された予約語はpar, to, do, nonatomic, EREW, CREW, common, arbitrary, priorityの9つである.

共有変数
par文
atomic関数とnoatomic 関数
並列再起の記述
パイプラインアルゴ リズムの記述
平行アクセス のモデル
参考文献

共有変数
Work-Time Cでは,すべての変数は共有メモリ上に確保される. C言語でいうと ころの局所変数は, Work-Time Cではスコープがその変数が宣言されたブロッ クに局所的な共有メモリ上の変数である(Work-Timeモデルにはプロセッサとい う概念は現れない). そのため局所変数もpar文の本体中の文から並列アクセ スできる. 例えば,このプログラム の関数prefixsumの局所配列変数yは,そのスコープ内にある6行目のpar文 で並列にアクセスされている.

par文
1時間単位での複数命令の並列実行を指定するには, par文を用いる. 例えば, 再帰によるO(n)work, O(\log n)timeのprefix sum[3]の 記述例はこのプログラムのよう になる. 図 このプログラムの6 行目のpar文は, iが0からn/2-1の各々についてy[i] = x[2 * i] + x[2 * i + 1];という文を並列実行するという意味である.ただし代入文の評価は,1.式中 の各変数の値の読み出し, 2.式の評価, 3.代入,の順に同期して行なう.これは a[i] = a[i * 2] + a[i * 2 + 1];のように右辺の式に左辺と同じ変数が現れ る場合があるからである. またpar文のインデックス変数このプログラム6行目の変数i)は,特 殊な記憶クラスを持ち,宣言せずに使うことができるconst int型の変数である. par文のサブ文にはブロックの指定も可能である. さらにブロックの先頭での 局所変数の宣言も可能である.この場合,局所変数の実体は,インデックス変数 の値の数だけ存在する.ある実体にアクセスできるのは,対応するインデックス 変数の値が同じ文からだけである.

並列度mのpar文と並列度nのpar文がネストすると並列度がmnとなる(関数呼び 出しによる暗黙のネストの場合も 含む). このようなデータ並列性を入れ子状データ並列[1]という. Work-Time Cでは入れ子状データ並列を基本としている. このため Work-Time Cでは,より基本的な並列アルゴリズムをサブルーチンとして並列に 呼び出すことにより,より複雑な並列アルゴリズムを記述できる. 例えば,行 列の乗算を記述するのに,配列の値の総和を求める並列アルゴリズムをサブルー チンとして用いることができる. さらに分割コンパイルが可能であるので,並 列アルゴリズムの汎用的なライブラリを構築することが可能である.

atomic関数とnoatomic 関数
このプログラムの関数prefixsum のように, nonatomicという修飾子がついている関数をnonatomic関数と呼ぶ. nonatomic修飾子がついていない関数をatomic関数と呼ぶ(atomicという予約語 はない). atomic関数は,パイプライン処理の記述と逐次Cの既存コード(ソー ス,バイナリとも)の利用に用いる. nonatomic関数では,並列実行される nonatomic関数間で関数内の各文を,同期をとりながら実行する.これに対して atomic関数は,それが1つの基本命令であるかのように実行されるので,関数内 の各文の実行は並列実行されるatomic関数間で同期を取らずに実行される. とくにnonatomic関数中のif文の実行は,1.条件式の評価, 2.then節の実行, 3.else節の実行, がこの順に同期して行なわれるが, atomic関数中では非同期 に実行される. これはswitch文についても同様である.
printf関数などのANSI C標準関数や,Xlibなどの逐次Cライブラリの関数は atomic関数である. atomic関数の意味は逐次Cの関数の意味と同じなので,逐 次Cのコードはソース,バイナリともWork-Time Cでそのまま利用できる. nonatomic, atomic関 数ともにユーザー定義可能である.

並列再起の記述
次に並列再帰の記述例を示す.このプ ログラムは,並列再帰によるquick sortの記述例である.このプログラムでは2回の再帰呼び出 しをpar文を用いて並列実行することを指定している. このプログラムのpartition関数は, 適当なpivotを選択して,配列xの左側にpivotより小さい値を集め,右側にpivot より大きい値を集めて, pivotの（うちの１つの）添字を返す関数である. partition関数内の配列の値の移動に このプログラムのprefixsum関数をサブルーチンとして用いると平均O(n log n)work, O(log2n)timeのquick sortとなる. このように Work-Time Cでは,並列再帰を用いたり,より基本的な並列アルゴリズムをサブ ルーチンとして用いて,より複雑な並列アルゴリズムを記述できる.

パイプラインアルゴリズムの記述
次にパイプラインアルゴリズムの記述例を示す. このプログラムのように, Work-Time Cではatomic関数を par文で並列実行することにより,パイプライン処理を記述できる. 同様にし てO(n log n)work,O(log n)timeのpipeline merge [2]などの複雑なパイプラインアルゴリズムも記述で きる.

平行アクセス のモデル
関数の修飾子としてEREW, CREW, common, arbitrary, priorityが指定できる. 例えばEREWを指定した関数内の文の実行でConcurrent Read/Writeが起きると 実行時エラーを検出する. arbitraryの場合は,Concurrent Writeはarbitrary として処理される. デフォルトはCREWである.

参考文献

萩原研究室ホームページに戻る
萩原研の研究内容のページへ戻る