背景: データフロー グラフとして表示される独立したタスクがあります (これは永遠に繰り返されます)。非常に単純な例:
タスク 1: b1 -> c
タスク 2: e -> b2
プロセッサの割り当てが与えられます。グラフ自体は、それらが実行される利用可能なプロセッサを説明しています。上記の例では、b1 と b2 はプロセッサ b で実行され、c は c で実行され、e は e で実行されます。
すべてのタスクの実行時間は、コンパイル時にわかります。ラウンド ロビン モデリングであるため、各タスクの最悪の場合の実行時間は、ラウンド ロビン スケジューリングのリソース調停をキャプチャするように変更されます。例: 上記の例のすべてのタスクの実行時間が 1 だったとします。次に、タイミングを b1 と b2 に 2 時間単位、c と e に 1 時間に変更します。これは、プロセッサ b が次のコードを実行するためです。 (); run_task_b2(); したがって、タスク 1 を (スループットなどについて) 分析して、タスク b1 が 2 時間単位を要し、プロセッサ b での b1 と b2 の共有で十分であると言うと、効果的です。
私の問題:各タスクは追加のリソース (DMA) を使用します。2 つの DMA があるとします。次のように単純に D1 と D2 を割り当てた場合:
b1 は D1を取得し
ます c は D2を取得します
e は D1を取得します
b2 は D2 を取得します
ラウンドロビン モデリングの後、b1 と b2 は実行時間 3 を取得します (b1 は D1 を e と共有し、b1、b2 はプロセッサ b を共有するため、 1+1+1 = 3) および c と e は時間 2 を取得します (c は D2 を b2 と共有し、e は D1 を b1 と共有します)。したがって、時間は 3,2,2,3 です。
しかし、割り当てを次のように指定すると、 b1 が D1 を取得
c が D2を取得
e が D2を取得
b2 が D1 を取得
モデル化された実行時間は 2、2、2、2 です。
では、モデル化された RR 時間が最小になるように、特定のタスク グラフのコンパイル時にリソース (DMA) 割り当て (静的割り当て) を見つけるアルゴリズムを作成するにはどうすればよいでしょうか? 上記の例で説明したように、リストのスケジューリングは非効率的な結果をもたらします。