terminology - 「仕事盗み」vs.「仕事肩こり」？

Question

動的な負荷分散戦略として、「ワーク スティーリング」に関する多くの情報が見つかり、「ワーク シュラギング」に関する情報が何もないのはなぜですか?

「仕事を肩代わりする」とは、アイドル状態のプロセッサが忙しい隣人から仕事を引き出すのではなく、余剰の仕事を忙しいプロセッサから負荷の低い隣人に押しやることを意味します (「仕事を奪う」)。

一般的なスケーラビリティは、両方の戦略で同じであるべきだと思います。ただし、待ち時間と消費電力の観点から、すべてのアイドル状態のプロセッサがすべてのネイバーに可能な作業を定期的にポーリングするよりも、実行すべき作業が確実にあるときにアイドル状態のプロセッサをウェイクアップする方がはるかに効率的であると私は信じています。

とにかく、簡単なグーグルは「肩をすくめる仕事」などの見出しの下に何も表示されなかったので、この戦略の先行技術と専門用語へのポインタは大歓迎です。

明確化

私は実際に、プロセッサ(ターゲット プロセッサである場合もそうでない場合もある) が、優先されるターゲット プロセッサのすぐ近くの場所を (データ/コードの場所に基づいて) 調べて、近くの隣人に新しい彼らはするべき仕事がそれほど多くないので、代わりに働きます。

ここで、決定ロジックが、直近の (通常は 2 から 4) 近隣の推定 q 長のアトミックな読み取り以上のものを必要とするとは思いません。これは、泥棒が隣人からポーリングして盗むことによって暗示される以上の結合ではないと思います. （両方の戦略で「ロックフリー、ウェイトフリー」キューを想定しています）。

解像度

「仕事を肩をすくめる」戦略として私が意味したこと (ただし、部分的にしか説明されていません!) は、たまたまプロセッサ、キャッシュとメモリの忠実性、およびスケーラビリティについてスマートな「通常の」事前スケジューリング戦略の領域にあるようです。

これらの用語で検索すると多くの参考文献が見つかり、そのうちのいくつかはかなりしっかりしているように見えます。「仕事を肩をすくめる」の定義で私が念頭に置いていたロジックに最も一致する (または取り壊す!) ものを特定したら、参考文献を投稿します。

Answer 1

負荷分散は無料ではありません。（カーネルへの）コンテキストスイッチ、アイドル状態のプロセッサの検索、および再割り当てする作業の選択のコストがかかります。特に、タスクが常に1秒間に数十回切り替わるマシンでは、このコストが加算されます。

では、違いは何ですか？肩をすくめるということは、負荷分散のオーバーヘッドで、過剰にプロビジョニングされたリソース（ビジーなプロセッサー）にさらに負担をかけることを意味します。隣に何もすることがないプロセッサがあるのに、なぜビジー状態のプロセッサをadministriviaで中断するのですか？一方、ワークスティーリングを使用すると、アイドル状態のプロセッサがロードバランサを実行し、ビジー状態のプロセッサが作業を続行できます。仕事を盗むことは時間を節約します。

例

考えてみてください。プロセッサAには2つのタスクが割り当てられています。それぞれ時間a1とa2かかります。近くのプロセッサB（おそらくキャッシュバウンスの距離）はアイドル状態です。プロセッサはすべての点で同一です。各タスクのコードとカーネルが両方のプロセッサのiキャッシュにあると想定します（負荷分散でページフォールトが追加されることはありません）。

あらゆる種類のコンテキストスイッチ（負荷分散を含む）には時間がかかりますc。

負荷分散なし

タスクを完了する時間はa1+a2+cになります。プロセッサAがすべての作業を行い、2つのタスク間で1つのコンテキストスイッチが発生します。

仕事を盗む

Bがa2を盗み、コンテキストスイッチ時間自体が発生するとします。作業はmax（a1、a2 + c）時間で行われます。プロセッサAがa1で動作を開始するとします。その間、プロセッサBはa2を盗み、a1の処理の中断を回避します。Bのすべてのオーバーヘッドはフリーサイクルです。

a2がより短いタスクであった場合、ここでは、このシナリオでコンテキストスイッチのコストを効果的に隠しています。合計時間はa1です。

仕事-肩をすくめる

上記のようにBがa2を完了したと仮定しますが、Aはそれを移動する（作業を「肩をすくめる」）コストを負担します。この場合の作業は、max（a1、a2）+c時間で実行されます。コンテキストスイッチは、非表示ではなく、常に合計時間に追加されるようになりました。ここでは、プロセッサBのアイドルサイクルが無駄になっています。代わりに、ビジー状態のプロセッサAが時間を肩をすくめる作業をBに費やしました。

Answer 2

このアイデアの問題は、実際の作業を行うスレッドが、アイドル状態のプロセッサを常に探して時間を無駄にすることだと思います。もちろん、アイドル状態のプロセッサのキューを作成するなど、それを高速化する方法はありますが、そのキューが同時実行性のボトルネックになります。ですから、何もすることがないスレッドを座って仕事を探す方が良いのです。

Answer 3

「ワーク スティーリング」アルゴリズムの基本的な利点は、全員が忙しいときに、ワークを移動するオーバーヘッドが 0 になることです。そのため、一部のプロセッサがアイドル状態になっている場合にのみオーバーヘッドが発生し、そのオーバーヘッド コストの大部分はアイドル状態のプロセッサによって支払われ、使用中のプロセッサへのバス同期関連のコストはごくわずかです。

Answer 4

いくつかの問題... 使用中のスレッドが使用中の場合、オフロードするアイドル スレッドを投機的に探すのではなく、実際の作業の処理に時間を費やしたくありませんか?

スレッドは、作業が多すぎてその作業を停止して、助けてくれる友人を探す必要がある場合、どのように判断するのでしょうか?

他のスレッドにはそれほど多くの作業がなく、オフロードする適切なスレッドを見つけることができないことをどうやって知ることができますか?

ワーク スチールはより洗練されているように見えます。これは、同じ問題 (競合) を解決するために、負荷分散を行っているスレッドが負荷分散のみを行っており、それ以外の場合はアイドル状態であることが保証されるためです。

あなたが説明したことは、長期的には効率が大幅に低下するだけでなく、許容できる結果を得るためにシステムごとに多くの調整が必要になるというのが私の直感です。

編集では、プロセッサを送信してこれを処理することをお勧めしますが、以前に提案したワーカースレッドやここのコメントの一部ではありません。サブミット プロセッサが最小のキュー長を検索している場合、サブミットにレイテンシが追加される可能性がありますが、これは実際には望ましいことではありません。

しかし、もっと重要なことは、ワークスティーリングの補助的なテクニックであり、相互に排他的なテクニックではありません. ワークスティーリングは制御するために発明されたという主張の一部は潜在的に軽減されましたが、良い結果を得る前にまだ調整すべきことがたくさんあります。これらの調整はすべてのシステムで同じではありません。仕事を盗むことがあなたを助ける状況に遭遇するリスクはまだあります。

投稿スレッドが「スマートな」作業分散を行うという編集された提案は、作業盗用に対する時期尚早の最適化である可能性があると思います。アイドル スレッドがバスを酷使しすぎて、非アイドル スレッドが作業を完了できなくなっていませんか? 次に、ワークスティーリングを最適化するときが来ます。

Answer 5

私が理解しているように、ワーク スティーリングは高度に並列化されたシステム向けに設計されており、単一の場所 (単一のスレッドまたは単一のメモリ領域) が作業を共有することを回避します。このボトルネックを回避するために、単純なケースでは非効率性が導入されると思います。

アプリケーションが並列化されていないため、単一の作業点の分散がスケーラビリティの問題を引き起こす場合は、提案したように明示的に管理することでパフォーマンスを向上できると期待しています。

あなたが何をグーグルで検索するのかわかりませんが、恐れています。

Answer 6

したがって、「Work Stealing」とは対照的に、ここで「Work Shrugging」が実際に意味するのは、プロセッサ、キャッシュ、メモリの忠誠心について賢く、スケーラブルな通常の先行作業スケジューリング戦略です。

上記の用語/専門用語の組み合わせを検索すると、フォローアップするための多くの実質的な参照が得られます。マシン仮想化の追加の複雑さに対処するものもありますが、これは実際には質問者の懸念事項ではありませんでしたが、一般的な戦略は依然として適切です。