verilogで再帰する

verilogで再帰？

この記事はtask文やfunction文の再帰呼び出しに関連する記事では無く，再帰的構造の回路の実装方法を紹介する記事です．
ちなみに，task文やfunction文はatomaticを付加することで再帰呼び出しが可能です．

verilogでは再帰的なモジュールのインスタンス化はできませんが，generateブロック内に限り，再帰的にモジュールをインスタンス化することが可能です．
generate文はverilog2001から導入された構文で，下位モジュールや回路の定義をパラメタライズし，抽象化することができます．
verilogの再帰モジュールの実装方法に関してはRecursive and Iterative designs in VerilogやRecursive Modulesなどの記事でも紹介されています．

何がすごいの？

• ツリー構造の演算回路を簡潔に記述できる
  ツリーなどの再帰的な構造の回路を簡潔に表現できます．
  マルチプレクサや総和計算回路など多くの回路はツリー構造で表すことができるため，幅広い回路で活用できます．

• パラメタライズしやすい
  モジュールを呼び出す度にモジュールのパラメータを再設定することができるため，モジュールのパラメータの調整が簡単に行えます．

再帰モジュールの実装

ここではツリー構造の最大値計算回路を例に再帰モジュールの実装方法を紹介しようと思います．
それでは早速，実装コードを見てみましょう．

module Max #
(
    parameter WIDTH = 8, // データのビット幅
    parameter SIZE  = 8  // データの個数(1, 2, 4, 8, ...)
)
(
    input  wire [SIZE*WIDTH-1:0] idata, // 入力データ
    output wire      [WIDTH-1:0] odata  // 出力データ
);

    wire [WIDTH-1:0] data0;
    wire [WIDTH-1:0] data1;

    generate
        // 基底部
        if (SIZE == 1)
        
            // 入力データをそのまま出力する
            assign odata = idata;

        // 帰納部
        else begin
        
            // 最大値の計算
            assign odata = ($signed(data0) > $signed(data1)) ? data0 : data1;

            // 再帰呼び出し
            Max # 
            (
                .WIDTH(WIDTH),   // データのビット幅はそのまま
                .SIZE(SIZE >> 1) // データの個数を半分にする
            )
            max0
            (
                .idata(idata[(SIZE>>1)*WIDTH-1:0]), // 入力データの前半分を下位モジュールに入力
                .odata(data0)
            );
            
            // 再帰呼び出し
            Max # 
            (
                .WIDTH(WIDTH),   // データのビット幅はそのまま
                .SIZE(SIZE >> 1) // データの個数を半分にする
            )
            max1
            (
                .idata(idata[SIZE*WIDTH-1:(SIZE>>1)*WIDTH]), // 入力データの後半分を下位モジュールに入力
                .odata(data1)
            );
        end
    endgenerate

endmodule

上記のコードは下図のような回路になります．

この回路では，入力データを2つに分割し，半分サイズの下位モジュールにそれぞれのデータを入力しています．
そして，下位モジュールからの出力データを比較し，その結果を出力します．

モジュール本体は大きく，基底部，帰納部に分かれており，SIZEパラメータによっていずれかの回路が選択されます．

• 基底部(SIZE = 1)
  入力データは1つなので，受け取ったデータをそのまま出力する．
• 帰納部(SIZE = 2, 4, 8, ...)
  入力データを2つに分割し，2つの下位モジュールにそれぞれ入力する．

下位モジュールのインスタンス化をするときには下位モジュールのパラメータを再設定することが可能です．
例えば，加算回路のツリーを作成するときには加算で生じる桁上がりを考慮して下位モジュールの入力ビット幅を調整することで，効率的に加算回路のツリーを構築することもできます．

また，今回作成した最大値の計算回路はデータの個数が２のべき乗であるときにしか正しく動作しませんが，帰納部で正しく処理することで任意のサイズのデータに対応させることができます．

簡単ですね！

assign odata = ($signed(data0) > $signed(data1)) ? data0 : data1;

の部分を変更することで様々な計算回路を再帰させることができます．

例えば，

assign odata = $signed(data0) + $signed(data1)

とすると総和の計算回路になり，

assign odata = $signed(data0) * $signed(data1)

とすると総乗の計算回路になります．

注意点

残念ながら全ての合成ツールやシミュレーターで再帰的なモジュールの実装がサポートされているわけではなく，環境によっては正常に動作しない可能性があります．
※Xilinx社の合成ツールであるVivadoやPlanAheadではシミュレーションや合成が可能です．

上記の回路ではSIZEを$n$とすると$\log(n)$に比例して信号の遅延が増加し，$n$に比例して使用リソース数が増加します．
大規模な回路を実装すると回路のパフォーマンスが悪化する可能性があるのでご注意ください．