いろいろなラウンドロビンを実装する！

石谷@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