いろいろなラウンドロビンを実装する！
石谷@PEZY Computingです。HDL Advent Calender 2022 の3日目ということで、今年は趣向を変えて、ラウンドロビンについて書いていきたいと思います。
はじめに
ラウンドロビンはよく使う調停回路で、バスの MUX などでよく出てくるかと思います。安直に実装するなら、以下の様な実装になるかと思います。
function automatic logic [3:0] do_round_robin(logic [3:0] request, logic [1:0] currnet_grant);
logic [1:0] index;
for (int i = 1;i <= 4;++i) begin
index = (currnet_grant + i) % 4;
if (request[index]) begin
return 4'(1 << index);
end
end
return '0;
endfunction
Microarchitecture of Network on Chip Routers: A Designer's Perspective に面白い実装方法が載っていたので、まずはその実装方法を紹介します。次に、優先順位付きラウンドロビンなど、変種のラウンドロビンを、この方法を応用して実装していきたいと思います。
基本の回路
上記の書籍で紹介されている方法では、入力リクエストを走査する代わりに、「ある数列を入力し、最大値を持つ位置を返す」回路を使って、ラウンドロビンを実装しています。以下が、その安直な実装になります。
function logic [ELEMENTS-1:0] find_max_index(logic [ELEMENTS-1:0][WIDTH-1:0] values);
logic [WIDTH-1:0] max_value;
logic [ELEMENTS-1:0] result;
max_value = values[0];
result = ELEMENTS'(1);
for (int i = 1;i < ELEMENTS;++i) begin
if (max_value < values[i]) begin
max_value = values[i];
result = ELEMENTS'(1 << i);
end
end
return result;
endfunction
上記の function に与える values を工夫することで、ラウンドロビンを実現します。
ラウンドロビン
通常のラウンドロビンを実現する場合、values は 2 ビット幅で、以下のようにして作ります。
- 1 ビット目
- request が入力されているか
- request[index]
- 0 ビット目
- 現在 grant を得ている request より大きいインデックスを持つか
- index > current_grant
request の幅が 8 ビット幅で、現在 grant を得ている request が 2 ビット目の場合の、values の例は以下の通りです。
| index | request | index > current_grant | value | grant |
|---|---|---|---|---|
| 0 | 0 | 0 (0 > 2) | 0b00 | |
| 1 | 1 | 0 (1 > 2) | 0b10 | |
| 2 | 1 | 0 (2 > 2) | 0b10 | |
| 3 | 0 | 1 (3 > 2) | 0b01 | |
| 4 | 1 | 1 (4 > 2) | 0b11 | win! |
| 5 | 0 | 1 (5 > 2) | 0b01 | |
| 6 | 1 | 1 (6 > 2) | 0b11 | |
| 7 | 1 | 1 (7 > 2) | 0b11 |
この値を find_max_index に入力すると、最大値 3 を持つ一番最初の位置は 4 ビット目なので、0b0001_0000 を返します。なので、次に grant を得る request は 4 ビット目の request になります。
ラウンドロビンでは、現在 grant を得ている request の隣 (3 ビット目) から走査を開始するので、4 ビット目の request が初めてヒットする request となり、find_max_index を使った方法と合致することがわかります。
次の例は、現在 grant を得ている request が 7 ビット目の場合です。最大値 2 を持つ一番最初の位置は 1 ビット目なので、次に grant を得る request は 1 ビット目の request となります。
| index | request | index > current_grant | value | grant |
|---|---|---|---|---|
| 0 | 0 | 0 (0 > 7) | 0b00 | |
| 1 | 1 | 0 (1 > 7) | 0b10 | win! |
| 2 | 1 | 0 (2 > 7) | 0b10 | |
| 3 | 0 | 0 (3 > 7) | 0b00 | |
| 4 | 1 | 0 (4 > 7) | 0b10 | |
| 5 | 0 | 0 (5 > 7) | 0b00 | |
| 6 | 1 | 0 (6 > 7) | 0b10 | |
| 7 | 1 | 0 (7 > 7) | 0b10 |
優先順位付きラウンドロビン
通常のラウンドロビンでは平等に grant が与えられますが、ある位置の reuqest に対して優先的に grant を与えたい場合もあります。values を拡張し、優先度を埋め込むことで、実現可能です。
上記の例に対して、2 ビットの優先度を表す値を付与してみます。次の例は、現在 grant を得ている request が 2 ビット目の場合です。
| index | request | priority | index > current_grant | value | grant |
|---|---|---|---|---|---|
| 0 | 0 | 3 | 0 (0 > 2) | 0b0110 | |
| 1 | 1 | 3 | 0 (1 > 2) | 0b1110 | win! |
| 2 | 1 | 2 | 0 (2 > 2) | 0b1100 | |
| 3 | 0 | 2 | 1 (3 > 2) | 0b0101 | |
| 4 | 1 | 1 | 1 (4 > 2) | 0b1011 | |
| 5 | 0 | 1 | 1 (5 > 2) | 0b0011 | |
| 6 | 1 | 0 | 1 (6 > 2) | 0b1001 | |
| 7 | 1 | 0 | 1 (7 > 2) | 0b1001 |
1 ビット目が最大値 14 を持つので、次に grant を得る request は 1 ビット目の request になります。通常のラウンドロビンでは 4 ビット目の request に grant が与えられますが、優先度が効いていることがわかります。
次の例は、優先度が高い request が入力されていない場合で、現在 grant を得ている request は 4 ビット目の request とします。
| index | request | priority | index > current_grant | value | grant |
|---|---|---|---|---|---|
| 0 | 0 | 3 | 0 (0 > 4) | 0b0110 | |
| 1 | 0 | 3 | 0 (1 > 4) | 0b0110 | |
| 2 | 0 | 2 | 0 (2 > 4) | 0b0100 | |
| 3 | 0 | 2 | 0 (3 > 4) | 0b0100 | |
| 4 | 1 | 1 | 0 (4 > 4) | 0b1010 | |
| 5 | 1 | 1 | 1 (5 > 4) | 0b1011 | win! |
| 6 | 1 | 0 | 1 (6 > 4) | 0b1001 | |
| 7 | 1 | 0 | 1 (7 > 4) | 0b1001 |
5 ビット目が最大値 13 を持つので、次に grant を得る request は 5 ビット目の request になります。同じ優先度を持つ 4 ビット目の request も入力されていますが、ラウンドロビンが効いて 5 ビット目の request に grant が与えられたことがわかります。
重み付きラウンドロビン
重み付きラウンドロビンは、request 毎に grant を与える頻度 (重み) を変更できる機能を有するラウンドロビンです。設定された回数（重み）分の grant を得た request の優先度を下げることで実現できます。この「優先するかしないか」を values に組み込むことで、重み付きラウンドロビンに対応することができます。
用いる values は 3 ビット幅で、その構成は、
- 2 ビット目
- request が入力されているか
- request[index]
- 1 ビット目
- 重み
- grant を得るごとに減っていく
- weight[index] > 0
- 重み
- 0 ビット目
- 現在 grant を得ている request より大きいインデックスを持つか
- index > current_grant
となります。
以下の例は、重みの幅は 2 ビット幅で、現在 grant を得ている request は 3 ビット目の request とします。
| index | request | weight | weight > 0 | index > current_grant | value | grant |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 (0 > 2) | 0b000 | |
| 1 | 1 | 0 | 0 | 0 (1 > 2) | 0b100 | |
| 2 | 0 | 0 | 0 | 0 (2 > 2) | 0b000 | |
| 3 | 1 | 0 | 0 | 1 (3 > 2) | 0b101 | |
| 4 | 1 | 1 | 1 | 1 (4 > 2) | 0b111 | win! |
| 5 | 0 | 2 | 1 | 1 (5 > 2) | 0b011 | |
| 6 | 1 | 2 | 1 | 1 (6 > 2) | 0b111 | |
| 7 | 1 | 3 | 1 | 1 (7 > 2) | 0b111 |
通常のラウンドロビンでは、3 ビット目の request が grant を得ますが、重みが 0 のため、優先度が下げられ、grant が与えられていません。その代わり、重みが 1 である 4 ビット目の request が grant を得ることになります。
実装例
実装例は https://github.com/taichi-ishitani/hdl-advent-calender-2022 に置いてあります。
-
max_finder.sv
- 「最大値を持つ位置を返す」回路
-
round_robin.sv
- 普通のラウンドロビン
-
prioritized_round_robin.sv
- 優先順位付きラウンドロビン
-
weighted_round_robin.sv
- 重み付きラウンドロビン
-
tb.sv
- テストベンチ
以下は、各ラウンドロビンの実行例です。
- round_robin.sv
- prioritized_round_robin
- weighted_round_robin
