🙆‍♀️

Verilator5で簡単な(剰余)乗算器をシミュレーション

2023/05/25に公開

簡単な乗算器シミュレーション

前回の記事で、これまで作っていた大規模な乗算器シミュレーションに失敗したので、今回は簡単な乗算器を作ってシミュレーションしてみる。

ソースコード
tb_mult.sv
`timescale 1ns / 1ps


module tb_mult;
    localparam 
        CYCLE = 10,
        DELAY = 2,
        N_LOOP = 10000,
		N_MUL_LEN = 256,
		N_PIPELINE_STAGES = 2;
               
    reg clk, rstn;
    logic [N_MUL_LEN - 1:0] X, Y, Z, ans;
	logic [N_PIPELINE_STAGES - 1:0][N_MUL_LEN - 1:0] reg_ans;

	int unsigned _urandom;
	assign ans = X*Y;

    mult #(N_MUL_LEN) DUT(.clk, .rstn, .X, .Y, .Z);
    
    always begin
        #(CYCLE/2) clk <= ~clk;
    end

	always @(posedge clk) begin
		reg_ans <= {reg_ans[N_PIPELINE_STAGES - 2:0], ans};
	end
    
    /*-------------------------------------------
    Test
    -------------------------------------------*/
    initial begin
		_urandom = $urandom(1);
        rstn = 1'b1;
        clk = 1'b1;
    #(CYCLE*10)
        rstn = 1'b0;
    #(CYCLE*10)
        rstn = 1'b1;
    #DELAY;
        $display("Test start\n");

        for(integer i = 0; i < N_LOOP; i = i + 1) begin
            X = urand_n();
            Y = urand_n();
            
            #DELAY
            $display("%d: x = %h, y = %h, z = %h, ans = %h", i, X, Y, Z, ans);
            if(Z !== reg_ans[N_PIPELINE_STAGES - 1]) begin
                $display("Failed: ans = %h", ans);
                $stop();
            end
            #(CYCLE-DELAY);
        end
        $display("#%d Test end\n", N_LOOP);
        $finish;
    end

	function static [N_MUL_LEN - 1:0] urand_n;
		logic [(N_MUL_LEN/32 + 1)*32 - 1: 0] temp_var = '0;
		repeat(N_MUL_LEN/32 + 1)
			temp_var = {temp_var[$bits(temp_var)-32-1:0], $urandom};
		urand_n = (N_MUL_LEN)'(temp_var);
	endfunction

endmodule
mult.sv
`timescale 1ns / 1ps

module mult #(
	parameter N_MUL_LEN = 4
	)(
	input clk, rstn,
	input [N_MUL_LEN - 1:0] X, Y,
	output logic [N_MUL_LEN - 1:0] Z
	);

	logic [N_MUL_LEN - 1:0] ZZ;
	always_ff @(posedge clk) begin
		if (!rstn) 
			Z <= 0;
		else begin
			ZZ <= X*Y;
			Z <= ZZ;
		end
	end

endmodule // mult

ソースコードは上のような感じで、N_MUL_LENビットの乗算を2サイクルかけて行うmultモジュールに対して$urandomで乱数を入力し、期待する出力ansと比較している。
何のことはない単純なテストベンチだが、タイミング記述が動くのかとかurandomが動くのかとか、何ビットまで乗算できるのかとか、いろいろ気になる。

ビルド

verilator --binary tb_mult.sv

トップモジュールを選択して、--binaryをつけるだけ。

実行結果

...
      99997: x = ff6ef8f39d25f63a5cbe122b825b86ebf294f41349933aee56908c118e1ff74f, y = 226f71a9ad41b34d1cb412109b907a3676e1c60dc8e8493fed506a2672bd9304, z = 0e9a050d008bf1dd784a18c79fcf15814a96139de384d0e82d79676501d5de8b, ans = 0598a3e092eb74e926173a1c55c086ddf226fc97fe25835c55c5da5756d53a3c
      99998: x = d591e9ace24eaf09ab970d8e067703aba3a8984793db8e5267585fc73d88e0fe, y = 54a339bac77d803288d3000e2c40545f3e1407013cf0ae268def649a034ada82, z = be64622ae3c7ede0e7b271a248d4437d1010bb73a73e5ea33e2e40a16a4576dc, ans = 8f12ec5c9a52a2400dbcbdfeba9d30e67931ca09a190acd3311d4293d2868cfc
      99999: x = 8d8217d4f561fd7665c0edce8287d74d0c00d4fb5754612bb2b3d2800849e6e1, y = 58192057ff8b177784dde1068805db8a65e20fc1d7a5e91bd477a460933c2fc0, z = 0598a3e092eb74e926173a1c55c086ddf226fc97fe25835c55c5da5756d53a3c, ans = e8e6d02536271a22decdb75664cc19f271e29a19da983033ff7d7ad1188c77c0
#     100000 Test end

- tb_mult.sv:56: Verilog $finish

256ビット乗算器で、10万件テストしても1秒くらいで終わるので、早いんだろう。
1024ビットにして100万件テストしても30秒くらいで終わった。($displayなし)
ということでこれくらいのコード動作に問題なさそう。verilogで書いたテストベンチが動くのですごいことなんだろう。
ただ--traceオプションをつけても波形ファイルは出力されなかった。まだサポートされてない?デバッグには使えないかなあ。$displayでprintfデバッグみたいなことはできるかな。

簡単な剰余乗算器シミュレーション

続いて、もうちょっと難しい対象として2^k-基数モンゴメリ乗算器をテストする。

ソースコード
montmul.sv
`timescale 1ns / 1ps

module montmul (
	input clk, rstn,
	input fp_t A, B,
	output fp_t S
	);

	logic [n-1:0][k*(n+1)-1:0] biAS, qiM;
	logic [n-1:0][k-1:0] qi;

	fp_t [n-1:0] reg_A, reg_B;
	fp_t [n:0] reg_S;

	always_ff @(posedge clk) begin : shift_reg_AB
		if (!rstn) begin
			reg_A <= '0;
			reg_B <= '0;
		end
		else begin
			reg_A <= {reg_A[n-2:0], A};
			reg_B <= {reg_B[n-2:0], B};
		end
	end

	assign S = reg_S[n];
	generate
		for (genvar i = 0; i < n; i = i + 1) begin : gen_reg_S
			assign biAS[i] = reg_A[i] * reg_B[i][i] + reg_S[i];
			assign qi[i] = k'(k'(biAS[i]) * Mp);
			assign qiM[i] = qi[i] * M;
			always_ff @(posedge clk) begin
				if (!rstn) 
					reg_S[i] <= '0;
				else begin
					reg_S[i+1] <= ((biAS[i] + qiM[i]) >> k);
				end
			end
		end
	endgenerate
endmodule // montmul
tb_montmul.sv
`timescale 1ns / 1ps

localparam 
	M = 256'h2523648240000001ba344d80000000086121000000000013a700000000000013, //The BN254 prime
	k = 32,
	n = 8,
	R = 256'h212ba4f27ffffff5a2c62effffffffcdb939ffffffffff8a15ffffffffffff8e, // 2**256 mod M
	R2 = 256'h1b0a32fdf6403a3d281e3a1b7f86954f55efbf6e8c1cc3f1b3e886745370473d, // R**2 mod M
	R_inv = 256'h1a7344bac91f117ea513ec0ed5682406b6c15140174d61b28b762ae9cf6d3b46, // R**-1
	Mp = 32'hd79435e5;

typedef logic[n-1:0][k-1:0] fp_t;

module tb_montmul;
    localparam 
        CYCLE = 10,
        DELAY = 2,
        N_LOOP = 1000000,
		N_PIPELINE_STAGES = n+1;
               
    reg clk, rstn;
    fp_t X, Y, Z, ans, x, y, z;
	fp_t [1:0] xy;
	fp_t [N_PIPELINE_STAGES - 1:0] reg_ans;

	int unsigned _urandom;
	assign z = MR(Z, 1);
	assign xy = x*y;
	assign ans = xy % M;

    montmul DUT(.clk, .rstn, .A(X), .B(Y), .S(Z));
    
    always begin
        #(CYCLE/2) clk <= ~clk;
    end

	always @(posedge clk) begin
		reg_ans <= {reg_ans[N_PIPELINE_STAGES - 2:0], ans};
	end
    
    /*-------------------------------------------
    Test
    -------------------------------------------*/
    initial begin
		_urandom = $urandom(1);
        rstn = 1'b1;
        clk = 1'b1;
    #(CYCLE*10)
        rstn = 1'b0;
    #(CYCLE*10)
        rstn = 1'b1;
    #DELAY;
        $display("Test start\n");

        for(integer i = 0; i < N_LOOP; i = i + 1) begin
            x = urand_n();
            y = urand_n();
			X = MR(x, R2);
			Y = MR(y, R2);
            
            #DELAY
            //$display("%d: x = %h, y = %h, z = %h, ans = %h", i, x, y, z, ans);
            if(z !== reg_ans[N_PIPELINE_STAGES - 1]) begin
                $display("Failed: ans = %h", ans);
                $stop();
            end
            #(CYCLE-DELAY);
        end
        $display("#%d Test end\n", N_LOOP);
        $finish;
    end

	function static fp_t urand_n;
		logic [($bits(fp_t)/32 + 1)*32 - 1: 0] temp_var = '0;
		repeat($bits(fp_t)/32 + 1)
			temp_var = {temp_var[$bits(temp_var)-32-1:0], $urandom};
		urand_n = ($bits(fp_t))'(temp_var);
	endfunction

	function static fp_t MR;
		input fp_t A, B;

		fp_t [1:0] tmp_AB, tmp_ABRi;
		fp_t tmp_ABmodM;

		assign tmp_AB = A*B;
		assign tmp_ABmodM = tmp_AB % M;
		assign tmp_ABRi = tmp_ABmodM * R_inv;
		MR = tmp_ABRi % M;
	endfunction

endmodule

http://www.acsel-lab.com/arithmetic/arith12/papers/ARITH12_Orup.pdf
のアルゴリズム1をパイプライン実装(for1段に対してパイプライン1段)している。

雑な回路図は

こんな感じ。

ビルド

verilator --binary tb_montmul.sv -Wno-lint

演算子のビット幅が異なるというwarningが出るが無視する。

一応テスト通るまでにすることができたが、ハマリポイントをいかに記す。
ちなみにこれくらいの規模であれば波形ファイルなくても$displayでデバッグできた。しかしpacked arrayとかは全部シリアルに出力されるので見にくい。

1ファイルに1モジュール

実装し始めのころは、横着してmontmulモジュールをmult.svに書いていた。
この場合

%Error: tb_montmul.sv:31:13: Can't resolve module reference: 'montmul'
   31 |     montmul DUT(.clk, .rstn, .A(X), .B(Y), .S(Z));
      |             ^~~

みたいに、モジュールが見つからないといわれる。従って1ファイルに1モジュールが基本となり、かつモジュール名とファイル名を合わせる必要があるっぽい。こういうのが推奨されると聞いたことはあったけど、実際やるとファイル増えすぎんか?と思う。

乗算後のビット幅

fp_t X, Y, Z, ans, x, y, z;
fp_t [1:0] xy;

assign xy = x*y;
assign ans = xy % M;

の部分で、テストベクタx, yに対する答えansを計算しているが、ここでassign ans = x*y %Mのように1行で書いてしまうと上手くいかない。どうも計算は結果のビット幅分しかやってくれないようなので、x*yのところで2倍のビット幅を持つ変数を一回経由させる必要がある。
これはxsimの時もそうだったし、なんとなくわかる挙動ではある。

剰余演算子

剰余演算子%の挙動はよくわからない。
MR関数で256*256*256ビットを256ビットで剰余する部分があるのだが、

fp_t [2:0] tmp_ABRi;

assign tmp_ABRi = A*B*R_inv;
MR = tmp_ABRi % M;

のように、3倍の長さの変数tmp_ABRiを経由して剰余をとると、Floating point exceptionでダメだった。%の右辺の値を変えてみると*** stack smashing detected ***: <unknown> terminatedが出たり、上手くいったりするので、この辺の挙動はよくわからない。
最終的には2倍長の変数を2回経由することでうまくいった。

大きな数の剰余演算子使うのは暗号演算くらいだから、サポートも適当なのかな?
剰余演算子を使うときはDPI-Cとかで別にテストベクタ作った方がいいのだろう。

Discussion