0

このアルゴリズムについては、次の論文で説明されています: Thread Scheduling for Multiprogrammed Multiprocessors。簡単に言えば、計算はプロセスに分散され、各プロセスにはジョブを実行するためのスレッドのキューがあります。プロセスはスレッドをその両端キューの下部に (から) プッシュ (ポップ) でき、他のプロセスはスレッドを上部からポップすることでそこから盗むことができます。このように、プッシュ操作によって動的にワークを作成することができます。アルゴリズムは以下です。

スケジューリングアルゴリズム

私の質問は、popTop() のワーク スチール機能に関するものです。すべての場合に適切に機能するとは思いません。たとえば、キュ​​ー Q を持つプロセス A と、popTop() を呼び出して Q から作業を盗もうとしているプロセス B を想定します。また、この時点で popTop() の 2 行目以降で B がプリエンプトされ、localBot = X であるとします。A が実行され、popBottom() が Q <= X の最後まで実行された場合、B が実行を再開すると、A によって既に処理されたスレッドが取得されます。

私の考えは正しいですか？CUDAプログラムでワークバランシングを行うために実装するので、検証する必要があります。

4

1 に答える 1

2

コードは cas() (比較とスワップ) を使用して、記述している種類のものを停止しようとしています。popTop() が 2 行目以降で停止する場合、age と bot を読み込んだ後に停止します。次に popBottom() が実行されてスレッドが返されると、age 内のフィールドがインクリメントされ、cas() を使用してインクリメントされたバージョンがメモリに書き込まれます。ここで、B が再開して cas() を呼び出すと、cas() 命令は、B が age に提供した値がメモリ内の値と一致しないことを検出します (つまり、この cas() への呼び出しはメモリを変更しません)。したがって、B は (oldAge == newAge) を検出し、ABORT を返します。このような状況では、通常、もう一度やり直して、次回はうまくいくことを期待します。この記事では、運が良ければyield()の呼び出しが必要であると言っているようですが、いずれにせよpopTop()は他の誰かがつかんだスレッドを返すべきではありません。

もちろん、 http://en.wikipedia.org/wiki/Compare-and-swapに cas() に関するウィキペディアの記事があります。

ロックを使用する並列コードは、シリアル コードより 1 レベル上の難易度で配置し、ロックなしの並列コードは、ロックする並列コードよりも 1 レベル上の難易度で配置します。パフォーマンスが必要であることが確実にわかっていない限り、ロックフリーの並列コードを作成することはなく、再利用できる既知の信頼できるコードが存在しませんでした。私は徹底的にテストするまでそのようなコードを信用しませんし、可能であればモデルチェックも行いたいと思っています。

于 2012-07-04T17:55:54.007 に答える