複数サイクルの unsigned シフト加算乗算器

前提知識：順序回路、ノンブロッキング^{iノンブロッキング代入 順序 RTL で <= と書く代入です。右辺を評価して更新を予約するので、同じエッジのレジスタが更新前の状態に基づいて計算できます。 詳しく見る}代入、カウンタ、シフト、加算器を理解していること。

一つの加算器を複数クロックで再利用する

unsigned^{iunsigned ビット列を非負整数として解釈する規則です。n ビットの範囲は 0 から 2^n−1 で、同じビット列の signed 解釈と異なる場合があります。 詳しく見る} W ビット乗算は、乗数 B の各ビットが選ぶ部分積の和です。

すべての部分積を一度に加えると、多くの加算論理が必要です。ここでは一つの加算器を W 回使い、面積とスループットのトレードオフを取ります。RTL にループを書くだけで複数サイクル回路になるわけではなく、クロック間に計算状態を保つレジスタ^{iレジスタ 複数ビットの状態を記憶する回路です。このコースの同期式レジスタは、クロックエッジで定められた入力を記憶します。 詳しく見る}と終了条件が必要です。

累算器 P は 2W ビット、移動する被乗数 M も 2W ビット、右へ動く乗数 Q は W ビットです。開始時は P=0、M=zero-extend(A)、Q=B とします。各計算クロックで Q[0]=1 なら M を P に加え、M を一桁左、Q を一桁右へ動かします。

W 回後に Q=0、P は完全な積です。最大値 $(2^W-1)^2$ が $2^{2W}$ 未満で、unsigned 部分積の中間和も最終積を超えないため、2W ビットで十分です。

A=13,B=11,W=4 なら Q の下位ビットは 1,1,0,1 の順です。P は 0→13→39→39→143、使う M は 13→26→52→104 です。Q[0]=0 の三回目も、移動とカウンタ増加は必須です。

下の各列は要求取込みまたは計算エッジ直後の状態です。最初は初期化、続く四列が計算です。三回目は旧 Q[0]=0 なので P だけ保持し、M・Q は移動します。

要求と完了の時点を先に決める

このインターフェースは idle で start=1 の立上りエッジ^{i立上りエッジ クロックが 0 から 1 に変わる瞬間です。CLK=1 の区間全体を指すレベルとは区別します。 詳しく見る}を要求受付とします。その t0 は入力を保存するだけで、t1～tW の W 回で計算し、tW 直後に product と done が有効になります。受付から完了は W 周期ですが、受付エッジを含めて数えると W+1 エッジです。

busy=1 の間は start を無視します。完了エッジも直前の busy=1 のため新要求を受けません。最速の次受付は tW+1 で、連続要求の最小受付間隔は W+1 周期です。start を 1 に保つと idle に戻った次のエッジで再開します。呼出し側は通常、受付に合わせたパルスを与えます。

module mul_iter #(parameter int W = 8) (
  input  logic clk, rst, start,
  input  logic [W-1:0] a, b,
  output logic busy, done,
  output logic [2*W-1:0] product
);
  localparam int CW = (W <= 1) ? 1 : $clog2(W);
  localparam logic [CW-1:0] LAST = CW'(W-1);
  logic [CW-1:0] step;
  logic [2*W-1:0] acc, m, next_acc;
  logic [W-1:0] q;

  assign next_acc = acc + (q[0] ? m : {2*W{1'b0}});

  always_ff @(posedge clk) begin
    if (rst) begin
      busy <= 1'b0;
      done <= 1'b0;
      product <= '0;
      acc <= '0;
      m <= '0;
      q <= '0;
      step <= '0;
    end else begin
      done <= 1'b0;
      if (!busy) begin
        if (start) begin
          busy <= 1'b1;
          acc <= '0;
          m <= {{W{1'b0}}, a};
          q <= b;
          step <= '0;
        end
      end else begin
        acc <= next_acc;
        m <= m << 1;
        q <= q >> 1;
        if (step == LAST) begin
          product <= next_acc;
          busy <= 1'b0;
          done <= 1'b1;
        end else begin
          step <= step + 1'b1;
        end
      end
    end
  end
endmodule

W≥1 を前提にし、W=1 でも 0 ビットカウンタにならないよう CW を最小 1 にします。reset は同期式 active-high で実行中の演算より優先されます。受付後に外部 a,b が変わっても、保存した m,q で計算するので影響しません。product が変わるのは reset または完了時だけです。done は一周期パルスであり、消費まで保持する valid ではありません。

最後は product<=acc ではなく product<=next_acc です。nonblocking の右辺は更新前の値を読むため、acc を出すと最後の乗数ビットの部分積が抜けます。同様に q のシフト代入を先に書いても、next_acc は現在の Q[0] から計算します。

計算の不変条件と実設計の選択

k 回の計算直後、次の関係を保ちます。

Q を偶数部分と最下位ビットに分けると、次段でも関係が保たれることを示せます。k=W では Q=0 なので P=AB です。この不変条件^{i不変条件 許可されたすべての実行で、常に真でなければならない条件です。例えば深さ 4 の FIFO の格納数は常に 0 以上 4 以下です。 詳しく見る}は、小例の波形だけよりも、累算と移動の順番が正しい理由を明確にします。

一回の計算のクリティカルパスには 2W ビット加算器と入力選択があります。乗算記号をなくしても、必ず小さく速くなるわけではありません。FPGA 専用 DSP、合成結果、必要スループット^{iスループット 単位時間に受け入れる、または完了する処理の数です。パイプラインは個々の処理の遅延を短くしなくても、スループットを高められます。 詳しく見る}を比較します。このモジュールは early-exit・signed 処理・結果のバックプレッシャーを実装しません。受け手が done を逃さない取り決めが必要です。

検証には 0・1・最大値・最上位ビットだけ 1 の B を含め、busy 中の start と入力変更、reset による取消しも確認します。最上位だけ 1 の B は、最後の累算漏れを特に示します。