再利用可能な MUX を作る

## はじめに

MUX はよく使う記述です。選択肢の個数が固定値なら、`if` 文なり `case` 文なりで記述可能です。再利用可能なように、選択肢の個数を parameter で指定できるようにするには、ひと工夫が必要です。本稿ではその方法をまとめます。

今回作成する MUX モジュールの仕様は以下の通りです。

* Parameter
    * `N`
        * 選択肢の個数
    * `W`
        * データの幅
* 入出力ポート
    * `i_select`
        * 入力
        * 幅: $clog2(N) または N
        * 選択信号
   * `i_data`
       * 入力
       * 幅: W
       * 配列の大きさ: N
       * 入力データ
   * `o_data`
       * 出力
       * 幅: W
       * 出力データ

## 通常の MUX の場合

選択信号がデコード前のインデックスとして与えられる、通常の MUX の場合です。以下の様に、`i_select` で `i_data` の選択を行うだけです。

```verilog:normal_mux.sv
module normal_mux #(
  parameter   int N             = 8,
  parameter   int W             = 8,
  localparam  int SELECT_WIDTH  = $clog2(N)
)(
  input   var [SELECT_WIDTH-1:0]  i_select,
  input   var [N-1:0][W-1:0]      i_data,
  output  var [W-1:0]             o_data
);
  always_comb begin
    o_data  = i_data[i_select];
  end
endmodule
```

想定通りに MUX が推論されます。

![normal_mux.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/ef9423f1-57e8-4d11-8b65-f791854114d2.png)

## 優先度付 MUX (安直な実装編)

選択信号が何かしらの方法でデコード済みで、複数の選択信号が立つ場合がある MUX です。`for` 文で走査し、`i_select[i]` が立ったところで `break` を掛ければ、安直ですが実装できます。

```verilog:priority_mux_naive.sv
module priority_mux_naive #(
  parameter   int N = 8,
  parameter   int W = 8
)(
  input   var [N-1:0]         i_select,
  input   var [N-1:0][W-1:0]  i_data,
  output  var [W-1:0]         o_data
);
  function automatic logic [W-1:0] __mux(
    logic [N-1:0]         select,
    logic [N-1:0][W-1:0]  data
  );
    logic [W-1:0] result;

    result  = data[N-1];
    for (int i = 0;i < (N - 1);++i) begin
      if (select[i]) begin
        result  = data[i];
        break;
      end
    end

    return result;
  endfunction

  always_comb begin
    o_data  = __mux(i_select, i_data);
  end
endmodule
```

ただし、この場合、２入力 MUX が多段に接続された構成になってしまします。選択肢の個数が多いと、遅延が大きくなって、クロック周波数を上げることが難しくなります。

![priority_mux_naive.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/86056082-2658-017e-5254-e24bb2459d38.png)

## 優先度付 MUX (遅延低減実装編)

多重に接続されている MUX を、ツリー上に接続することで、遅延の低減を図ることができます。選択肢の個数が固定値なら、`if` 文に展開するなどして実現することができます。

![priority_mux_fix.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/f2ec24d5-ecf3-853c-24d0-5cc84e5aa360.png)

再帰的な構造になっているので、`function` の再帰呼び出しで表現可能です。これを用いれば、選択肢の個数をパラメータ化した状態で、MUX の接続をツリー上に展開することができます。

```verilog:priority_mux.sv
module priority_mux #(
  parameter   int N = 16,
  parameter   int W = 8
)(
  input   var [N-1:0]         i_select,
  input   var [N-1:0][W-1:0]  i_data,
  output  var [W-1:0]         o_data
);
  function automatic [(1+W)-1:0] __mux(
    int                   n,
    int                   position,
    logic [N-1:0]         select,
    logic [N-1:0][W-1:0]  data
  );
    if (n > 4) begin
      int                     next_n;
      int                     next_position;
      logic [1:0][(1+W)-1:0]  result;

      next_n        = n / 2;
      next_position = position;
      result[0]     = __mux(next_n, next_position, select, data);

      next_n        = (n / 2) + (n % 2);
      next_position = (n / 2) + position;
      result[1]     = __mux(next_n, next_position, select, data);

      return (result[0][W]) ? result[0] : result[1];
    end
    else if (n == 4) begin
      case (1'b1)
        select[position+0]: return {select[position+0], data[position+0]};
        select[position+1]: return {select[position+1], data[position+1]};
        select[position+2]: return {select[position+2], data[position+2]};
        default:            return {select[position+3], data[position+3]};
      endcase
    end
    else if (n == 3) begin
      case (1'b1)
        select[position+0]: return {select[position+0], data[position+0]};
        select[position+1]: return {select[position+1], data[position+1]};
        default:            return {select[position+2], data[position+2]};
      endcase
    end
    else if (n == 2) begin
      case (1'b1)
        select[position+0]: return {select[position+0], data[position+0]};
        default:            return {select[position+1], data[position+1]};
      endcase
    end
    else begin
      return {select[position+0], data[position+0]};
    end
  endfunction

  logic __dummy;

  always_comb begin
    {__dummy, o_data} = __mux(N, 0, i_select, i_data);
  end
endmodule
```

以下がエラボレーション結果です。MUX がきれいにツリー上に展開されていることがわかります。

![priority_mux.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/8aeceba5-897a-1e49-1c63-3611c68b85b1.png)

## Onehot MUX

選択信号が一か所しか立たない、優先度付 MUX です。１つ入力データしか有効にならないので、`i_data` と `i_select` の AND-OR 構成とすることで実装できます。また、OR の個所もツリー上に展開可能で、上記の `function` の再帰呼び出しを利用可能です。

```verilog:onehot_mux.sv
module onehot_mux #(
  parameter   int N = 16,
  parameter   int W = 8
)(
  input   var [N-1:0]         i_select,
  input   var [N-1:0][W-1:0]  i_data,
  output  var [W-1:0]         o_data
);
  function automatic [W-1:0] __reduce_or(
    int                   n,
    int                   position,
    logic [N-1:0][W-1:0]  data
  );
    if (n > 4) begin
      int                 next_n;
      int                 next_position;
      logic [1:0][W-1:0]  result;

      next_n        = n / 2;
      next_position = position;
      result[0]     = __reduce_or(next_n, next_position, data);

      next_n        = (n / 2) + (n % 2);
      next_position = (n / 2) + position;
      result[1]     = __reduce_or(next_n, next_position, data);

      return result[0] | result[1];
    end
    else if (n == 4) begin
      return
        (data[position+0] | data[position+1]) |
        (data[position+2] | data[position+3]);
    end
    else if (n == 3) begin
      return
        data[position+0] | data[position+1] |
        data[position+2];
    end
    else if (n == 2) begin
      return
        data[position+0] | data[position+1];
    end
    else begin
      return
        data[position+0];
    end
  endfunction

  function automatic [(1+W)-1:0] __mux(
    logic [N-1:0]         select,
    logic [N-1:0][W-1:0]  data
  );
    logic [N-1:0][W-1:0]  masked_data;

    for (int i = 0;i < N;++i) begin
      masked_data[i]  = {W{select[i]}} & data[i];
    end

    return __reduce_or(N, 0, masked_data);
  endfunction

  always_comb begin
    o_data  = __mux(i_select, i_data);
  end
endmodule
```

こちらも、OR の個所がきれいにツリー上に展開されることがわかります。

![onehot_mux.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144465/f3985380-6d86-a846-cbec-6344c57a635d.png)

## EDA ツールの対応状況

以下の EDA ツールで論理合成できることを確認しました。

* Synopsys Design Comppiler
* Xilinx Vivado
    * 図の作成に使用しました

@morilab さんに、他の EDA ツールの対応状況を調べていただけました。ありがとうございます。
以下の EDA ツールでも上記の MUX の実装を使うことができます。

* SynplifyPro
* Lattice Radiant

なお、Quartus 君はと言うと。

```
Error (10210): Verilog HDL unsupported feature error at priority_mux.sv(9): recursive Function Call in Function Declaration is not supported
```