多くの並列言語は動的なスレッド生成をサポートしている. 言語コンストラク トの例としては, future [21], [50], 並列オブジェクト間非同期メッセージ送受信 [2], [12], [52], fork-join [34] 並列ブロックとループ [11], [13], 非明示的並列 [4], [33] を含む. 動的なスレッド生 成を伴う並列言語(以後マルチスレッド言語と呼ぶ)の実装は, 良い逐次性能を 犠牲にすることなしに, 効率的なマルチスレッドを実現できなくてはならない.
マルチスレッド言語をCにコンパイルし, Cコンパイラによって行なわれる最適 化を利用することは, 逐次の性能を得るために魅力的な選択である. しかし, マルチスレッド言語の実行モデルはCの単スレッド実行モデルに直接対応しな いため, それは簡単にはいかない. 各スレッドに別のスタックを確保するための時 間および空間のオーバヘッドは非常に大きく, 現存するユーザレベルスレッド ライブラリ [15], [30] はマルチスレッド言語を実装するために直接使用することはできない. 結果として, これまで に発表されてきたほとんどのマルチスレッド言語の効率的な実装は, 自前のフ レーム管理を採用しており, フレーム管理およびコンテキストスイッチのため のコード列が埋め込まれたアセンブリもしくはアセンブリライクなCコードを 生成する. そのような実装においては, 典型的には, スレッド生成は一般の自 由記憶から一つのフレームを確保するだけであり, コンテキストスイッチは生 きているレジスタをフレームにセーブして再開するスレッドに制御を移すだけ である [16], [51]. このアプローチは非常に速いスレッド生成とコンテキスト スイッチを達成するが, いくつかの欠点と潜在的な落とし穴ももっている. ま ず, コンパイラを開発するコストが非常に高い. それは, スレッドの実行のた めにランタイムのデータ構造をスクラッチから設計しなければならず, さらに コンパイラが埋め込まれたコンテキストスイッチのコード列を生成するために live-range解析などの低レベルの解析をしなければならないからである. 二つ めに, しっかりした最適化の努力がないと, 逐次の性能が犠牲になってしまう ということである. もっとも特筆すべき影響としては, たとえCコードを生成 するときでも, その高度に複雑で構造化されていない計算の表現のせいで, ア センブリライクなCコードを最適化するのにしばしば失敗するということであ る. 例えば, ループ中での計算の再開はループボディの中へのgoto文を必要と するが, それはバックエンドによる最適化を不可能にさせやすい.
本論文はマルチスレッド言語の高効率な実装に対する魅力的な選択肢を提供す る. その機構はStackThreadsと呼ばれる低レベルCライブラリによって 提供される. 低レベルによって, 我々は, 原始的なフレーム管理機構の みが定義されていることを意味している. 基本プリミティブの上により高レベ ルのアブストラクションをサポートすることは言語設計者と実装者の手に委ね られている. 3.2.5節で, いくつかのアブストラクションの例がStackThreadsの 上に作り上げられることを示す. ライブラリによって, マルチスレッディ ングのための仕事のほとんどが, コード生成器の広範な協力を必要とせず, ラ イブラリのおおいの下で行なわれることを表す. より正確に言えば, 生 成されるコードはスレッドがブロックしたときにただ単にいくつかのライブラ リルーチンを呼ぶだけである. ライブラリルーチンは他のスレッドにスイッチ するのに必要な全ての仕事を行なう. 特に, コンテキストをセーブするコード 列は生成されるCコードの中に埋め込まれる必要はない. よって, StackThreadsでは, 逐次コンストラクトは評価がもはや続けられなくなったと きにライブラリルーチンを呼ぶかも知れない, それに相当するCの文および式 に直接的にコンパイルされる. これは開発コストを低減し, バックエンドの最 適化の機会を高める.
伝統的なスレッドライブラリとは異なり, StackThreadsはマルチスレッド言語 の性能要求--小さい生成オーバヘッド--を満たしている. StackThreadsでは 新しいスレッドを始めることは, パラメータ渡しを含め, 数インストラクショ ンしか要しない. 実際には, C関数 f のボディを実行する新しいスレッドを 始めるのは, 単なる f のプロシージャ呼びだしである(実装されている言語 コンストラクトによっては追加のパラメタがつけられる可能性がある). スレッ ドがブロックするケースでは, (1) Cの手続きのコンテキストを保存し, 手続 きのcallerを再開する(2) 後でセーブされたコンテキストからブロック したスレッドを再開する, ために機構が提供される. これらの機構や似たよう な機構が自前のフレーム管理プロトコルを仮定して実装されているこれまでの マルチスレッド言語の実装とは対照的に, StackThreads はこれを, 3.2.4 (6)節に述べ るいくつかの条件を満たすどんなスタイルのCコードでも達成することができ る. つまり, 生成されたCコードは伝統的なCのスタックフレームとパラメタ渡 し, 返り値渡し, そして callee save registerさえも含む手続き結合コンベ ンションを使用する. 本論文の主なコントリビューションは効率的なマルチス レッディングに必要で, スタックフレームフォーマットと現在の逐次コ ンパイラの呼びだし慣例の下で実装可能なプリミティブの集合を明らか にすることである.
本節の以降の内容は以下の通りである. 3.2.2節はこ れまでのマルチスレッディングのソフトウェアによる実装における研究を再考 する. 3.2.3節は StackThreadsの機構が依存しているス タックフレームの配置とC手続きのコード生成の慣例をまとめる. 3.2.4節は 我々の機構がどのように働くかを詳しく述 べる. 3.2.5節は StackThreadsの上に組み立てられてい るいくつかの高レベル言語のコンストラクトを示す. 第 3.2.6節では性能を報告し, 3.2.7節は この研究のまとめと結論を述べる.