FPGAで加算器を実装するということ - 3項加算

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


# 様々な加算の実装

ここまで概説したALMの基本構造を前提として、様々な加算器の実装を考えていきましょう。

※ここでは、Altera(Intel)のFPGAを前提としていますが、XilinxやLatticeのFPGAも基本的には同じ構成ですので、だいたい適用可能ではないかと思います。

## 3項加算

共有演算モードを使うことで、3項の加算が高密度に（しかし最速ではないが）実装できます。
このため、多入力の加算器のパイプラインを実装する場合には、3項で1段にすると都合がよい場合が多いです。

32bit 8入力の加算の実装例を4つ示します。

 * adder8
    * 8入力を一度に加算します
 * adder8_binary
    * 1段で2項の加算をするバイナリツリー状の回路です
    * 3段のパイプラインです
 * adder8_ternary
    * 1段で3項を加算します
    * 2段のパイプラインです
 * adder8_quatenary
    * 1段で4項を加算します
    * 2段のパイプラインです

回路図として以下のようになります。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/142927/12bb7daf-738e-4358-3351-5aa346248856.png)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/142927/77a53168-3747-837f-65f7-03339848cc51.png)

Verilog-HDLでの記述は以下のようになります。

```Verilog
module adder8 #(
    parameter   W   = 32
) (
    input wire              	clk,
    input wire  [7:0][W-1:0]    d,
    output reg  [W-1:0]     	sum
);

    always_ff @(posedge clk) begin
        sum <= d[0] + d[1] + d[2] + d[3] + d[4] + d[5] + d[6] + d[7];
    end

endmodule
```

```Verilog
module adder8_binary #(
    parameter   W   = 32
) (
    input wire              	clk,
    input wire  [7:0][W-1:0]    d,
    output reg  [W-1:0]     	sum
);

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

    always_ff @(posedge clk) begin
        sum1[0] <= d[0] + d[1];
        sum1[1] <= d[2] + d[3];
        sum1[2] <= d[4] + d[5];
        sum1[3] <= d[6] + d[7];

        sum2[0] <= sum1[0] + sum1[1];
        sum2[1] <= sum1[2] + sum1[3];

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

endmodule
```

```Verilog
module adder8_ternary #(
    parameter   W   = 32
) (
    input wire              	clk,
    input wire  [7:0][W-1:0]    d,
    output reg  [W-1:0]     	sum
);

    logic [2:0][W-1:0] sum1;

    always_ff @(posedge clk) begin
        sum1[0] <= d[0] + d[1] + d[2];
        sum1[1] <= d[3] + d[4] + d[5];
        sum1[2] <= d[6] + d[7];

        sum <= sum1[0] + sum1[1] + sum1[2];
    end

endmodule
```

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

    logic [1:0][W-1:0] sum1;

    always_ff @(posedge clk) begin
        sum1[0] <= d[0] + d[1] + d[2] + d[3];
        sum1[1] <= d[4] + d[5] + d[6] + d[7];

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

endmodule

```

Quartus での合成結果を示します。

 * Cyclone V 5CSEMA4U23C6
 * 17.0.0 Build 595 04/25/2017 SJ Lite Edition
 * Virtual Pin による仮合成
 * クロックは300MHzで制約

| module         | Latency | fMax | ALMs | FFs | ALUTs |
|:---------------|:-:|:-:|:-:|:-:|:-:|
| adder8 | 1clk | 171MHz |47.5|32|128|
| adder8_binary  |3clk|327MHz|111.0 |224|224|
| adder8_ternary |2clk|317MHz|63.8|128|128|
| adder8_quatenary|2clk|226MHz|67.1|160|96|

adder8 が最も回路規模が小さいです。しかし、fMax が一番遅い回路です。

adder8_binaryが最も fMax が高いですが、回路規模は adder8_ternary に比べて約倍となっています。Latencyは3clkで最も遅い回路です。

adder8_quaternaryは、adder8_ternary とほぼ同様の回路規模です（ALM数は同等、FF数LUT数は小さい）。しかし、fMaxはbinary, ternaryに比べて100MHzも遅くなっています。

上記の例では、3入力ごとに加算をまとめるのが、最もバランスが良いといえます。

# 修正履歴

 * 読みやすさのため、サンプルコードを packed array 形式で記述するようにしました
 * ブロック図を追加し、説明文を修正しました