仕事の盗みを効率的に理解する方法

現代のコンピューターはほぼ複数のプロセッサコアを搭載しており、すべてがスムーズに動作していれば、各コアは常に処理に忙しくしているはずです。基本的に、各コアにはスレッドやタスクなど、作業のキューが割り当てられ、スケジューラがこれらの作業項目を割り当てます。厄介なのは、スレッドが新しいスレッドを生成したり、実行中に追加の作業を作成したりする場合です。これらの作業は、特に子スレッドの場合は、既に何かの処理を行っているコアと同じコアによって処理されるとは限りません。OSのスケジューリング戦略に基づいて、同じコアに割り当てられることもあれば、別のコアに割り当てられることもあります。

ほとんどの場合、すべてのコアに仕事が与えられていますが、もし1つのコアが早く終わったらどうなるでしょうか？ここでワークスティーリングの出番です。あるコアがタスクを完了すると、別のコアのキューからジョブを「奪う」のです。こうすることで、ただ待機してポテンシャルを無駄にしているコアがなくなるのです。実際には、これは全体的なパフォーマンスに大きな違いをもたらす可能性があり、特に最初から完全にバランスが取れていないワークロードでは顕著です。システムやアプリがこの並列処理をサポートするように設定されていれば、パフォーマンスの向上を実感できるかもしれません。

メリットとデメリット

ワークスティーリングは、作業を動的に再分配することでプロセッサの稼働率を維持します。これによりコアのアイドル状態が防止されるため、全体的なスループットが大幅に向上します。特に、開始時にタスクが均等に分割されないワークロードでは顕著です。しかし、すべてが順調というわけではありません。コアがワークスティーリングを行う際には、データをキャッシュにロードし直す（キャッシュミスが発生した場合はシステムRAMからデータを取得する）必要があるため、ある程度のオーバーヘッドが発生します。このキャッシュミスはデータのロードを待つため、処理速度を低下させる可能性があります。もし、元のコアでタスクをより速く開始できたのであれば、これは本来の目的に反することになります。

正直なところ、このプロセスは環境によってはうまく機能するかもしれませんが、他の環境ではわずかな遅延が発生する可能性があります。少し奇妙に聞こえるかもしれませんが、特定のマシンでは、ワークスティーリングによってメリットよりもキャッシュスラッシングが大きくなることがあります。コア数が増えるほど、このバランス調整はより複雑になります。

実装

これはCPUだけの問題ではありません。多くのプログラミング環境には、ワークスティーリングのサポートが組み込まれています。例えば、Cilk（高性能コンピューティングで使用）、RustのTokioランタイム、.NETのTask Parallel Libraryといった言語が挙げられます。これらの言語は背後でワークの分散を管理し、まるで楽々と並列処理が行われているかのように見せかけます。OS自体も、タスクのスケジューリングやスレッドプールの管理といった、多くの重労働を担っています。これらの処理は通常、LinuxのpthreadやWindowsのWindows ThreadPoolなどのAPIを介して行われます。

マルチプロセスシステムでは、特定のタスクに専用のコアを割り当てるのではなく、OSが利用可能なコア全体にスケジュールするワーカースレッドのプールにタスクが追加されるのが一般的です。ここでワークスティールの仕組みが生まれます。ワーカースレッドは互いのキューからタスクを「奪う」ことで、すべてのコアをビジー状態に維持します。タスクが奪う対象として選択される方法は様々です。ランダムにコアを選び、そのキューの最後のタスクを奪うシステムもあれば、最も負荷の高いコアを選ぶシステムもあります。

結局のところ、ワークスティーリングは、ワークロードを均等に分散し、CPUのアイドル状態を回避するために多くのマルチコアシステムに組み込まれている巧妙な手法の一つに過ぎません。ほとんどのユーザーが直接目にすることはないかもしれませんが、現代の並列処理の基本的な要素です。

結論

ワークスティーリングは、過負荷のコアからアイドル状態のコアへタスクを動的に再配分することで、すべてのコアをビジー状態に保ちます。これにより、マルチコアCPUはユーザーが手動でワークロードのバランスを取ることなく効率を最大化します。もちろん、これは完璧なシステムではありません。オーバーヘッドが伴い、場合によってはキャッシュミスが発生して動作が若干遅くなることもあります。しかし、全体として、システムで適切に活用すれば、マルチスレッドプログラムの実行が大幅にスムーズになります。