Leapfrogging
[48]
は Multilisp の future コンストラクトを
実装している. 式 e を評価するスレッドは future 式
(future e) によって生成される. Leapfrogging は
後に述べる条件を満たす限り, 定数個(普通はプロセッサの個数)のスタックで
任意の数の future をサポートすることのできる技法である.
プロセッサが future 式に出会ったときには, プロセッサは式の
継続の評価を続け,
eのデスクリプタを共有タスクプールに残す.
タスクは未決定の future の値を必要とするときにはブロック
するかもしれない. もし, タスク T を実行しているプロセッサが
未決定のfuture F に出会ったときには, プロセッサは
現在のスタックの上で F の
サブタスク(F自身も含む)の評価を始める.
この戦略はCのスタックフレーム管理機構によって自然に
表現される. プロセッサは単に F の適切なサブタスクを
持ってきて, F を評価する手続きを呼び出す. 暗に言いたいことは,
ブロックしたスレッド T は F のサブタスクが終わってからのみ
再開されるということである. この決定は, F の値を決定することが,
サブタスクの値を決定することを要求する限り正しい. なぜなら
この場合, F の値を必要とすることがわかっている T を
再開することは推移的にサブタスクの値の決定を必要とするからである.
まとめると, leapfrogging は, 下のスレッドがブロックし,
かつ, 上のスレッドと独立であるかぎり(スタックは上に伸びると仮定する),
二つのタスクを一つのスタックで評価できる. 独立かもしれない
複数のタスクを評価することは, 従って多数のスタックを必要とする.
Leapfroggingの並行モデルは一般のマルチスレッドモデルよりも いくつかの意味で限定されている. まず一つめに, 投機的 計算をサポートしていない. 彼らが [48] で指摘しているように, もし F のサブタスクが投機的で, F の値に対して貢献を しないならば, leapfrogging は一般のマルチスレッドモデルでは 起こらないデッドロックを引き起こすかもしれない. 二番目に, それはfutureを通じての生産者-消費者型の同期だけのサポートで, 一般の同期プリミティブをサポートしていないこと. より具体的に言うと, それはブロックしたスレッドが再開させる スレッド, つまりブロックスレッドを再開しようとするスレッド を知っていることを仮定している. この条件は future の型に はまった使用の中では成り立つが, mutex や condition variable のような 一般の同期プリミティブに対しては成り立たない. 最後に, それは分散メモリ並列計算機上で特に重要な タスクの激しい移動や, アプリケーションspecificな タスク配置を奨励していない. やはりこれも独立なタスクが 一つのスタック上に共存することを許していないためである. 新しいタスクは空のスタックが使用可能になったときにのみ評価される.
Lazy RPC [17] は同じアイデアに基づいている. 相違は, タスクがブロックしたときには, プロセッサはタスクプールの 任意のタスクの評価を始めることである. 上の議論と制限は Lazy RPC にも当てはまる. 一方, StackThreads は一つの プロセッサにつき一つのスタック(もしくは定数個のスタック)で 一般的なマルチスレッドを実装している. 鍵となる機構は スタック巻き戻しである. それによって我々は投機的に 一つのスタックで独立のタスクを評価し, 一番上の タスクがブロックしたときには決定を取り消すことができる. Lazy RPC の leapfrogging とは異なり, StackThreads は スタックフレームを動かすために, スタックフレームを動かさないと 仮定しているCプログラムおよびCコンパイラの 最適化とは両立できない. それゆえに, StackThreads の主要な用途は, Cのユーザレベルライブラリ というよりはむしろ, コンパイラのターゲットである.