高速ビットカウントを実装して学ぶSystemVerilog入門 #アルゴリズム

はじめに

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

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

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

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

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

SystemVerilogの開発環境(OSS)

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

Icarus Verilog(iverilog)

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

主な特徴:

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

Verible

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

主な特徴:

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

インストール方法

iverilogは、OSS CAD Suiteをインストールすることで使用することができます。OSS CAD Suiteは公式GitHubレポジトリからビルド済みバイナリが配布されているので、ダウンロードしPATHを通すことで使用できます。

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

veribleは公式GitHubレポジトリからビルド済みバイナリが配布されているので、ダウンロードしPATHを通すことで使用できます。また、VSCodeの拡張機能であるVerilog-HDL/SystemVerilog/Bluespec SystemVerilogを使用することができます。

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

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)の実装

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として出力されます。

テスト

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モジュールの出力が正しいかどうかを確認することができます。テスト結果は、各入力パターンとそれに対応するポピュレーションカウントの値として表示されます。

例えば、出力結果の一部は以下のようになります：

実際に実行！

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

おわりに

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