仕事の盗み

並列コンピューティングでは、ワーク スティーリングは、マルチスレッドコンピュータ プログラムのスケジュール戦略です。これは、固定数のプロセッサ (またはコア) を持つ静的マルチスレッドコンピュータ上で、新しい実行スレッドを「生成」できる動的マルチスレッドコンピューティングを実行する問題を解決します。これは、実行時間、メモリ使用量、およびプロセッサ間通信の点で効率的に実行されます。

ワーク スティール スケジューラでは、コンピュータ システム内の各プロセッサに、実行する作業項目 (計算タスク、スレッド) のキューがあります。各作業項目は、順番に実行される一連の命令で構成されますが、実行中に、作業項目は、他の作業と並行して実行可能な新しい作業項目を生成することもあります。これらの新しい項目は、最初に、作業項目を実行しているプロセッサのキューに置かれます。プロセッサの作業がなくなると、他のプロセッサのキューを調べて、その作業項目を「スティール」します。実際には、ワーク スティールは、アイドル状態のプロセッサにスケジューリング作業を分散し、すべてのプロセッサに作業がある限り、スケジューリングのオーバーヘッドは発生しません。^[1]

ワークスティーリングは、動的マルチスレッドのもう1つの一般的なスケジューリング手法であるワークシェアリングとは対照的です。ワークシェアリングでは、各作業項目が生成されると、プロセッサにスケジュールされます。この手法と比較して、ワークスティーリングでは、すべてのプロセッサに作業がある場合にこのような移行が発生しないため、プロセッサ間のプロセス移行の量が減少します。^[2]

ワークスティーリングの考え方は、 1980年代のMultilispプログラミング言語の実装と並列関数型プログラミング言語の研究にまで遡ります。 ^[2] Cilkプログラミング言語のスケジューラ、^[3] Javaフォーク/ジョインフレームワーク、^[4] .NETタスク並列ライブラリ、^[5] Rust Tokioランタイムで採用されています。^{[6] [} 7 ]

ワークスティーリングは、並列計算の「厳密な」フォーク・ジョインモデル用に設計されており、計算は単一のソース（計算の開始）と単一のシンク（計算の終了）を持つ有向非巡回グラフとして見ることができます。このグラフの各ノードは、フォークまたはジョインのいずれかを表します。フォークは、さまざまな「スレッド」 ^[2]または「ストランド」と呼ばれる複数の論理的に並列な計算を生成します。 ^[8]エッジはシリアル計算を表します。^{[9] [注 1]}

例として、Cilk のような構文で書かれた次の単純な fork-join プログラムを考えてみましょう。

関数f(a, b):
    c ←フォークg(a)
    d ← h(b)
    参加する
    c + dを返す

関数g(a):
    × 2を返す

関数h(a):
    b ←フォークg(a)
    c ← a + 1
    参加する
    b + c を返す

関数呼び出しf(1, 2)は、次の計算グラフを生成します。

グラフでは、2 つのエッジがノードを離れると、エッジ ラベルによって表される計算は論理的に並列になります。つまり、並列または順次に実行できます。計算は、入力エッジによって表される計算が完了した場合にのみ、結合ノードを通過できます。スケジューラの作業は、計算全体が正しい順序 (結合ノードによって制約される) で完了するように、計算 (エッジ) をプロセッサに割り当てることです。これは、可能な限り高速に行うのが望ましいです。

Blumofe と Leiserson が提案したワーク スティーリング アルゴリズムのランダム化バージョンでは、複数の実行スレッドが維持され、これらがプロセッサにスケジュールされます。各プロセッサには、スレッドの両端キュー(deque) があります。deque の両端を「トップ」と「ボトム」と呼びます。 ${\displaystyle P}$

現在実行中のスレッドを持つ各プロセッサは、4つの「特別な」動作のいずれかを引き起こす命令に遭遇するまで、スレッド内の命令を1つずつ実行します。^{[2] : 10}

• spawn命令により、新しいスレッドが作成されます。現在のスレッドはデキューの一番下に配置され、プロセッサは新しいスレッドの実行を開始します。
• ストール命令は、スレッドの実行を一時的に停止する命令です。プロセッサはデキューの一番下からスレッドをポップし、そのスレッドの実行を開始します。デキューが空の場合、以下で説明するワーク スチールを開始します。
• 命令によってスレッドが停止する場合があります。この場合の動作は、停止する命令の場合と同じです。
• 命令によって別のスレッドが有効になる場合があります。別のスレッドはデキューの一番下にプッシュされますが、プロセッサは現在のスレッドの実行を継続します。

最初、計算は 1 つのスレッドで構成され、あるプロセッサに割り当てられ、他のプロセッサはアイドル状態になります。アイドル状態になったプロセッサは、実際のワーク スティーリング プロセスを開始します。これは次のことを意味します。

• 別のプロセッサを均一にランダムに選択します。
• 他のプロセッサのデキューが空でない場合は、デキューから最上位のスレッドをポップし、その実行を開始します。
• それ以外の場合は繰り返します。

spawnの規則では、Blumofe と Leiserson は、関数呼び出しを実行するかのように「親」スレッドが新しいスレッドを実行することを提案していることに注意してください (C のようなプログラムf(x); g(y); では、関数fの呼び出しはgの呼び出しが実行される前に完了します)。これは、生成されたスレッドの実行中に関数の継続を盗むことができるため、「継続窃盗」と呼ばれ、 Cilk Plusで使用されるスケジューリング アルゴリズムです。^{[8]これは、ワーク スティーリングを実装する唯一の方法ではありません。代替戦略は「子窃盗」と呼ばれ、}コンパイラのサポートなしでライブラリとして実装する方が簡単です。^{[8]子窃盗は、} Threading Building Blocks、Microsoft の Task Parallel Library、およびOpenMPで使用されますが、後者ではプログラマがどの戦略を使用するかを制御できます。^[8]

ワーク・スティールにはいくつかのバリエーションが提案されている。Blumofeと Leiserson によるランダム化バリエーションは、プロセッサ上で期待時間 で並列計算を実行する。ここで、はワーク、つまりシリアル・コンピュータで計算を実行するのに必要な時間であり、はスパン、つまり無限並列マシンで必要な時間である。 ^{[注 2]}これは、期待値 において、必要な時間は最大でも理論上の最小値の定数倍であることを意味する。^[2]ただし、最悪の場合、実行時間 (特に、実行されたスティールの数) は で指数関数的になる可能性がある。 ^[10]プロセッサが空いているときはいつでも自分のワークをスティールバックしようとする局所的なバリエーションも理論的および実践的に分析されている。^{[11] [12]}${\displaystyle T_{1}/P+O(T_{\infty })}$${\displaystyle P}$${\displaystyle T_{1}}$${\displaystyle T_{\infty}}$${\displaystyle T_{\infty}}$

ブルーモフェ・ライザソン版のワークスティーリングでスケジュールされた計算は、単一のプロセッサ上で同じ計算を行う際のスタック使用量が であった場合、スタックスペース を使用し、 ^{[2] は}著者らの以前の空間効率の定義に適合する。^[13]この制限は継続スティーリングを必要とするが、子スティーリングスケジューラでは次の例からわかるように、この制限は成立しない。^[8]${\displaystyle O(S_{1}P)}$ ${\displaystyle S_{1}}$

i = 0からnの場合:
     fork f(i)
 join

子を盗む実装では、fへのすべての「フォークされた」呼び出しが作業キューに入れられ、サイズnまで大きくなります。これは任意の大きさにすることができます。

前述のワーク スティール アルゴリズムとその分析では、計算が専用プロセッサのセットにスケジュールされるコンピューティング環境を想定しています。マルチプログラミング(マルチタスク) 環境では、アルゴリズムを変更して、計算タスクをワーカースレッドのプールにスケジュールし、ワーカースレッドがオペレーティング システムスケジューラによって実際のプロセッサにスケジュールされるようにする必要があります。任意の時点で、OS スケジューラは、コンピュータ内のP 個のプロセッサのうちP _A ≤ P 個のプロセッサをワーク スティール プロセスに割り当てます。これは、他のプロセスが残りのプロセッサを使用している可能性があるためです。この設定では、 P 個のワーカースレッドのプールを使用したワーク スティールには、泥棒として動作するワーカーがライブロックを引き起こす可能性があるという問題があります。つまり、実際には有用なタスクを生成するワーカーの実行をブロックする可能性があります。^{[14] [15]}

このような状況のために、期待される時間内に計算を実行するワークスティーリングの変種が考案された。

$${\displaystyle O\left({\frac {T_{1}}{P_{\mathrm {avg} }}}+{\frac {T_{\infty }P}{P_{\mathrm {avg} }}}\right),}$$

ここで、Pavg_はOSスケジューラが計算の実行時間中に計算に割り当てたプロセッサの平均数である。^[16] マルチプログラミングワークスケジューラは、従来のバージョンとは2つの点で異なります。

• キューは非ブロッキングです。専用プロセッサでは、キューへのアクセスはロックを使用して同期できますが、マルチプログラミング環境では、オペレーティング システムがロックを保持しているワーカー スレッドをプリエンプトし、同じキューにアクセスしようとする他のワーカーの進行をブロックする可能性があるため、これは推奨されません。
• 作業を奪おうとするたびに、ワーカー スレッドは、飢餓状態を防ぐために、スケジュールされているプロセッサを OS に譲る「 yield 」システム コールを呼び出します。

マルチプログラミングワークスティーラーを改良する試みは、キャッシュの局所性の問題^[12]とキューデータ構造の改良に焦点が当てられてきました。^[17]

動的マルチスレッド計算のためのいくつかのスケジューリングアルゴリズムは、ワークスティーリングと競合します。従来のワークシェアリングアプローチの他に、並列深さ優先（PDF）と呼ばれるスケジューラがあり、ワークスティーリングの空間境界を改善し、^[18]チップマルチプロセッサのコアがキャッシュを共有する状況では、より優れたパフォーマンスを発揮します。^[1]