マルチスレッデイングとは,ひとつのプロセッサ中で多数のスレッド(実行流)を管理する機能であり,これによって並列計算機上で,プログラマはプロセッサ台数よりも多くのスレッドを持てるようになる.マルチスレッディングの実行方式は,従来から非常に多くの文脈で研究されており,我々の実行方式そのものは,本質的には,遅延タスク生成(Lazy Task Creation,以下LTC)という,並列Lispを対象にして研究された方式と同一のものである.

　マルチスレッディングの分野における本論文の貢献は二つある.まずLTCは,比較的小さな,ほとんど副作用のない応用問題で評価されており,また,共有記憶計算機上でしか実装されていない.これに対し我々は,より大規模で複雑なオブジェクト指向の応用問題を記述し,その性能を分散記憶計算機上で測定した.マルチスレッディングの性能を測定する設定としては,LTCが評価された「副作用のほとんどないプログラム,およびハードウェアによる共有ヒープを持つ計算機」という設定と,我々の「副作用があるプログラム,および分散記憶計算機」という設定では大きく異なっている.LTCの設定の元では明らかにスレッド切り替えの頻度は十分小さくなり,結果としてそのコストが問題になることはあまりない.一方我々の設定では,プログラムはロック獲得失敗時および,遠隔データアクセス時にしばしばブロックするため,その性能は実験によって確かめる必要があった.次に,これまでのマルチスレッディングのための実行時方式は,実際には,その方式専用のコード生成器(コンパイラ)との密な連携を前提にしており,これに対して我々の方式は,既存のCコンパイラをコード生成器としてそのまま用いることができるという点があげられる.これまでの方式は原理的には他の言語に通用する部分を多く持つにもかかわらず,実際には他の言語の実装者と直ちに共有できる技術ではないし,また,Cコンパイラの優れた逐次性能を利用できるものでもなかった.そして,LTCのような方式を,現在の逐次の呼び出し慣例や,それを前提にした逐次言語のコンパイラや支援ツールをそのまま再利用可能な形で効率的に実装できるかどうかは,明らかとは言えなかった.我々の方式は,Cのスタックフレーム上にある情報を最大限に活用し,SparcおよびAlphaという二つの異なったプラットフォーム上で,Cコンパイラを変更することなく実装されている.

　この方式は以下のように動作する.まず,スレッド生成は,単にCの関数呼び出しをすることによって行う.そして,そのスレッドがブロックした時は,その関数のスタックフレームをヒープにコピーした上で,その関数の親(呼び出した関数)に制御を移す.そのスレッドが計算を再開できる状態になったら,保存してあったフレームをスタックに書き戻して,その関数の途中から実行を再開する.一般に,スタックフレームは,ブロックした時とは違うアドレスに書き戻されるため,現在のところ,スタックフレームには,構造体および配列は割り当てられないものと仮定している.ここでCのスタックフレームについて,それをコピーしたり,正しいレジスタの状態で親に復帰するために,いくつかの問題が生ずる.

　特に,これまでの多くのマルチスレッディングの実装では,単純のためにスレッド生成時には呼び出し側がすべての必要なレジスタを待避する,つまりcallee-saveレジスタは存在しないものとしていた.これによって,スレッドのブロック時には,単に次のスレッドのフレームポインタおよびスタックだけを設定すれば正しい処理が継続できる.一方,Cの関数呼びだしをスレッド生成とみなす我々の方式では,それは仮定できない.従ってあるスレッドがブロックした時に,そのスレッドが使用中のcallee-saveレジスタは,親が期待する値に復帰させねばならない.しかしCの関数がどのcallee-saveレジスタを使用しているかを実行時に簡単に判定する方法はなく,あったとしてもオーバーヘッドが大きいものになる.

　この問題に関して,以下のような,簡潔で効率の良い解決法を考案した.我々の知る限りすべてのCコンパイラは,ある関数が使用するcallee-saveレジスタの保存・復帰を関数の入口と出口で全て一度に行う.従って,ある関数のどこからでも,その出口にある,callee-saveレジスタを復帰するコード(終了処理コード)に直接ジャンプすれば,その関数が呼び出された直後のレジスタの状態を正しく再現できる.そこでブロックを実現する関数は,まず自分の戻り番地を,それを呼び出した関数の終了処理コードの番地に書き換える.同様のことを実際にブロックしたスレッドにたどり着くまで行い,最終的にその親,つまりスレッドを呼び出した関数に復帰する.さらなる詳細および一般化を本文で述べている.

　マルチスレッディング同様,GCもこれまで非常に様々な文脈で研究されてきた.分散記憶環境での研究に限っても非常に多くのアルゴリズムが提案されている.我々の方式は,数々の分散環境における複雑な問題(信頼できない通信路や,故障しているプロセスなど)を扱った他の多くのアルゴリズムと比べると,方式自体は最も単純な部類に属する.我々のこの分野に対する貢献は,性能を向上するためのいくつかの単純な技法と,実際的な応用問題を用いた実験による定量的な性能評価である.

　我々のGCの方式はmark & sweep方式と呼ばれるもので,大域GC時には全プロセッサが協力しながら,ルートからたどれるオブジェクトに印をつけていく.この時,遠隔オブジェクトへのポインタは,そのオブジェクトが存在するプロセッサにメッセージを送ることでたどっていく.

　単純な実装で問題になるのは,この,遠隔ポインタをたどるためのメッセージ送受信オーバーヘッドである.最も単純な実装は,遠隔ポインタを一つ見つけるたびにひとつメッセージを送信するというものであるが,これでは実用的な速度は得られない.なるべくたくさんの遠隔ポインタを一つのメッセージでたどることが重要で,そのために我々は以下のようにした.各プロセッサはプロセッサ内のポインタだけでたどれるものだけを最大限たどり,これ以上何もたどれなくなった時に初めて,これまでプロセッサ内でたどっている最中に見つけた遠隔ポインタ全てに対してメッセージを送る.この時,複数の遠隔ポインタを一つのメッセージとして送ることができる.またこれと同様に,メッセージを受け取った方も,一つメッセージを受け取るたびにそこからプロセッサ内でたどれるものを見つけに行くのではなく,複数のメッセージをためて一括して処理を行うようにする.以上のような簡単な工夫を行うことで,メッセージ送受信のコストは大幅に削減され,mark&sweep方式は実用的な速度を示すようになる.

　応用問題を用いて実験を行った結果,我々の並列GCのオーバーヘッドが,同じプログラムを1プロセッサで実行した時と大きく違わないことが,最大256台のプロセッサを用いた実験によって確かめられた.また,r＝2のときにGCがアプリケーションの実行時間に占める割合は,高々15%程度であった.ここでアプリケーションの実行時間には,アイドル時間は含まれていない.

　また,この実験により,局所的なGCは多くの場合,すべてのプロセッサで一斉に行わなければならないという結果が得られている.これは,各プロセッサが独立にGCを行うと,各プロセッサが,不揃いなタイミングで,他のプロセッサからのメッセージに反応しない時間帯を作り出すためである.そのようなGCのスケジューリングの元では,頻繁に同期通信を行う応用問題の性能は極端に悪くなる.一方,同期通信をあまり行わなず,1プロセッサ内部にたくさんの並列性を持つ応用問題ではこのようなことは起こらないし,実際独立にGCを行う方が(我々の実験ではわずかであったが)性能がよくなることもある.そこでさらに,局所GCを一斉に行うかどうかを実行時に適応的に決める方式を開発した,我々のこれまでの実験結果ではこの適応的な局所GCの選択方式は,明らかにどちらかが一方に比べて優れている時は,きちんとその優れている方を選択していることを確認した.

　マルチスレッディングと,GCという二つの機構の上にプログラミング言語ABCL/fを設計・構築し,さらにその応用問題によって性能を評価した.ABCL/fはC++への変換という形で実装されており,そこでは上に述べたマルチスレッデイングの機能を活用して,ABCL/fの動的に並列性を作り出す機能の効率と,逐次計算部分の速度との両立を達成している.