概観

我々の処理系の中心部分は, ABCL/f をそれに対応するC++コードに変換するト ランスレータである. ABCL/f の一つの手続き(defunないし defmethodで定義されたもの)は, C++の一つの関数に変換される. その 中では, 逐次実行の部分は, ほぼそのまま対応するC++のコードに変換される.

すると, 並列計算機上で動作するABCL/f を実装するに当たって, 大きな問題 は,

1. 細粒度マルティスレッディング
2. 大域ゴミ集め(Global GC)

の2点である. マルティスレッディングは, futureプリミティブを効率良く支 援するために必要で, 特に, 粒度の小さいスレッドを, 1プロセッサ内に多数 (たとえば, > 100. 時にはこれよりずっと多いこともあり得る)生成しても, それらが効率に影響を与えず, feasibleなプログラミングスタイルとして支援 されている必要がある. Global GCは, いうまでもなく, もはや他のプロセッ サから参照されていないオブジェクトを見つけて回収する機能で, 並列計算機 上で動作する言語処理系には欠かせない機能である.

もちろんABCL/f を実装するに当たって解決すべき点は, 上記二つだけではな いが, 上記二つの機能はどちらも, 「ありあわせの」libraryや, 良く知られ た実装技術の組合せでは達成不可能であるという点で, ABCL/f という処理系 の完成に当たって特に重要な課題であった. 今回の我々の研究ではこれらのど ちらの問題に対しても, ユニークでかつ, 実践的な解答を生み出し, かつその 有効性を, いくつもの応用実証によって検証することができた.

まず, 1.のマルチスレッディングに関して, 我々は, 一回のローカルなfuture 呼び出しにかかるオーバーヘッドをほとんど通常の関数呼び出し+数命令程 度にする実行方式を開発した Taura97FineGrain. 我々の方式の特に特 徴的な点は, 逐次部分の実行に関しては, ほぼそのままC++のコードに翻訳し, 結果としてC++と同等の効率を得ているにも関わらず, futureの実行に関して も上記のような高効率を達成している点である. これまでの多くの並列言語の 実装は,

• 逐次実行を効率良くするためにスレッド生成の効率を犠牲にして, プロ グラミングスタイルを制限していたか,
• または細粒度マルチスレッディングの効率を得るために, コンパイラを 1から設計し, その結果, 逐次の効率が既存の最適化Cコンパイラのそれに比べ て, しばしば落ちる

のどちらかに当てはまるものがほとんどであった. ABCL/f は既存 の逐次Cコンパイラのcalling convention上でC手続きのactivation frameから 必要な情報を得ることによって, 通常のC手続きの途中で実行を止めたり, そ れを後から別の場所で再開させたりする機能を実現することによって, スレッ ドの機能を実現している. これによってコード生成器は単純な逐次のコードを 生成しつつ, 実行時システムが各々のC手続き呼び出しを「スレッド生成つき 関数呼び出し」に転化させることができる. これにより高効率なスレッド生成 と, (単純なコード生成で, 逐次のCコンパイラによってなされる最適化を最大 限活用利用することによる)高い逐次の効率を達成しているのである. またこ の実行メカニズムはABCL/f とは独立であり, C++を直接コード生成器のtarget にするマルチスレッド言語処理系に組み合わせることができる.

次に2.のglobal GCに関して, 我々の方式は概念的には極めて単純だが, これ までほとんど実装され, 評価されたことのなかった, 大域マーキング方 式に基づくGCである. 大域マーキング方式は単純に, システム全体に渡るオ ブジェクトの参照関係がつくり出すグラフを, ルートから--ローカル参照, リモート参照に関わらず--たどっていき, たどれるものだけを生きているオ ブジェクトと見なし, 残りはゴミとみなす方式である. 特に1プロセッサ上の 言語実装ではほとんどこの方式が使われている. しかし分散メモリ計算機では, 実装上困難な点が多く, あまり実装されていない. そして, 特に並列計算機上 で実装され, 評価までされた例はほとんど存在しない. 以下は想像の域を出な い推論だが, 理由を考えてみると,

• 同期した時計を仮定できない分散記憶計算機においては, consistentな global snapshotの元でマーキングを行なわねば, 正しいゴミ集めが行なわれ ないため, タイミングによるバグなどが生じやすく, 正しい実装が複雑になる こと.
• 通信のコストが高い分散記憶計算機においては, 遠隔参照をメッセージ によってtranverseするコストが高いと信じられてきたこと.
• 同期のコストが高い大規模計算機においては, そのコストを隠すために, concurrent GC (ユーザプログラムと並行に動作するGC)が必要で, そのような マーキングGCを実装するのは複雑であること.

などがあげられる. 以上のようなことから, 分散記憶計算機ではしばしば参照 カウント方式が用いられてきた. これは特に, 「並列」言語処理系ではなく, 同期や通信のコストが並列計算機に比べて圧倒的に大きい「分散」言語処理系 で, 用いられてきたが [7], 一部の並列計算機用の処理系でも用いられている [24], [39]. 今回の我々の実装では, GC 戦略として独立local GC, 同期local GC, global GCの3種類を用意し, 大域マー キング方式を効率良く実装することに成功した [46]. この研究は参照カウント方式と大域マーキング のどちらが優れているかについて, 結論を下すものではないが, 少なくとも大 域マーキングが一般に信じられているよりも効率がずっと良く, 参照カウント に比べて優れた点をいくつか持っていることを示している. それらについては, 3.3節で詳しく論じている.

本節の以下の節, 3.2節 および 3.3節 では, マルチスレッディングおよびGCそれぞれについて詳しく説明している.