Tree Multiplier(16bit Dadda Multiplier)

이번 포스팅은 Tree Multiplier(곱셈기)에 대해 다뤄볼 것이다.

 

내가 처음 설계해본 것은 Carry Save Adder를 이용한 곱셈기였다.

이런 구조의 곱셈기를 8비트로 만들었다.

8비트로 저런 곱셈기를 만들면 critical path가 2*HA(Half Adder) + 13*FA(Full Adder)가 된다. 16비트가 되면 당연히 이보다 더 긴 시간이 걸릴 것이다.

 

Tree Multiplier는 위에서 설명한 곱셈기보다 더 짧은 시간 안에 곱셈을 수행한다. 8비트를 예로 들면 8x8 부분곱이 이루는 Stage의 갯수를 감소시켜 연산을 고속화한다.

왼쪽 그림은 Wallace Tree로, 3개 혹은 2개의 부분곱 그룹을 Full Adder 혹은 Half Adder로 연산하여 Stage를 줄인다. 

가장 위의 점들은 8x8 부분곱들을 나타낸 것인데, 여기서 3/2개씩 묶어서 FA 혹은 HA에 입력하면 Sum과 Carry가 출력된다. Sum은 해당 자리에 남고, Carry는 다음 자리에 올라가므로 3개의 부분곱은 2개의 부분합으로 나눠진다.

 

오른쪽 2번째 열에서 부분곱 2개의 묶음은 해당 자리에 부분합 1개를 남기며 그 다음 자리에 Carry 1개를 남긴다. 그 다음 자리에서 3개의 부분곱 묶음은 해당 자리에 부분합 1개, 다음 자리에 Carry 1개를 남긴다. 따라서 3번째 열에는 2개의 부분합이 남는다(두번째 단계). 같은 방식으로 4열에는 3개(부분합1 + carry1 + 기존 부분곱)가 남게 된다.

 

이런식으로 부분합들을 2줄까지 줄여 이를 16비트 Adder로 더하게 만드는게 Tree Multiplier의 동작 원리다.

 

조금 다른 방식으로 2줄까지 만드는 방식도 있는데, Dadda Reduction이라고 한다.

Dadda Reduction은 기존 Wallace Tree에 비해 게이트 수가 적다고 약간 더 빠르다는 특징이 있다.

아래 그림은 8x8 Dadda Reduction을 나타내고 있다.

앞의 Wallace Tree와 똑같이 3/2개 묵음은 Sum과 Carry 하나씩을 남겨 Stage를 줄인다. 차이점은 마지막 단계에서 두 줄의 길이가 비슷해지는 것이다.

 

Dadda Reduction은 아래와 같은 규칙으로 수행된다.

단계 d는 아래와 같고, 2, 3, 4, 6, 9, 13, 19, ... 등으로 단계를 구분짓는다.

16비트는 d=13에서부터 d를 초과하는 높이의 부분곱들에 대해 reduction을 시작한다. 가장 낮은 비트부터 시작한다.

Carry로 인해 LSB+1bit에서는 높이가 Carry 갯수만큼 추가된 상태에서 reduction을 해야한다. 

 

깃허브에 Verilog 코드 및 16비트 reduction에 대한 엑셀 파일을 만들어뒀다.

https://github.com/pyong-1459/Dadda-Multiplier-16bit-implementation

GitHub - pyong-1459/Dadda-Multiplier-16bit-implementation: 16bit Tree Multiplier implementation with Dadda reduction

doc 폴더에 있는 엑셀 파일부터 한번 살펴보자.

각 부분곱들의 비트 조합을 적어뒀다. 2,14는 AxB에서 A의 2비트와 B의 14비트의 부분곱이라는 뜻이다.

볼드 처리한 부분이 d를 초과하는 부분곱들이며, 테두리가 칠해져 있는 것들이 FA/HA로 더하는 부분곱들이다.

13열에서는 HA 1개, 14열에서는 FA 1개 HA 1개가 쓰이며, 16열에서는 FA 2개 HA 1개가 쓰인다.

 

그 다음 단계는 아래와 같다.

Sum0~11은 이전 단계에서 사용된 HA, FA들의 Sum 값들을 나타내며 Co는 Carry를 나타낸다. 2단계에서는 44개의 FA/HA가 쓰인다. 나머지 부분은 너무 길어서 생략한다.

 

이 표를 토대로 코드를 작성했으며 총 200여줄의 코드가 만들어졌다. 아래 코드는 그 중 일부를 보여준다.

module Dadda_16b(
    output [31:0] Y, 
    input [15:0] A, B
);

wire [11:0] Step1Sum, Step1Co;
wire [43:0] Step2Sum, Step2Co;
wire [53:0] Step3Sum, Step3Co;
wire [45:0] Step4Sum, Step4Co;
wire [25:0] Step5Sum, Step5Co;
wire [27:0] Step6Sum, Step6Co;
wire [30:0] Step6A, Step6B;    // Last Step: {30} + {29, 1'b0} => 32bit Y

wire [15:0] DotProduct [0:15];
wire [15:0] Yh0, Yh1;
wire Carry_low, Carry_high0, Carry_high1, PG_low, PG_high0, PG_high1, GG_low, GG_high0, GG_high1;

genvar i;
generate
    for (i=0; i<16; i=i+1) begin
        assign DotProduct[i] = B & {16{A[i]}};
    end
endgenerate
// 15 MSB, 0 LSB
// Step 1
HA      STEP1HA0 (Step1Sum[0],  Step1Co[0],  DotProduct[13][0],  DotProduct[12][1]);                        // Col13
CSA_1b  STEP1FA00(Step1Sum[1],  Step1Co[1],  DotProduct[14][0],  DotProduct[13][1],  DotProduct[12][2]);    // Col14
HA      STEP1HA1 (Step1Sum[2],  Step1Co[2],  DotProduct[11][3],  DotProduct[10][4]);                        // Col14
CSA_1b  STEP1FA01(Step1Sum[3],  Step1Co[3],  DotProduct[15][0],  DotProduct[14][1],  DotProduct[13][2]);    // Col15
CSA_1b  STEP1FA02(Step1Sum[4],  Step1Co[4],  DotProduct[12][3],  DotProduct[11][4],  DotProduct[10][5]);    // Col15
HA      STEP1HA2 (Step1Sum[5],  Step1Co[5],  DotProduct[9][6],   DotProduct[8][7]);                         // Col15
CSA_1b  STEP1FA03(Step1Sum[6],  Step1Co[6],  DotProduct[15][1],  DotProduct[14][2],  DotProduct[13][3]);    // Col16
CSA_1b  STEP1FA04(Step1Sum[7],  Step1Co[7],  DotProduct[12][4],  DotProduct[11][5],  DotProduct[10][6]);    // Col16
HA      STEP1HA3 (Step1Sum[8],  Step1Co[8],  DotProduct[9][7],   DotProduct[8][8]);                         // Col16
CSA_1b  STEP1FA05(Step1Sum[9],  Step1Co[9],  DotProduct[15][2],  DotProduct[14][3],  DotProduct[13][4]);    // Col17
CSA_1b  STEP1FA06(Step1Sum[10], Step1Co[10], DotProduct[12][5],  DotProduct[11][6],  DotProduct[10][7]);    // Col17
CSA_1b  STEP1FA07(Step1Sum[11], Step1Co[11], DotProduct[15][3],  DotProduct[14][4],  DotProduct[13][5]);    // Col18
//------------
// Step 2
HA      STEP2HA0 (Step2Sum[0],  Step2Co[0],  DotProduct[9][0],   DotProduct[8][1]);                         // Col9
CSA_1b  STEP2FA01(Step2Sum[1],  Step2Co[1],  DotProduct[10][0],  DotProduct[9][1],   DotProduct[8][2]);     // Col10
HA      STEP2HA1 (Step2Sum[2],  Step2Co[2],  DotProduct[7][3],   DotProduct[6][4]);                         // Col10
CSA_1b  STEP2FA02(Step2Sum[3],  Step2Co[3],  DotProduct[11][0],  DotProduct[10][1],  DotProduct[9][2]);     // Col11
CSA_1b  STEP2FA03(Step2Sum[4],  Step2Co[4],  DotProduct[8][3],   DotProduct[7][4],   DotProduct[6][5]);     // Col11
HA      STEP2HA2 (Step2Sum[5],  Step2Co[5],  DotProduct[5][6],   DotProduct[4][7]);                         // Col11
CSA_1b  STEP2FA04(Step2Sum[6],  Step2Co[6],  DotProduct[12][0],  DotProduct[11][1],  DotProduct[10][2]);    // Col12
CSA_1b  STEP2FA05(Step2Sum[7],  Step2Co[7],  DotProduct[9][3],   DotProduct[8][4],   DotProduct[7][5]);     // Col12
CSA_1b  STEP2FA06(Step2Sum[8],  Step2Co[8],  DotProduct[6][6],   DotProduct[5][7],   DotProduct[4][8]);     // Col12
HA      STEP2HA3 (Step2Sum[9],  Step2Co[9],  DotProduct[3][9],   DotProduct[2][10]);                        // Col12
CSA_1b  STEP2FA07(Step2Sum[10], Step2Co[10], Step1Sum[0],        DotProduct[11][2],  DotProduct[10][3]);    // Col13
CSA_1b  STEP2FA08(Step2Sum[11], Step2Co[11], DotProduct[9][4],   DotProduct[8][5],   DotProduct[7][6]);     // Col13
CSA_1b  STEP2FA09(Step2Sum[12], Step2Co[12], DotProduct[6][7],   DotProduct[5][8],   DotProduct[4][9]);     // Col13
CSA_1b  STEP2FA10(Step2Sum[13], Step2Co[13], DotProduct[3][10],  DotProduct[2][11],  DotProduct[1][12]);    // Col13
CSA_1b  STEP2FA11(Step2Sum[14], Step2Co[14], Step1Sum[1],        Step1Sum[2],        Step1Co[0]);           // Col14
CSA_1b  STEP2FA12(Step2Sum[15], Step2Co[15], DotProduct[9][5],   DotProduct[8][6],   DotProduct[7][7]);     // Col14
CSA_1b  STEP2FA13(Step2Sum[16], Step2Co[16], DotProduct[6][8],   DotProduct[5][9],   DotProduct[4][10]);    // Col14
CSA_1b  STEP2FA14(Step2Sum[17], Step2Co[17], DotProduct[3][11],  DotProduct[2][12],  DotProduct[1][13]);    // Col14
CSA_1b  STEP2FA15(Step2Sum[18], Step2Co[18], Step1Sum[3],        Step1Sum[4],        Step1Sum[5]);          // Col15
CSA_1b  STEP2FA16(Step2Sum[19], Step2Co[19], Step1Co[1],         Step1Co[2],         DotProduct[7][8]);     // Col15
CSA_1b  STEP2FA17(Step2Sum[20], Step2Co[20], DotProduct[6][9],   DotProduct[5][10],  DotProduct[4][11]);    // Col15
CSA_1b  STEP2FA18(Step2Sum[21], Step2Co[21], DotProduct[3][12],  DotProduct[2][13],  DotProduct[1][14]);    // Col15
CSA_1b  STEP2FA19(Step2Sum[22], Step2Co[22], Step1Sum[6],        Step1Sum[7],        Step1Sum[8]);          // Col16
CSA_1b  STEP2FA20(Step2Sum[23], Step2Co[23], Step1Co[3],         Step1Co[4],         Step1Co[5]);           // Col16
CSA_1b  STEP2FA21(Step2Sum[24], Step2Co[24], DotProduct[7][9],   DotProduct[6][10],  DotProduct[5][11]);    // Col16
CSA_1b  STEP2FA22(Step2Sum[25], Step2Co[25], DotProduct[4][12],  DotProduct[3][13],  DotProduct[2][14]);    // Col16
CSA_1b  STEP2FA23(Step2Sum[26], Step2Co[26], Step1Sum[9],        Step1Sum[10],       Step1Co[6]);           // Col17
CSA_1b  STEP2FA24(Step2Sum[27], Step2Co[27], Step1Co[7],         Step1Co[8],         DotProduct[9][8]);     // Col17
CSA_1b  STEP2FA25(Step2Sum[28], Step2Co[28], DotProduct[8][9],   DotProduct[7][10],  DotProduct[6][11]);    // Col17
CSA_1b  STEP2FA26(Step2Sum[29], Step2Co[29], DotProduct[5][12],  DotProduct[4][13],  DotProduct[3][14]);    // Col17
CSA_1b  STEP2FA27(Step2Sum[30], Step2Co[30], Step1Sum[11],       Step1Co[9],         Step1Co[10]);          // Col18
CSA_1b  STEP2FA28(Step2Sum[31], Step2Co[31], DotProduct[12][6],  DotProduct[11][7],  DotProduct[10][8]);    // Col18
CSA_1b  STEP2FA29(Step2Sum[32], Step2Co[32], DotProduct[9][9],   DotProduct[8][10],  DotProduct[7][11]);    // Col18
CSA_1b  STEP2FA30(Step2Sum[33], Step2Co[33], DotProduct[6][12],  DotProduct[5][13],  DotProduct[4][14]);    // Col18
CSA_1b  STEP2FA31(Step2Sum[34], Step2Co[34], Step1Co[11],        DotProduct[15][4],  DotProduct[14][5]);    // Col19
CSA_1b  STEP2FA32(Step2Sum[35], Step2Co[35], DotProduct[13][6],  DotProduct[12][7],  DotProduct[11][8]);    // Col19
CSA_1b  STEP2FA33(Step2Sum[36], Step2Co[36], DotProduct[10][9],  DotProduct[9][10],  DotProduct[8][11]);    // Col19
CSA_1b  STEP2FA34(Step2Sum[37], Step2Co[37], DotProduct[7][12],  DotProduct[6][13],  DotProduct[5][14]);    // Col19
CSA_1b  STEP2FA35(Step2Sum[38], Step2Co[38], DotProduct[15][5],  DotProduct[14][6],  DotProduct[13][7]);    // Col20
CSA_1b  STEP2FA36(Step2Sum[39], Step2Co[39], DotProduct[12][8],  DotProduct[11][9],  DotProduct[10][10]);   // Col20
CSA_1b  STEP2FA37(Step2Sum[40], Step2Co[40], DotProduct[9][11],  DotProduct[8][12],  DotProduct[7][13]);    // Col20
CSA_1b  STEP2FA38(Step2Sum[41], Step2Co[41], DotProduct[15][6],  DotProduct[14][7],  DotProduct[13][8]);    // Col21
CSA_1b  STEP2FA39(Step2Sum[42], Step2Co[42], DotProduct[12][9],  DotProduct[11][10], DotProduct[10][11]);   // Col21
CSA_1b  STEP2FA40(Step2Sum[43], Step2Co[43], DotProduct[15][7],  DotProduct[14][8],  DotProduct[13][9]);    // Col22

코드가 너무 길어서 2단계 부분까지만 올렸다.

1~6단계로 이루어져 있으며 마지막 덧셈은 16비트 CLA를 이용해 32비트 Carry Select Adder를 구현했다.

 

assign Step6A = {Step6Co[27], Step6Sum, DotProduct[1][0], DotProduct[0][0]};
assign Step6B = {DotProduct[15][15], Step6Co[26:0], DotProduct[0][2], DotProduct[0][1], 1'b0};

CLA_16b ADDLOW  (Y[15:0], Carry_low, PG_low, GG_low,   1'b0, Step6A[0 +: 16], Step6B[0 +: 16]);
CLA_16b ADDHIGH0(Yh0, Carry_high0, PG_high0, GG_high0, 1'b0, {1'b0, Step6A[16 +: 15]}, {1'b0, Step6B[16 +: 15]});  // 0 Carry prediction
CLA_16b ADDHIGH1(Yh1, Carry_high1, PG_high1, GG_high1, 1'b1, {1'b0, Step6A[16 +: 15]}, {1'b0, Step6B[16 +: 15]});  // 1 Carry prediction

assign Y[31 -: 16] = Carry_low ? Yh1 : Yh0;

Carry Select Adder는 아래 링크를 참조하면 좋을 것 같다.

https://en.wikipedia.org/wiki/Carry-select_adder

Carry-select adder - Wikipedia

 

테스트벤치는 파이썬에서 총 1000개의 무작위 생성된 16비트 값들을 곱해 32비트 reference 값을 생성하여 오류가 나타나는지를 비교하는 코드다.

module tb_16b_Dadda();

reg  [15:0] A;
reg  [15:0] B;
reg  [31:0] Y_ref [0:999];
reg  [15:0] Data [0:1999];
reg  [15:0] err;
wire [31:0] Y;

Dadda_16b TEST(Y, A, B);

integer i, j;
integer k = 1000;

initial begin
    $readmemh("input.txt", Data);
    A <= 16'h0;
    B <= 16'h0;
    #(10);
    for (i=0;i<k;i=i+1) begin
        A <= Data[i*2];
        B <= Data[i*2 + 1];
        #(10);
    end
    #15 $finish;
end

initial begin
    $readmemh("output.txt", Y_ref);
    err <= 16'h0;
    #(10)
    for (j=0;j<k;j=j+1) begin
        // $display("%h", Y_ref[j]);
        #(5);
        if (Y_ref[j] != Y) begin
            err <= err + 1;
        end
        #(5);
    end
end

endmodule

테스트벡터는 깃허브 python 폴더의 vector_gen.py파일에서 생성할 수 있다.

 

23.03.09 추가

Tree Multiplier는 기존 비트수의 2배씩 확장이 용이하여 Tree Multiplier에서 출력된 부분곱을 줄일 수 있다.

앞에서 만든 16비트 곱셈기를 기준으로 32비트를 구현한다고 하면 다음과 같다.

32비트 A, B에 대해 상위 16비트 하위 16비트를 각각 A1/A0, B1/B0라고 하고 각각의 32비트 곱을 A1B1/A0B1/A1B0/A0B0라 하면 아래와 같이 더해야 한다.

 

                                            (A0B0[31:16])( A0B0[15:0] )

                      (A0B1[31:16])( A0B1[15:0] )

                      (A1B0[31:16])( A1B0[15:0] )

(A1B1[31:16])( A1B1[15:0] )

 

즉 64비트 결과에서 48:16 부분의 부분곱만 기존의 방식대로 줄이면 된다는 것이다.

이를 코드로 나타내면 아래와 같다.

module Dadda_32b(
    output [63:0] Y,
    input [31:0] A, B
);

wire [31:0] A0B0, A0B1, A1B0, A1B1;
wire [31:0] Sum0, Co0;
wire Carry_49, Carry_63, Carry_64, PG, GG; 

Dadda_16b MULT00(A0B0, A[0 +: 16],  B[0 +: 16]);
Dadda_16b MULT01(A0B1, A[0 +: 16],  B[16 +: 16]);
Dadda_16b MULT10(A1B0, A[16 +: 16], B[0 +: 16]);
Dadda_16b MULT11(A1B1, A[16 +: 16], B[16 +: 16]);

// Step 1
CSA_1b FA00(Sum0[0],  Co0[0],  A0B0[16], A0B1[0],  A1B0[0]);
CSA_1b FA01(Sum0[1],  Co0[1],  A0B0[17], A0B1[1],  A1B0[1]);
CSA_1b FA02(Sum0[2],  Co0[2],  A0B0[18], A0B1[2],  A1B0[2]);
CSA_1b FA03(Sum0[3],  Co0[3],  A0B0[19], A0B1[3],  A1B0[3]);
CSA_1b FA04(Sum0[4],  Co0[4],  A0B0[20], A0B1[4],  A1B0[4]);
CSA_1b FA05(Sum0[5],  Co0[5],  A0B0[21], A0B1[5],  A1B0[5]);
CSA_1b FA06(Sum0[6],  Co0[6],  A0B0[22], A0B1[6],  A1B0[6]);
CSA_1b FA07(Sum0[7],  Co0[7],  A0B0[23], A0B1[7],  A1B0[7]);
CSA_1b FA08(Sum0[8],  Co0[8],  A0B0[24], A0B1[8],  A1B0[8]);
CSA_1b FA09(Sum0[9],  Co0[9],  A0B0[25], A0B1[9],  A1B0[9]);
CSA_1b FA10(Sum0[10], Co0[10], A0B0[26], A0B1[10], A1B0[10]);
CSA_1b FA11(Sum0[11], Co0[11], A0B0[27], A0B1[11], A1B0[11]);
CSA_1b FA12(Sum0[12], Co0[12], A0B0[28], A0B1[12], A1B0[12]);
CSA_1b FA13(Sum0[13], Co0[13], A0B0[29], A0B1[13], A1B0[13]);
CSA_1b FA14(Sum0[14], Co0[14], A0B0[30], A0B1[14], A1B0[14]);
CSA_1b FA15(Sum0[15], Co0[15], A0B0[31], A0B1[15], A1B0[15]);
CSA_1b FA16(Sum0[16], Co0[16], A1B1[0],  A0B1[16], A1B0[16]);
CSA_1b FA17(Sum0[17], Co0[17], A1B1[1],  A0B1[17], A1B0[17]);
CSA_1b FA18(Sum0[18], Co0[18], A1B1[2],  A0B1[18], A1B0[18]);
CSA_1b FA19(Sum0[19], Co0[19], A1B1[3],  A0B1[19], A1B0[19]);
CSA_1b FA20(Sum0[20], Co0[20], A1B1[4],  A0B1[20], A1B0[20]);
CSA_1b FA21(Sum0[21], Co0[21], A1B1[5],  A0B1[21], A1B0[21]);
CSA_1b FA22(Sum0[22], Co0[22], A1B1[6],  A0B1[22], A1B0[22]);
CSA_1b FA23(Sum0[23], Co0[23], A1B1[7],  A0B1[23], A1B0[23]);
CSA_1b FA24(Sum0[24], Co0[24], A1B1[8],  A0B1[24], A1B0[24]);
CSA_1b FA25(Sum0[25], Co0[25], A1B1[9],  A0B1[25], A1B0[25]);
CSA_1b FA26(Sum0[26], Co0[26], A1B1[10], A0B1[26], A1B0[26]);
CSA_1b FA27(Sum0[27], Co0[27], A1B1[11], A0B1[27], A1B0[27]);
CSA_1b FA28(Sum0[28], Co0[28], A1B1[12], A0B1[28], A1B0[28]);
CSA_1b FA29(Sum0[29], Co0[29], A1B1[13], A0B1[29], A1B0[29]);
CSA_1b FA30(Sum0[30], Co0[30], A1B1[14], A0B1[30], A1B0[30]);
CSA_1b FA31(Sum0[31], Co0[31], A1B1[15], A0B1[31], A1B0[31]);

assign Y[0 +: 17] = {Sum0[0], A0B0[0 +: 16]};

ADD_32b_wCLA ADD0(Y[17 +: 32], Carry_49, 1'b0, {A1B1[16], Sum0[1 +: 31]}, Co0);
CLA_16b      ADD1({Carry_63, Y[63 -: 15]}, Carry_64, PG, GG, Carry_49, {1'b0, A1B1[17 +: 15]}, 16'b0);

endmodule

 

ADD_32b_wCLA는 앞의 32비트 Carry Select Adder를 모듈로 작성한 것이다.

module ADD_32b_wCLA(
    output [31:0]  Sum, 
    output Co, 
    input Cin,
    input [31:0] A, B
);

wire [15:0] SumH0, SumH1;
wire Carry_low, Carry_high0, Carry_high1;
wire PG0, GG0;
wire PG1, GG1;
wire PG2, GG2;

CLA_16b ADDLOW  (Sum[15:0], Carry_low,   PG0, GG0, Cin,  A[15 -: 16], B[15 -: 16]);
CLA_16b ADDHIGH0(SumH0,     Carry_high0, PG1, GG1, 1'b0, A[31 -: 16], B[31 -: 16]);
CLA_16b ADDHIGH1(SumH1,     Carry_high1, PG2, GG2, 1'b1, A[31 -: 16], B[31 -: 16]);

assign Sum[31 -: 16] = Carry_low ? SumH1 : SumH0;
assign Co = Carry_low ? Carry_high1 : Carry_high0;

endmodule

 

참고자료:

https://en.wikipedia.org/wiki/Dadda_multiplier
https://en.wikipedia.org/wiki/Wallace_tree
https://github.com/pyong-1459/Dadda-Multiplier-16bit-implementation