Help us understand the problem. What is going on with this article?

FPGAで加算器を実装するということ - 多入力加算 1

More than 1 year has passed since last update.

https://qiita.com/srmfsan/items/bc28156c41e6a26315cb
の続き。

多入力の加算 a+b+c+d+e+f+... について考えます。

更新履歴

  • adder256_ternary のソースに間違いがあったので修正しました
    • このため、合成結果の回路規模も修正しました

多入力加算

まずは、前回と同様に、加算器をツリー状に配置したパイプラインで実装してみます。
256個の入力の総和をとる場合を例とします。

module latency fMax ALMs FFs LUTs
adder256 1clk 70MHz 1500 32 4127
adder256_binary 8clk 225MHz 4048 8160 8160
adder256_ternary 6clk 213MHz 2111 4224 4224
adder256_quatenary 4clk 159MHz 2335 2720 5440

adder256 は256入力を一度に加算します。
binaryは1段で2項の加算をするパイプラインで、8段で256要素の総和が求まります。
ternaryは1段で3項の加算であり、6段で総和が求まります。
quatenaryは1段で4項の加算であり、4段で総和が求まります。

ここでもやはり、3項加算ツリーが最強です。
6clk のレイテンシさえ許せば、回路規模(ALM数)は最小で、動作周波数も最も高い回路となります。

回路規模について、フリップフロップ数だけに着目すると、無印が最小です。
しかし、LUT数(組み合わせ回路)が大きいため、ALMとしての占有量が増えてしまっています。
動作周波数についても、最低となっています。

ASICの場合には、フリップフロップもLUTもゲートに換算して回路規模を数えます
一方、FPGAの構成要素はロジックエレメント=フリップフロップ+LUTです。
FF数が極端に少なかったとしても、LUTの使用数が多ければ、ロジックエレメントの消費は大きくなってしまいます。

フリップフロップとLUTの使用比率が重要です。
既に存在する回路要素を使わないのはもったいないことです。

ソースコード

adder256

module adder256 #(
    parameter   W   = 32
) (
    input wire                  clk,
    input wire  [255:0][W-1:0]  d,
    output reg  [W-1:0]         sum
);

    logic  [W-1:0]  sumComb;

    always_comb begin
        sumComb = 0;
        for (int i=0; i<=255; i++) sumComb = sumComb + d[i];
    end

    always_ff @(posedge clk) begin
        sum <= sumComb;
    end


endmodule

adder256_binary

module adder256_binary #(
    parameter   W   = 32
) (
    input wire                  clk,
    input wire  [255:0][W-1:0]  d,
    output reg  [W-1:0]         sum
);

    logic [127:0][W-1:0] sum1;
    logic [ 63:0][W-1:0] sum2;
    logic [ 31:0][W-1:0] sum3;
    logic [ 15:0][W-1:0] sum4;
    logic [  7:0][W-1:0] sum5;
    logic [  3:0][W-1:0] sum6;
    logic [  1:0][W-1:0] sum7;

    always_ff @(posedge clk) begin
        for (int i=0; i<=127; i++) sum1[i] <= d[i*2+0]    + d[i*2+1];
        for (int i=0; i<= 63; i++) sum2[i] <= sum1[i*2+0] + sum1[i*2+1];
        for (int i=0; i<= 31; i++) sum3[i] <= sum2[i*2+0] + sum2[i*2+1];
        for (int i=0; i<= 15; i++) sum4[i] <= sum3[i*2+0] + sum3[i*2+1];
        for (int i=0; i<=  7; i++) sum5[i] <= sum4[i*2+0] + sum4[i*2+1];
        for (int i=0; i<=  3; i++) sum6[i] <= sum5[i*2+0] + sum5[i*2+1];
        for (int i=0; i<=  1; i++) sum7[i] <= sum6[i*2+0] + sum6[i*2+1];
        sum <= sum7[0] + sum7[1];
    end

endmodule

adder256_ternary

module adder256_ternary #(
    parameter   W   = 32
) (
    input wire                  clk,
    input wire  [255:0][W-1:0]  d,
    output reg  [W-1:0]         sum
);

    logic [85:0][W-1:0] sum1;
    logic [28:0][W-1:0] sum2;
    logic [ 9:0][W-1:0] sum3;
    logic [ 3:0][W-1:0] sum4;
    logic [ 1:0][W-1:0] sum5;

    always_ff @(posedge clk) begin
        for (int i=0; i<=83; i++) sum1[i] <= d[i*3+0]    + d[i*3+1]    + d[i*3+2];
        sum1[84] <= d[252] + d[253];
        sum1[85] <= d[254] + d[255];

        for (int i=0; i<=27; i++) sum2[i] <= sum1[i*3+0] + sum1[i*3+1] + sum1[i*3+2];
        sum2[28] <= sum1[84] + sum1[85];

        for (int i=0; i<= 8; i++) sum3[i] <= sum2[i*3+0] + sum2[i*3+1] + sum2[i*3+2];
        sum3[9] <= sum2[27] + sum2[28];

        sum4[0] <= sum3[0] + sum3[1] + sum3[2];
        sum4[1] <= sum3[3] + sum3[4] + sum3[5];
        sum4[2] <= sum3[6] + sum3[7];
        sum4[3] <= sum3[8] + sum3[9];

        sum5[0] <= sum4[0] + sum4[1];
        sum5[1] <= sum4[2] + sum4[3];

        sum <= sum5[0] + sum5[1];
    end

endmodule

adder256_quatenary

module adder256_quatenary #(
    parameter   W   = 32
) (
    input wire                  clk,
    input wire  [255:0][W-1:0]  d,
    output reg  [W-1:0]         sum
);

    logic [63:0][W-1:0] sum1;
    logic [15:0][W-1:0] sum2;
    logic [ 3:0][W-1:0] sum3;

    always_ff @(posedge clk) begin
        for (int i=0; i<=63; i++) sum1[i] <= d[i*4+0]    + d[i*4+1]    + d[i*4+2]    + d[i*4+3];
        for (int i=0; i<=15; i++) sum2[i] <= sum1[i*4+0] + sum1[i*4+1] + sum1[i*4+2] + sum1[i*4+3];
        for (int i=0; i<=3 ; i++) sum3[i] <= sum2[i*4+0] + sum2[i*4+1] + sum2[i*4+2] + sum2[i*4+3];
        sum <= sum3[0] + sum3[1] + sum3[2] + sum3[3];
    end

endmodule

次回予告

ここまで、+ 演算子で記述する「通常の」加算器を実装してきました。
次回は、キャリーセーブアダーを使った加算器を紹介していきます。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした