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

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
```Verilog
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

```Verilog
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


```Verilog
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

```Verilog
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
```

# 次回予告

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