分治法帶來的好處

上一篇文章分治法（Divide and Conquer）以 Leading Zero Count 為例解釋了分治法帶來的好處，本篇文章再舉一個(gè)類似的例子。

Count Number of Ones，計(jì)算一個(gè)32-bit輸入中 1 的個(gè)數(shù)。

For 循環(huán)

always_comb begin
    count = 0;
    for (int i=0; i<32; i++) begin
        count = count + data_i[i];
    end
end

分治法

第一級(jí)：6-3 compressor （需要三個(gè)LUT6）

第二級(jí)：ternary adder

第三級(jí)：ternary adder

logic [4:0][2:0] temp1;
logic [1:0] temp1_1;
always_comb
    for (int i=0; i<5; i++) begin
        case(data_i[i*6 +: 6])
            6'b000000 : temp1[i] = 0;
            6'b000001 : temp1[i] = 1;
            6'b000010 : temp1[i] = 1;
            6'b000011 : temp1[i] = 2;
            ...
            6'b111111 : temp1[i] = 6;
        endcase
    end
end
assign temp1_1 = data_i[30] + data_i[31]:

logic [1:0][4:0] temp2;
always_comb begin
    temp2[0] = temp1[0] + temp1[1] + temp[2];
    temp2[1] = temp1[3] + temp1[4] + temp[5];
end

logic [5:0] count;
assign count = temp2[0] + temp2[1] + temp1_1;

綜合結(jié)果對(duì)比

審核編輯：劉清