9

次の問題を考えてみましょう。ワンホット エンコーディングで現在スケジュールされているスレーブを表すビット文字列があります。たとえば、「00000100」(左端のビットが #7、右端のビットが #0) は、スレーブ #2 がスケジュールされていることを意味します。

ここで、ひねりを加えて、ラウンド ロビン スケジューリング スキームで次にスケジュールされたスレーブを選択したいと思います。どのスレーブが実際にスケジュールされたいかを示す「リクエストマスク」があります。次の奴隷は希望者からのみ選ばれます。

いくつかの例 (左にローテーションすることでラウンドロビン スケジューリングが行われると仮定します)。例1:

  • 現在：「00000100」
  • マスク：「01100000」
  • 次のスケジュール: "00100000" - 通常のラウンドロビンでは、#2 の後に #3、次に #4 が来るはずですが、要求がないため、#5 が選択されます。

例 2:

  • 現在：「01000000」
  • マスク：「00001010」
  • 次: "00000010" - スケジューリングは左に循環することによって行われ、#1 はその順序で最初に要求しているスレーブです。

さて、これはループで簡単にコーディングできます。しかし、実際には、ループなしで少しいじる操作で結果を取得したいと考えています。動機: これを VHDL/Verilog のハードウェア (FPGA) に実装したい。

ボーナスは、任意の量のスレーブ N に対して汎用的なアルゴリズムを構成することです。

ところで、これは宿題の問題ではありません。何らかの方法でスレーブをスケジュールし、スレーブの要求によってスケジュールを調整したい場合はいつでも、これは重要な問題です。私の現在の解決策はやや「重い」ものであり、明らかな何かが欠けているかどうか知りたいと思っていました。

4

9 に答える 9

6

ループは悪いものである必要はありません。

私は単にするだろう

current[i] = current[i-1] & mask[i] |                         // normal shift logic
                mask[i] & current[i-2] & !mask[i-1] |         // here build logic 
                ...                                          // expression for 
                                                             // remaining

そして、それを生成ループに入れます (つまり、ハードウェアにアンロールされます)。これにより、式の並列ハードウェアが生成されます。

ここで言及されている他のソリューションでは、複数の「-」が使用されています。これは非常に高価な操作になるため、私は彼らを思いとどまらせることしかできません。特に。1 回のホットで 32 ビット以上を簡単に取得できますが、これはハードウェアでは簡単に実装できません。借用はすべてのビットを通過する必要があるためです (特定の fpgas の専用キャリー ロジックにより、少数のビットにアプローチしやすくなります)。

于 2009-01-26T17:11:07.793 に答える
4

アルテラの高度な合成クックブックでタスクを実装するための次のVerilogコードを見つけました。

// 'base' is a one hot signal indicating the first request
// that should be considered for a grant.  Followed by higher
// indexed requests, then wrapping around.
//

module arbiter (
    req, grant, base
);

parameter WIDTH = 16;

input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;
input [WIDTH-1:0] base;

wire [2*WIDTH-1:0] double_req = {req,req};
wire [2*WIDTH-1:0] double_grant = double_req & ~(double_req-base);
assign grant = double_grant[WIDTH-1:0] | double_grant[2*WIDTH-1:WIDTH];

endmodule

減算を使用するため（ただし、1回のみ）、概念的にはDougのソリューションと非常によく似ています。

于 2009-01-29T19:08:27.130 に答える
3

次のソリューションは、任意の数のスレーブ (K) に対して機能し、FPGA では O(n) です。フィールドの各ビットには、3 つの論理ゲートと 2 つのインバータが必要です。基本的なロジック シミュレータでこの概念をテストしたところ、うまくいきました。

電流とマスクの間の論理ゲートのチェーンは、基本的に、チェーン内の「下位」のビットを優先する優先順位システムを作成します。このチェーンは最後にループされますが、現在のビットを使用してチェーンが切断されます。

操作を視覚化するために、ビット3が現在のフィールドに設定されていると想像し、図の下方向に信号をたどります。ビット3の論理 1 は、最初の AND ゲートへの入力に論理 0 を配置し、その AND ゲートの出力もゼロになることを保証します (ここで、OR ゲート チェーンが壊れます)。最初の AND ゲートの出力のゼロは、2 番目の AND ゲートの入力に 1 を置きます。これにより、nextのビット2がmaskのビット2に直接依存するようになります。

ここで、OR ゲートのチェーンが登場します。

マスクのビット2が設定されている場合、そのすぐ左にある OR ゲートの論理出力も 1 になり、現在のビット2の下の AND ゲートへの入力に論理 1 が配置されます(これはゼロになります)。一度に設定できるのはcurrent の1 ビットのみであるため)。上部 AND ゲートの出力の論理 1 は、下部 AND ゲートの入力に論理 0 を配置し、次のビット1を0 に設定します。

maskのビット2が設定されていない場合、OR ゲートへの両方の入力がゼロになるため、現在のビット2の下の AND ゲートの出力はゼロになり、最下部の AND ゲートへの入力に 1 が配置されます。したがって、nextのビット1をmaskのビット1に依存させます。

このロジックは、一連の OR ゲートに従ってビットを「上向き」にし、左側から右側にループして、次の1 つのビットのみを 1に設定できるようにします。ループは、そのビットが設定された結果、current のビット3に戻ると停止します。これにより、回路が永久ループに留まることを防ぎます。

私は Verilog や VHDL の経験がないので、実際のコードはあなたと残りの stackoverflow に任せます。

代替テキスト http://img145.imageshack.us/img145/5125/bitshifterlogicdiagramkn7.jpg

ノート：

  1. このソリューションは部分的なものです。ビットフィールドを保持するには、何らかのラッチメカニズムが必要です。
  2. ビット数を増やすと、ゲート電圧が安定するまでに必要な時間も長くなることに注意してください。
  3. 現在のフィールドがゼロに等しい場合を処理するには、何らかのロジックが必要です。このスタックオーバーフローの質問を参照してください。
于 2009-01-28T04:26:54.043 に答える
2

ここでは、サブラクト1が重要なアイデアです。これは、次のタスクを見つけるためにビットを介して借用をカスケードするために使用されます。

bits_before_current = ~(current-1) & ~current
bits_after_current = current-1
todo = (mask & bits_before_current) 
if todo==0: todo = (mask & bits_after_current) // second part is if we have to wrap around
next = last_bit_of_todo = todo & -todo

ただし、これは内部でループを使用します...

于 2009-01-26T16:57:51.253 に答える
2

面白い問題！スケジューラーの操作を単純化できないので、この種の操作が必要になるのではないかと思います。

あなたがVHDLを知っているので、私は詳細には立ち入りませんが、私の提案は次のようになります：

3ビットエンコーダーを使用して、現在スケジュールされているタスクを数値に変換します。

01000000-> 6

次に、バレルシフタを使用して、マスクをその数+ 1だけ回転させます（現在のタスクをスキップするため）。

00001010-> 00010100

次に、プライオリティエンコーダを使用して、最初に利用可能な「次の」タスクを見つけます。

00010100-> 00000100-> 2

次に、追加してバレルシフタを逆にします。

（2 + 7）％8 = 1

再エンコードすると、次にスケジュールされたタスクが提供されます。

00000010

バレルシフタは不動産の面で「高価」ですが、非常に高速で簡単なはずですが、現時点ではそれを回避する簡単な方法はわかりません。

編集：ダグのソリューションははるかにエレガントです...

-アダム

于 2009-01-26T16:59:01.203 に答える
2

2 の補数表現を仮定すると、C で2 つの単語maskを and と呼びます。current

mask_lo = (current << 1) - 1; // the bits to the right and including current
mask_hi = ~mask_lo;           // the bits to the left of current
                              // the left bits, otherwise right:
next = (mask & mask_hi) ? (mask & mask_hi) : (mask & mask_lo);
return (next & -next);        // the least significant bit set
于 2009-01-26T16:48:02.007 に答える