0

複数の静的データ ストリームが指定されている場合に、最適なスケジューリング ポリシーを見つけようとしています。例えば、

stream 0: 000---00--000

stream 1: 1111--11--11-11

stream 2: 22-222---2-2

...

ここで、"1" は 1 サイクルで処理される有効なデータを意味し、"-" は 1 サイクルのストールを意味します。ディスパッチャーは、各サイクルで 1 つのストリームからの有効なデータのみを処理できます。1 つのストリームがストールした場合、ディスパッチャは、有効なデータが待機している別のストリームにいつでも切り替えることができます。または、ディスパッチャは、他のスケジューリング ポリシーを使用してストリームの切り替えを決定できます。

たとえば、厳密なラウンド ロビン ポリシー (現在選択されているストリームが停止または null であっても、ストリーム 0 1 2 の順序に従う) を以下に示します。

DispatchTimeLine: 012012012-1201201-01201201xx1

stream 0 time line:   0xx0xx0---xx0xx0--0xx0xx0xxxx  

stream 1 time line:   x1xx1xx1xx1--1xx1--1xx1-x1xx1 

stream 2 time line:   xx2xx2-x2xx2xx2---xx2-x2xxxxx

この場合、ディスパッチャはすべてのデータを処理するのに 29 サイクルかかります。貪欲なポリシーを使用すると、合計 26 サイクルを達成できます。(「x」は待機またはアイドルを意味します。)

目標が最高のパフォーマンス (合計サイクル数の最小化) である場合、ディスパッチャーに最適なポリシーを導き出す方法は? より一般的なケースで利用できる理論的証拠はありますか?

以下は、この問題の一般的な説明です。

N 個のデータ ポイント ストリーム (0 から N-1) があり、各データ ポイント ストリーム (Di) には独自の静的データ ポイント パターン (「有効、有効、有効...ストール、ストール、...」など) があるとします。 , すなわち, "valid" ポイントと "stall" ポイントのインターリーブされたシーケンス. "valid" の数は Vi であり, "stall" の数は Si である. 各ストリーム内の時間的順序は固定されている.) 特定の制約はありません. N、Vi、Si の値、および各データ ストリームのデータ パターンも、スケジューリング中に固定されます。つまり、複数または単一のデータ ストリームが存在する可能性があり、データ ストリームの構成と長さは制限されません。

ディスパッチャに関しては、1 つのサイクルで 1 つのストリームから 1 つのデータ ポイントしか処理できません。ストリーム Di が停止すると、ディスパッチャは他のストリームを選択して移動できます。また、ディスパッチャが他のストリームを処理している場合、ストリーム Di の停止時間を非表示にすることができます。ストリーム Di のストールが完了すると、再び選択できるようになります。サイクル内ですべてのストリームがストール状態にある場合、このサイクルではデータを処理できず、NOP がディスパッチャのタイム ラインでこのサイクルを占有します。

ここでの唯一の目標は、ディスパッチャーの合計処理時間を最小にする (つまり、最高のパフォーマンスを実現する) ことです。ここには、ストリーム間の公平性など、他の要件はありません。

直観的には、上記の数値例のように、貪欲なポリシーが最適な場合があると思います。しかし、このポリシーがすべての状況で最適かどうかはわかりません。理論的に証明できるのだろうか？または、最適なスケジューリング ポリシーを見つけるプロセスを支援できる体系的な方法はありますか?

4

1 に答える 1

0

一般に、最適なスケジュールを見つけることは NP 困難であると推測します。利用可能なタスクがディスパッチャのスループットに非常に近い状態で到着する場合、スケジューリングのトリッキーさを悪用する何らかのパーティションの問題を軽減する必要があるように思われます。確かに、私が試したさまざまな貪欲なアルゴリズムはうまくいきませんでした (私が以前に気づいていなかったのは、各ストリームには 1 つの要素のみの「バッファー」があるということです)。

動的計画法を介して時間 O(n^k) で実行される、それぞれ長さ n の k 個のストリームに対する固定パラメーター アルゴリズムがあります。これは k = 48 の場合には役に立たないので、説明しません。代わりに、特定の入力の機能を利用する可能性がある制約プログラミングをお勧めします。

問題を制約プログラムとして定式化する 1 つの方法を次に示します。i番目のストリームの j番目のアイテムについて、 t ijをそのアイテムの処理が終了する整数時間とする。i番目のストリームの j番目と (j + 1)番目のアイテムの間に長さ k のストールを強制するには、t i(j+1) - t ij > k を制約します。すべての i に対して、t i1 > 0 を制約します。変数のすべての 1 つにまったく異なる制約を置き、それらの最大値を最小化します。

制約プログラムを解決するさまざまなソフトウェア パッケージがあります。それらはインテリジェントな制約の伝播と分岐戦略を使用し、ブルートフォースよりもはるかに高速である必要があります。特定の推奨事項を作成するのに十分な経験があるとは思えないので、使いやすく、適度に成熟しているように見えるものを見つけてください。

于 2014-03-27T21:56:46.803 に答える