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

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

石谷@[PEZY Computing](https://www.pezy.co.jp)です。[HDL Advent Calender 2022](https://qiita.com/advent-calendar/2022/hdl) の3日目ということで、今年は趣向を変えて、ラウンドロビンについて書いていきたいと思います。

## はじめに

ラウンドロビンはよく使う調停回路で、バスの MUX などでよく出てくるかと思います。安直に実装するなら、以下の様な実装になるかと思います。

```verilog
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](https://link.springer.com/book/10.1007/978-1-4614-4301-8) に面白い実装方法が載っていたので、まずはその実装方法を紹介します。次に、優先順位付きラウンドロビンなど、変種のラウンドロビンを、この方法を応用して実装していきたいと思います。

## 基本の回路

上記の書籍で紹介されている方法では、入力リクエストを走査する代わりに、「ある数列を入力し、最大値を持つ位置を返す」回路を使って、ラウンドロビンを実装しています。以下が、その安直な実装になります。

```verilog
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](https://github.com/taichi-ishitani/hdl-advent-calender-2022/blob/master/max_finder.sv)
    * 「最大値を持つ位置を返す」回路
* [round_robin.sv](https://github.com/taichi-ishitani/hdl-advent-calender-2022/blob/master/round_robin.sv)
    * 普通のラウンドロビン
* [prioritized_round_robin.sv](https://github.com/taichi-ishitani/hdl-advent-calender-2022/blob/master/prioritized_round_robin.sv)
    * 優先順位付きラウンドロビン
* [weighted_round_robin.sv](https://github.com/taichi-ishitani/hdl-advent-calender-2022/blob/master/weighted_round_robin.sv)
    * 重み付きラウンドロビン 
* [tb.sv](https://github.com/taichi-ishitani/hdl-advent-calender-2022/blob/master/tb.sv)
    * テストベンチ

以下は、各ラウンドロビンの実行例です。

* round_robin.sv![round_robin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/6a491426-417b-42d3-fa75-5a81cc09f6c5.png)
* prioritized_round_robin![prioritized_round_robin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/835d7faf-b2d3-7f0d-1d4f-63ae9ada5c2a.png)
* weighted_round_robin![weighed_round_robin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/7e7dc96d-a5f9-25ac-b8d9-2588d1214ab6.png)