A Multicycle Unsigned Shift-Add Multiplier

선수 지식: 순차회로, nonblocking 대입, 카운터, 시프트와 가산기를 이해해야 합니다.

하나의 가산기를 여러 클록에서 재사용하기

unsigned W비트 곱셈은 승수 B의 각 비트가 선택하는 부분곱의 합입니다.

모든 부분곱을 동시에 더하면 많은 가산 논리가 필요합니다. 이번에는 가산기 하나를 W번 사용합니다. 이는 면적과 처리량을 교환하는 구조이며, RTL에 반복문을 썼다고 저절로 다중 사이클 회로가 만들어지는 것은 아닙니다. 클록 사이에 계산 상태를 저장할 레지스터와 종료 조건이 필요합니다.

누산기 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가 완전한 곱입니다. 2W비트는 충분합니다. 최댓값 $(2^W-1)^2$가 $2^{2W}$보다 작고, unsigned 부분곱을 더하는 중간 P도 최종 곱을 넘지 않기 때문입니다.

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인 세 번째 작업에서도 이동과 카운터 증가는 반드시 해야 합니다.

요청과 완료 시점을 먼저 정하기

아래 인터페이스는 idle에서 start=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입니다. 이 불변식은 작은 예제의 파형만 보는 것보다 누산·이동 순서가 맞는 이유를 분명히 보여 줍니다.

한 작업의 임계 경로에는 2W비트 가산기와 입력 선택이 있습니다. 곱셈 기호를 없앴다고 항상 더 작거나 빠른 것은 아닙니다. FPGA의 전용 DSP 블록, 합성 결과, 필요한 처리율을 함께 비교해야 합니다. 이 모듈은 early-exit, signed 처리, 결과 backpressure를 구현하지 않습니다. 소비 측이 done을 놓치지 않는 계약이 필요합니다.

검증 시 0,1,최댓값과 최상위 비트만 1인 B를 포함하고, busy 중 start와 입력 변경 및 reset 취소도 확인하십시오. 특히 최상위 비트만 1인 B는 마지막 누산 누락을 드러냅니다. 위 코드는 새 설명용 RTL이며 시뮬레이션 완료를 주장하지 않습니다.