search
LoginSignup
0

posted at

updated at

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

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

石谷@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 に置いてあります。

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

  • round_robin.svround_robin.png
  • prioritized_round_robinprioritized_round_robin.png
  • weighted_round_robinweighed_round_robin.png

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0