Fibonacci演算の高速化

Fibonacci数列の演算は漸化式から一つずつ添え字を増やしていく計算が一般的だ. しかし並列に演算をすることで添え字を飛ばして進めることができる. これをFPGAで実装してみよう. <a name='more'></a> githubリポジトリは以下. <a href="https://github.com/toms74209200/FIB_Q"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgNVYmsCeKLHxudVpk0vNXGDPfq5idcWEti6kHoN1-S7PvQIj-dQFM8bydQMX-U_JUHjlg9wkAtmmRYYnXGDccNXgzkE6LL16EXoxHdE093m6v8W4u5PVRAmu4wU_kF56oZ4ZW4K4DqOshV/s1600/FIB_Q.png" width="400px"></a> Fibonacci数列の演算をそのまま実装したものは以下. [toms.log: HDLでフィボナッチ数](https://toms-log.blogspot.com/2019/01/hdl12.html) ## 原理 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}$のみを保持すればよい. 算術結果によりそれぞれのビット幅が異なるので, 代入のときにビット幅をそろえる必要がある. ### 出力セレクタ 演算の結果は4つ出てくるため, セレクタを使って選択する. 上で述べたように添え字は$F_3, F_7, F_{11}, ..., F_{n}$のようにの2進数の下2桁が一致するため, 入力された$n$の下2桁と一致するものを選べばよい. セレクタは組み合わせ回路で実装しているが, これは望ましくない. 算術演算から直接つながるため, クロックに同期しないまま出力される. 今回は簡単のためにレジスタ出力にしていないが, 本来はレジスタ出力にすべき. ### カウンタ 演算が4つずつ進むから, 演算を制御するカウンタも4つずつインクリメントする. 4ずつインクリメントする場合下位2ビットは変化しないから, 実際には下位2ビットを実装しないで1ずつインクリメントするようにしてもよい. 今回は簡単のためにそのまま4ずつインクリメントしている. ### 完了信号 完了信号は入力された演算回数$n$ (`calc_n`) とカウンタとを比較してアサートする. カウンタ値は$F_n$の値を示しているため, $F_{n+3}$までを比較するためにカウンタの値に$+3$する必要がある. ## エラー処理 エラー処理では以下の2つを扱う. - 加算結果のビットオーバーフロー - 入力された演算回数が演算可能の回数より多い場合 今回は特にビットオーバーフローのみの注目する. ### ビットオーバーフロー ビットオーバーフローでは加算のときの最上位ビットの桁上げを通知する. 今回は4つを並行して演算するため, 現在の演算回数に一致する演算より上位の演算によるビットオーバーフローは無視しなければならない. また$F_{n+2}, F_{n+3}$では桁上りが最大で2桁起こる. また現在の演算回数が入力された演算回数$n$ (`calc_n`) まで到達していなくてもビットオーバーフローが起こったことを通知する（ここで途中でビットオーバーフローが起こっても演算の打ち切りはしていない）. ## まとめ 以上のようにすることで, 1段ずつ組んだフィボナッチ演算よりも4倍速い演算回路ができる. アイデアは$F_n,F_{n+1},F_{n+2},F_{n+3}$の数式を並べるだけだが, それにともない制御信号も変わる. 以下にIntel Cyclone Vでコンパイルした結果を示す. ```text +-------------------------------------------------------------------------------+ ; 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 % ) ; +---------------------------------+---------------------------------------------+ ``` ```text +--------------------------------------------------+ ; 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へと下がっている. これは加算器をそのまま組み合わせ回路で出力しているためだと考えられる. 今回は簡単のためにこのようにしたが, 実際に使う場合は加算器にレジスタをつないで出力すべきである.