タスク並列処理系におけるCPUの利用効率に着目したスケジューリング手法

大筒, 裕之, 中島, 潤, 田浦, 健次朗

一般にタスク並列処理系は，アイドル状態になったワーカスレッドが他のワーカスレッドからタスクを奪うワークスチールによって，動的に負荷分散を行なっている．しかし，多くのタスク並列処理系では，プロセス全体で実行可能なタスクの数がワーカスレッド数に対して少ない場合には，アイドル状態のワーカスレッドが成功しないワークスチールを行い続けてしまう．このような状態はCPU資源を有効に利用できているとは言えない．そこで本研究では，(1)スチール可能なタスクが存在しない場合はワーカスレッドを可能な限り速やかにスリープさせる(2)新たなタスクが生まれたらスリープしているワーカを速やかに起こす，という2つの方針を採る．それにより，並列処理系の台数効果への悪影響を抑えつつ，余剰のワーカがCPUを消費しないようにワーカスレッドの挙動を管理する方式を提案する．また，我々が開発しているタスク並列処理系であるMassiveThreadsにこの手法を実装し，評価を行った．

Most task parallel frameworks balance loads dynamically by an idle worker thread that steals a task from another worker thread. In most frameworks, however, the idle worker thread fails in work-stealing when the number of runnable tasks is less than that of worker threads which leads to waste of CPU resources. Our work uses following two strategies: (1) Make worker threads sleep as soon as possible when no task to be stolen exists. (2) wake up sleeping workers as soon as possible when new tasks are created. Our approach prevents idle worker threads from consuming CPU resources and keeps well load-balancing. We implemented this methods into our task parallel framework called MassiveThreads and evaluated its performance.

タスク並列処理系におけるCPUの利用効率に着目したスケジューリング手法

Bibliographic Information

Description

Journal

Keywords

Details 詳細情報について

Export

Report a problem