Intel FPGAのアダーツリー

2つずつ足していけば良いというわけではない.

『6. 推奨される HDL コーディング構文』[1]にデバイスごとに加算器のつなぎ方を変えるべきということが書いてある.

アダー・ツリー

ターゲットにしたアルテラ・デバイスのアーキテクチャに合わせてア ダー・ツリーを適切に構築すると、性能と集積度が大幅に改善される場 合があります。大きなアダー・ツリーを使用するアプリケーションの例 として、有限インパルス応答（FIR）フィルタがあります。パイプライ ン化されたバイナリまたはターナリ・アダー・ツリーを適切に使用する と、結果の品質を大幅に改善できます。

ロジック・エレメントに 4 入力 LUT を使用したアーキテクチャ

Stratix シリーズ、Cyclone シリーズ、APEX シリーズ、および FLEX シ リーズのデバイスなどのアーキテクチャは、LE の標準組み合わせ構造と して 4 入力 LUT を使用しています。 デザインがパイプライン化可能な場合、4 入力ルックアップ・テーブル を使用するデバイスにおいて 3 つの数値（A、B、C）を最も高速で加算 する方法は、A+B を計算し、出力をラッチし、ラッチされた出力を C に加算することです。A + B の加算には 1 レベルのロジック（1 つの LE で 1 ビットが加算される）が必要なので、最大クロック速度で実行され ます。これは必要なだけ拡張できます。

アダプティブ・ロジック・エレメントに 6 入力 LUT を使用した アーキテクチャ

Stratix II アーキテクチャは基本ロジック構造に 6 入力 LUT を使用する ため、Stratix II デバイスは上記の 4 入力 LUT を用いた例とは異なるコー ディング・スタイルのほうが有利です。特に Stratix II デバイスの ALM は、3 ビットを同時に加算できます。したがって、上記の例のツリーは 深度が 2 レベルで、4 つの add-by-two の代わりに、2 つの add-by-three で実現できることになります。

だそうな. つまりいつも二項加算でつなげれば良いというわけではないらしい. おそらくデバイスアーキテクチャを見ればわかるだろう. 私にはわからない. ということでCyclone VとMAX 10で一度に加算する数を変えて試してみた. 実装したのは64個の移動平均. 2項加算と3項, 4項, 6項の場合で実装した. 当然3項と6項の加算は64個であまりが出るので, 一部項の数が異なる. 下に2項の場合のみのソースコードを載せる.

	-- =====================================================================
	-- Title : Moving average 64taps 2adder
	--
	-- File Name : ADDR_TREE_2.vhd
	-- Project : Sample
	-- Block :
	-- Tree :
	-- Designer : toms74209200 <https://github.com/toms74209200>
	-- Copyright : 2019 toms74209200
	-- License : MIT License.
	-- http://opensource.org/licenses/mit-license.php
	-- =====================================================================
	library ieee;
	use ieee.std_logic_1164.all;
	use ieee.std_logic_unsigned.all;
	entity ADDR_TREE_2 is
	port(
	CLK : in std_logic; --(p) Clock
	nRST : in std_logic; --(n) Reset
	EN : in std_logic; --(p) Data input enable
	IN_DAT : in std_logic_vector(15 downto 0); --(p) Data
	OUT_DAT : out std_logic_vector(15 downto 0) --(p) Data
	);
	end ADDR_TREE_2;
	architecture RTL of ADDR_TREE_2 is
	-- Parameter --
	constant TAP : integer := 64; -- Filter taps
	-- Internal signal --
	type RegAryType is array (0 to TAP-1) of std_logic_vector(15 downto 0);
	type SumAryType is array (0 to TAP-1) of std_logic_vector(IN_DAT'length+TAP-1 downto 0);
	signal dat_reg : RegAryType; -- Data register array x[n]
	signal sum : SumAryType; -- Sum array
	begin
	-- ***********************************************************
	-- Data register
	-- ***********************************************************
	process (CLK, nRST) begin
	if (nRST = '0') then
	dat_reg(0) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	dat_reg(0) <= IN_DAT;
	end if;
	end if;
	end process;
	process (CLK, nRST) begin
	for i in 1 to TAP-1 loop
	if (nRST = '0') then
	dat_reg(i) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	dat_reg(i) <= dat_reg(i-1);
	end if;
	end if;
	end loop;
	end process;
	-- ***********************************************************
	-- Summation
	-- ***********************************************************
	process (CLK, nRST) begin
	for i in 0 to 31 loop
	if (nRST = '0') then
	sum(i) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	sum(i) <= (X"0000_0000_0000_0000" & dat_reg(i*2)) + (X"0000_0000_0000_0000" & dat_reg(i*2+1));
	end if;
	end if;
	end loop;
	end process;
	process (CLK, nRST) begin
	for i in 0 to 15 loop
	if (nRST = '0') then
	sum(i+32) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	sum(i+32) <= sum(i*2) + sum(i*2+1);
	end if;
	end if;
	end loop;
	end process;
	process (CLK, nRST) begin
	for i in 0 to 7 loop
	if (nRST = '0') then
	sum(i+32+16) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	sum(i+32+16) <= sum(i*2+32) + sum(i*2+1+32);
	end if;
	end if;
	end loop;
	end process;
	process (CLK, nRST) begin
	for i in 0 to 3 loop
	if (nRST = '0') then
	sum(i+32+16+8) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	sum(i+32+16+8) <= sum(i*2+32+16) + sum(i*2+1+32+16);
	end if;
	end if;
	end loop;
	end process;
	process (CLK, nRST) begin
	if (nRST = '0') then
	sum(60) <= (others => '0');
	sum(61) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	sum(60) <= sum(56) + sum(57);
	sum(61) <= sum(58) + sum(59);
	end if;
	end if;
	end process;
	process (CLK, nRST) begin
	if (nRST = '0') then
	sum(62) <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (EN = '1') then
	sum(62) <= sum(60) + sum(61);
	end if;
	end if;
	end process;
	-- ***********************************************************
	-- Divider
	-- ***********************************************************
	OUT_DAT <= sum(62)(21 downto 6);
	end RTL; -- ADDR_TREE_2

view raw ADDR_TREE_2.vhd hosted with ❤ by GitHub

アダーツリーの実験用なので普通はこんなふうに移動平均しない. 直接形のFIRフィルタの加算はこんな感じになるだろう.

詳しくは以下のリポジトリを参照. ソースコードと実装結果を載せた.

https://github.com/toms74209200/ADDR_TREE

実装結果

下に実装した結果を抜粋して表にまとめた. Cyclone V(5CSEBA6U19C6)とMAX 10(10M08SAE144C8GES)で違うスピードグレードにしてしまったため, デバイス同士では比較できない.

Cyclone V

	Logic utilization	Total registers	CLK
2	739	2146	306.28
3	435	1623	309.02
4	545	1623	309.02
6	511	1292	201.01

MAX 10

	Logic utilization	Total registers	CLK
2	2,156	2146	269.69
3	1,841	1623	177.87
4	1,653	1408	178.22
6	1,663	1292	127.52

まず言えるのはCyclone Vでは3項の加算, MAX 10では4項の加算が最も優れているということだ. 何も考えずに2項にした場合, 動作周波数は問題ないがレジスタと（ここでは陽に表れていないが）レイテンシが増える. 対していっぺんに加算した6項では段数が減るため, レジスタとレイテンシは減るが動作周波数が大幅に下る.

参考

[1] 6. 推奨される HDL コーディング構文 https://www.intel.co.jp/content/dam/altera-www/global/ja_JP/pdfs/literature/hb/qts/qts_qii51007_j.pdf