高速ビットカウントを実装して学ぶSystemVerilog入門

## はじめに

SystemVerilogは、ハードウェア記述言語（HDL）の一つで、デジタル回路の設計や検証に広く使用されています。本記事では、SystemVerilogを用いて高速ビットカウント（ポピュレーションカウント）を実装する方法について解説します。ビットカウントは、バイナリデータ内の1のビット数を数える操作で、デジタル信号処理や暗号化、文字列検索など、様々な分野で重要な役割を果たしています。

## 高速ビットカウントの概要

高速ビットカウントは、効率的にバイナリデータ内の1のビット数を数える技術です。単純な実装では、各ビットを順番に確認して1の数を数えますが、これは大きなビット幅のデータに対しては非効率的です。そこで、並列処理や再帰的アプローチを用いることで、処理速度を大幅に向上させることができます。
主な高速ビットカウント手法には以下のようなものがあります：

- ルックアップテーブル法：事前に計算された結果を格納したテーブルを使用
- 並列加算法：複数のビットを同時に処理
- 分割統治法：データを再帰的に分割して処理


本記事では、分割統治法を用いたSystemVerilogの実装を紹介します。この方法は、ハードウェア実装に適しており、並列性を活かした高速な処理が可能です。

https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266

https://qiita.com/ozwk/items/90ddee5f4bb98ed3ea2d

https://www.nminoru.jp/~nminoru/programming/bitcount.html

https://www.slideshare.net/slideshow/ss-15916040/15916040

## SystemVerilogの開発環境(OSS)

オープンソースの開発ツールを使用することで、SystemVerilogの学習や開発を無料で始めることができます。ここでは、代表的な3つのツールについて詳しく説明し、インストール方法を紹介します。

### Icarus Verilog(iverilog)

https://steveicarus.github.io/iverilog/

`iverilog`は、Verilog HDLのシミュレータおよびコンパイラです。オープンソースで提供されており、Linux、macOS、Windowsなど、多くのプラットフォームで動作します。

主な特徴:
- IEEE 1364-2005 (Verilog-2005)、IEEE 1800-2012 (SystemVerilog-2012) をサポート
- コマンドラインベースの実行環境
- 多くのOSで動作

### Verible

https://chipsalliance.github.io/verible/

`verible` は、SystemVerilogのリント、フォーマットツールです。コードの品質を向上させ、可読性を高めるために使用されます。GoogleがオープンソースとしてリリースしたSystemVerilog向けのツールセットです。

主な特徴:
- リンター、フォーマッター、パーサーを提供
- コーディングルールに基づいたコードチェック
- コマンドラインツールとしても利用可能

### インストール方法

`iverilog`は、`OSS CAD Suite`をインストールすることで使用することができます。`OSS CAD Suite`は[公式GitHubレポジトリ](https://github.com/YosysHQ/oss-cad-suite-build)からビルド済みバイナリが配布されているので、ダウンロードしPATHを通すことで使用できます。

https://github.com/YosysHQ/oss-cad-suite-build

:::note
OSS CAD Suiteは、デジタル論理設計で使用される多くのオープンソースソフトウェアのバイナリソフトウェア配布です。Verilog、Migen、AmaranthなどのHDLをサポートし、RTL合成、フォーマルハードウェア検証、配置配線、FPGAプログラミング、テストのためのツールを見つけることができます。
:::

`verible`は[公式GitHubレポジトリ](https://github.com/chipsalliance/verible)からビルド済みバイナリが配布されているので、ダウンロードしPATHを通すことで使用できます。また、VSCodeの拡張機能である[Verilog-HDL/SystemVerilog/Bluespec SystemVerilog](https://marketplace.visualstudio.com/items?itemName=mshr-h.VerilogHDL)を使用することができます。

https://github.com/chipsalliance/verible

https://marketplace.visualstudio.com/items?itemName=mshr-h.VerilogHDL

![sample.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3665667/814ef2f9-b37a-87eb-ba99-61640287adee.gif)

### Dockerを使用した開発環境構築例

```Dockerfile : Dockerfile
FROM hdlc/verible

RUN apt update && apt install wget \
    && cd /opt/ \
    && wget https://github.com/YosysHQ/oss-cad-suite-build/releases/download/2024-06-21/oss-cad-suite-linux-x64-20240621.tgz \
    && tar -xzvf oss-cad-suite-linux-x64-20240621.tgz \
    && rm oss-cad-suite-linux-x64-20240621.tgz \
    && echo "source /opt/oss-cad-suite/environment" >> ~/.bashrc
```


## ビットカウント(population count)の実装

```verilog:popcnt.sv
module popcnt #(
    parameter int WIDTH = 64
) (
    input wire [WIDTH-1:0] i_data,
    output wire [$clog2(WIDTH+1)-1:0] o_count
);
  wire [$clog2((WIDTH >> 1) + 1)-1:0] left_count;
  wire [$clog2(WIDTH - (WIDTH >> 1) + 1)-1:0] right_count;
  generate
    if (WIDTH == 1) assign o_count = i_data;
    else begin : gen_count_tree
      assign o_count = left_count + right_count;
      popcnt #(
          .WIDTH(WIDTH >> 1)
      ) left_popcnt (
          .i_data (i_data[(WIDTH>>1)-1:0]),
          .o_count(left_count)
      );
      popcnt #(
          .WIDTH(WIDTH - (WIDTH >> 1))
      ) right_popcnt (
          .i_data (i_data[WIDTH-1:(WIDTH>>1)]),
          .o_count(right_count)
      );
    end
  endgenerate
endmodule
```

### 解説

再帰的な分割統治法を用いることで、効率的にビットカウントを計算しています。データを半分に分割し、それぞれの半分に対して再帰的にカウント（立っているビットの数を数える）を行うことで、並列性を活かした高速な処理を可能にします。

### モジュールの概要
- モジュール名は`popcnt`で、ジェネリックパラメータ`WIDTH`を持ちます。デフォルトでは`WIDTH`は64に設定しています。
- 入力ポート`i_data`は`WIDTH`ビットのビット列で、カウント対象のデータです。
- 出力ポート`o_count`は`$clog2(WIDTH+1)`ビットの幅を持ち、`i_data`内の1のビット数を表します。

### 実装の詳細

- `generate`ブロックを使用して、再帰的にモジュールをインスタンス化しています。
- `WIDTH`が1の場合、`o_count`は`i_data`と等しくなります。これは、1ビットの場合、そのビットが1であれば1、0であれば0となるためです。
- `WIDTH`が1より大きい場合、`gen_count_tree`ブロックが実行されます。
  - `i_data`を左右に分割し、それぞれ`left_popcnt`と`right_popcnt`のインスタンスに渡します。
  - `left_popcnt`は`i_data`の下位半分のビットを処理し、`right_popcnt`は上位半分のビットを処理します。
  - 再帰的に`popcnt`モジュールがインスタンス化され、分割されたデータに対してビットカウントが実行されます。
  - 最終的に、`left_count`と`right_count`の合計が`o_count`として出力されます。

## テスト

```verilog:test_popcnt.sv
`include "popcnt.sv"

module test_popcnt;
  localparam int BitWidth = 5;
  reg [BitWidth-1:0] data;
  reg [$clog2(BitWidth+1)-1:0] count;
  popcnt #(
      .WIDTH(BitWidth)
  ) _popcnt (
      .i_data (data),
      .o_count(count)
  );
  initial begin
    for (int i = 0; i < (1<<BitWidth); ++i) begin
      data = i;
      #10 $display("%b, %d", data, count);
    end
  end
endmodule
```

このテストコードでは、さきの`popcnt`モジュールの機能を検証するします。テストベンチモジュール`test_popcnt`を定義し、様々な入力パターンに対して`popcnt`モジュールの出力を確認しています。

### テストベンチの概要
- `BitWidth`というローカルパラメータを定義し、テストするビット幅を指定しています。ここでは`BitWidth`は5に設定しています。
- `data`レジスタは`BitWidth`ビット幅を持ち、`popcnt`モジュールへの入力データを表します。
- `count`レジスタは`$clog2(BitWidth+1)`ビット幅を持ち、`popcnt`モジュールの出力結果を格納します。
- `popcnt`モジュールをインスタンス化し、`BitWidth`をパラメータとして渡しています。`data`を入力ポートに、`count`を出力ポートに接続しています。

### テストの実行
- `initial`ブロック内で、`for`ループを使用して`0`から`2^BitWidth-1`までの全ての値を`data`に順番に代入しています。
- 各ループの反復で、`data`の値を変更した後、`#10`のディレイを挿入しています。これにより、`popcnt`モジュールの出力が安定するまで待ちます。
- `$display`タスクを使用して、現在の`data`の値と、対応する`count`の値を表示します。`%b`は`data`をバイナリ形式で、`%d`は`count`を10進数形式で表示します。

このテストコードを実行すると、`BitWidth`で指定されたビット幅（この例では5ビット）の全ての可能な入力パターンに対して、`popcnt`モジュールの出力が正しいかどうかを確認することができます。テスト結果は、各入力パターンとそれに対応するポピュレーションカウントの値として表示されます。

例えば、出力結果の一部は以下のようになります：
```
00000, 0
00001, 1
00010, 1
00011, 2
...
11110, 4
11111, 5
```

## 実際に実行！

```shell
iverilog -g 2012 -o test_popcnt test_popcnt.sv
vvp test_popcnt
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3665667/db1a2411-8d0f-9fcf-91a1-3c65dd759bad.png)

## おわりに

この記事では、SystemVerilogを使用して高速ビットカウントを実装する方法を学びました。再帰的な分割によるアルゴリズムを用いることで、ハードウェアでの並列処理を活用し、効率的なビットカウントを実現できます。
また、オープンソースのSystemVerilog開発ツールについても紹介しました。Icarus Verilog、Veribleを使用することで、無料で学習や開発を始めることができます。