toms.log: Fibonacci演算の高速化

Fibonacci数列の演算は漸化式から一つずつ添え字を増やしていく計算が一般的だ. しかし並列に演算をすることで添え字を飛ばして進めることができる. これをFPGAで実装してみよう.

githubリポジトリは以下.

Fibonacci数列の演算をそのまま実装したものは以下.

原理

Fibonacci数列の漸化式は

$F_n = F_{n-1} + F_{n-2}$

である. これより $n+1$ 項目以降も $n-1$ 項目と $n-2$ 項目で表すことができる. $F_{n+1}, F_{n+2}, F_{n+3}$ を書き下すと以下のようになる

$F_{n+1} = F_n + F_{n-1} \\ \ \ \ \ \ \ \ \ = 2 \cdot F_{n-1} + F_{n-2} \\ F_{n+2} = 2 \cdot F_{n-1} + F_{n-1} + F_{n-2} \\ F_{n+3} = 4 \cdot F_{n-1} + F_{n-1} + 2 \cdot F_{n-2} + F_{n-2}.$

ここで $3 \cdot F = 2 \cdot F + F$ としているが, これは乗算器をビットシフトと加算器にするためである.

上記より加算器を可能な限り並べることで, レジスタの段数を増やさずに演算の回数を増やすことができる. つまり $F_{n-1}, F_{n-2}$ だけを保持して $F_n, F_{n+1}, F_{n+2}, F_{n+3}$ を計算することができる. データの流れを図示すると以下のようになる.

ここで問題になるのは4つ同時に計算を行うため, このうちどれを選択するかということである. このためセレクタや条件分岐が必要になる. あらためてフィボナッチ数列の添え字を書き下していくと以下のようになる. 各演算ステージの添え字は2進数の下2桁が一致する（ように4並列の演算にしている）.

$F_{n-2}$	$F_{n-1}$	$F_n$	$F_{n+1}$	$F_{n+2}$	$F_{n+3}$
$F_{1}$	$F_{2}$	$F_3$	$F_4$	$F_5$	$F_6$
$F_{5}$	$F_{6}$	$F_7$	$F_8$	$F_9$	$F_{10}$

実装

インターフェース

モジュールの入出力は以下の通り. データのやり取りはAvalon-STで行う.

Name	I/O	P/N	Description
RESET_n	I	N	Reset
CLK	I	P	Clock
ASI_READY	O	P	Avalon-ST sink data ready
ASI_VALID	I	P	Avalon-ST sink data valid
ASI_DATA[DW-1:0]	I	P	Avalon-ST sink data: index n
ASO_VALID	O	P	Avalon-ST source data valid
ASO_DATA[DW-1:0]	O	P	Avalon-ST source data: Fibonacci number
ASO_ERROR	O	P	Avalon-ST source error

DWはデータビット幅.

レジスタ

$F_{n-1}, F_{n-2}$ を保持するためのレジスタを用意するが, $F_{n+2}, F_{n+3}$ のみを保持すればよい. 算術結果によりそれぞれのビット幅が異なるので, 代入のときにビット幅をそろえる必要がある.

	signal fnp3 : std_logic_vector(DW+1 downto 0); -- F_n+3
	signal fnp2 : std_logic_vector(DW+1 downto 0); -- F_n+2
	signal fnp1 : std_logic_vector(DW downto 0); -- F_n+1
	signal fn : std_logic_vector(DW downto 0); -- F_n
	signal fnm1 : std_logic_vector(DW-1 downto 0); -- F_n-1
	signal fnm2 : std_logic_vector(DW-1 downto 0); -- F_n-2
	~~
	process (CLK, RESET_n) begin
	if (RESET_n = '0') then
	fnm1 <= (others => '0');
	fnm2 <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	fnm1 <= fnp3(fnm1'range);
	fnm2 <= fnp2(fnm2'range);
	end if;
	end process;

view raw fib_q_reg.vhd hosted with ❤ by GitHub

出力セレクタ

演算の結果は4つ出てくるため, セレクタを使って選択する. 上で述べたように添え字は $F_3, F_7, F_{11}, ..., F_{n}$ のようにの2進数の下2桁が一致するため, 入力された $n$ の下2桁と一致するものを選べばよい.

	signal calc_n : std_logic_vector(6 downto 0); -- Calculation end count N
	~~
	ASO_DATA <= fn(ASO_DATA'range) when (calc_n(1 downto 0) = "11") else
	fnp1(ASO_DATA'range) when (calc_n(1 downto 0) = "00") else
	fnp2(ASO_DATA'range) when (calc_n(1 downto 0) = "01") else
	fnp3(ASO_DATA'range);

view raw fib_q_sel.vhd hosted with ❤ by GitHub

セレクタは組み合わせ回路で実装しているが, これは望ましくない. 算術演算から直接つながるため, クロックに同期しないまま出力される. 今回は簡単のためにレジスタ出力にしていないが, 本来はレジスタ出力にすべき.

カウンタ

演算が4つずつ進むから, 演算を制御するカウンタも4つずつインクリメントする. 4ずつインクリメントする場合下位2ビットは変化しないから, 実際には下位2ビットを実装しないで1ずつインクリメントするようにしてもよい. 今回は簡単のためにそのまま4ずつインクリメントしている.

	signal cnt : std_logic_vector(calc_n'range); -- Calculation count
	~~
	-- ============================================================================
	-- Calculation count
	-- ============================================================================
	process (CLK, RESET_n) begin
	if (RESET_n = '0') then
	cnt <= (others => '0');
	elsif (CLK'event and CLK = '1') then
	if (busy_i = '1') then
	if (done_i = '1') then
	cnt <= cnt;
	else
	cnt <= cnt + 4;
	end if;
	elsif (ASI_VALID = '1') then
	cnt <= B"000_0011";
	end if;
	end if;
	end process;

view raw fib_q_cnt.vhd hosted with ❤ by GitHub

完了信号

完了信号は入力された演算回数 $n$ (calc_n) とカウンタとを比較してアサートする. カウンタ値は $F_n$ の値を示しているため, $F_{n+3}$ までを比較するためにカウンタの値に $+3$ する必要がある.

	signal done_i : std_logic; -- Calculation done flag
	~~
	-- ============================================================================
	-- Calculation end
	-- ============================================================================
	done_i <= '1' when (busy_i = '1' and cnt + 3 > calc_n - 1) else
	'1' when (busy_i = '1' and calc_n < 3) else
	'0';

view raw fib_q_done.vhd hosted with ❤ by GitHub

エラー処理

エラー処理では以下の2つを扱う.

加算結果のビットオーバーフロー
入力された演算回数が演算可能の回数より多い場合

今回は特にビットオーバーフローのみの注目する.

ビットオーバーフロー

ビットオーバーフローでは加算のときの最上位ビットの桁上げを通知する. 今回は4つを並行して演算するため, 現在の演算回数に一致する演算より上位の演算によるビットオーバーフローは無視しなければならない. また $F_{n+2}, F_{n+3}$ では桁上りが最大で2桁起こる. また現在の演算回数が入力された演算回数 $n$ (calc_n) まで到達していなくてもビットオーバーフローが起こったことを通知する（ここで途中でビットオーバーフローが起こっても演算の打ち切りはしていない）.

	signal over_flow : std_logic; -- Bit overflow assert
	signal over_flow_reg : std_logic; -- Bit overflow assert
	~~
	-- ============================================================================
	-- Bit over flow assert
	-- ============================================================================
	process (CLK, RESET_n) begin
	if (RESET_n = '0') then
	over_flow_reg <= '0';
	elsif (CLK'event and CLK = '1') then
	if (busy_i = '1') then
	if (cnt + 3 < calc_n) then
	if (fn(fn'left) = '1') then
	over_flow_reg <= '1';
	elsif (fnp1(fnp1'left) = '1') then
	over_flow_reg <= '1';
	elsif (fnp2(fnp2'left downto fnp2'left-1) > 0) then
	over_flow_reg <= '1';
	elsif (fnp3(fnp3'left downto fnp3'left-1) > 0) then
	over_flow_reg <= '1';
	end if;
	end if;
	else
	over_flow_reg <= '0';
	end if;
	end if;
	end process;

	over_flow <= '1' when (calc_n(1 downto 0) = "11" and fn(fn'left) = '1') else
	'1' when (calc_n(1 downto 0) = "00" and fnp1(fnp1'left) = '1') else
	'1' when (calc_n(1 downto 0) = "01" and fnp2(fnp2'left downto fnp2'left-1) > 0) else
	'1' when (calc_n(1 downto 0) = "10" and fnp3(fnp3'left downto fnp3'left-1) > 0) else
	'0';

view raw fib_q_overflow.vhd hosted with ❤ by GitHub

まとめ

以上のようにすることで, 1段ずつ組んだフィボナッチ演算よりも4倍速い演算回路ができる. アイデアは $F_n,F_{n+1},F_{n+2},F_{n+3}$ の数式を並べるだけだが, それにともない制御信号も変わる.

以下にIntel Cyclone Vでコンパイルした結果を示す.

+-------------------------------------------------------------------------------+
; Flow Summary                                                                  ;
+---------------------------------+---------------------------------------------+
; Flow Status                     ; Successful - Fri Mar 06 22:55:04 2020       ;
; Quartus Prime Version           ; 17.1.0 Build 590 10/25/2017 SJ Lite Edition ;
; Revision Name                   ; FIB_Q                                       ;
; Top-level Entity Name           ; FIB_Q                                       ;
; Family                          ; Cyclone V                                   ;
; Device                          ; 5CGXFC7C7F23C8                              ;
; Timing Models                   ; Final                                       ;
; Logic utilization (in ALMs)     ; 128 / 56,480 ( < 1 % )                      ;
; Total registers                 ; 80                                          ;
; Total pins                      ; 70 / 268 ( 26 % )                           ;
; Total virtual pins              ; 0                                           ;
; Total block memory bits         ; 0 / 7,024,640 ( 0 % )                       ;
; Total DSP Blocks                ; 0 / 156 ( 0 % )                             ;
+---------------------------------+---------------------------------------------+

+--------------------------------------------------+
; Slow 1100mV 85C Model Fmax Summary               ;
+------------+-----------------+------------+------+
; Fmax       ; Restricted Fmax ; Clock Name ; Note ;
+------------+-----------------+------------+------+
; 129.79 MHz ; 129.79 MHz      ; CLK        ;      ;
+------------+-----------------+------------+------+

1段ずつ組んだフィボナッチ演算ではLogic utilizationが42だったため, 3倍ほど実装サイズが大きくなっている. 加算器を並列に並べたのがそのまま現れていることがわかる. また動作周波数は221.09 MHzから129.79 MHzへと下がっている. これは加算器をそのまま組み合わせ回路で出力しているためだと考えられる. 今回は簡単のためにこのようにしたが, 実際に使う場合は加算器にレジスタをつないで出力すべきである.

toms.log

2020/05/16

Fibonacci演算の高速化

原理

実装