HDLでフィボナッチ数

ソフトウェア言語ではHello, world!の次ぐらいにやると思う. それをあえてハードウェアで実装してみようと思う. <a name='more'></a> 日本語版WikipediaのVHDLのページにもフィボナッチ数の実装が載っているけど, あまりにも的はずれな内容なのでおとなしく英語版Wikipediaを見よう. 実際に実装したgithubリポジトリは以下. [https://github.com/toms74209200/FIB](https://github.com/toms74209200/FIB) ## インターフェース まずは外部と接続するインターフェースを決める. 規格化されたインターフェースを使うことで, 再利用性を高めることが大事. 特にFPGAではタイミング制御が重要なので, インターフェースと内部の処理を完全に切り分けることはできないことが多い. ここではIntel(altera) FPGAを想定するため, 考えられるインターフェースは以下の通り. - Avalon-MM[[1](#avmm_intel)] - Avalon-ST[[2](#avst_intel)] - Nios II Custom Instruction[[3](#ctistr_intel)] CPUとの連携を考えるとAvalon-MMかCustom Instructionだが, ここではHDLで実装しやすいAvalon-STにする. ### Avalon-ST Avalon-STでは`valid`と`data`の2つの信号でsourceからsinkへとデータを送る（参考[[2](#avst_intel)]のFigure 21がわかりやすい）. このインターフェースには使う信号によってバリエーションがあるが, シンプルに`valid`と`data`, `error`のみにする. これに従ってフィボナッチ演算を行うモジュールの入出力を表にまとめると以下の通り. | 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[31:0] | I | P | Avalon-ST sink data: index n | | ASO_VALID | O | P | Avalon-ST source data valid | | ASO_DATA[31:0] | O | P | Avalon-ST source data: Fibonacci number | | ASO_ERROR | O | P | Avalon-ST source error | sourceからのデータ (`ASI_DATA`) はフィボナッチ演算をいくつまで行うかという引数を与える. フィボナッチ数の漸化式 $F_n = F_{n-1} + F_{n-2}$ の$n$にあたる. そしてモジュールが出力するデータ (`ASO_DATA`) は$n$に対応するフィボナッチ数である. ## フィボナッチ演算の構成 フィボナッチ数の漸化式は下式の通り $F_n = F_{n-1} + F_{n-2}.$ この数列の第1項と第2項は特別に $F_1 = 1, F = 2$ とする. これは参考[[4](#fib_suguru)]からの答え合わせをしやすくするためだ. よって必要なものは - レジスタ - 加算器 となる. 回路全体は`CLK`と`nRST`でコントロールする. ### レジスタ 遅延器はレジスタで表現する. `CLK`に同期してデータを引き渡せばよい. レジスタを構成する上で重要なことはそのビット幅である. といってもフィボナッチ数列の場合は加算のみなので, ビット幅が減少することはない. 加算による桁上げを考慮して$F_{n-1}, F_{n-2}$に対して$F_n$はビット幅が1増える. ここで$F_{n-1}, F_{n-2}$のビット幅は`DW-1`とする（上記では32ビット: $DW = 32$）. また第1項と第2項は初期値としてレジスタに代入する. `ASI_VALID`によって演算が開始するタイミングでレジスタを初期化する. ### 加算器 加算器の構成は様々考えられるが, 単純に`+`演算子で表現することにしよう. VHDLでは代入の左辺と右辺は同じビット幅である必要があるので以下のように書く. ```VHDL fn <= ('0' & fnm1) + ('0' & fnm2); ``` ### ビジー信号 フィボナッチ演算をコントロールするためにビジー信号を実装する. ビジー信号が有効のときは演算を行い, 外部の入力を受け付けないようにする.ビジー信号によって演算が行われるように, レジスタにビジー信号を接続する. 上記のレジスタ部にビジー信号(`busy_i`)を追加すると以下のようになる. ビジー信号自体のコントロールには, 入力された演算回数をに到達したかチェックするカウンタが必要である. カウンタ`cnt`は演算回数をカウントするが, 演算は1`CLK`毎に行われるため, 通常のクロックカウンタである. 初期化処理によってレジスタに第1項と第2項が代入されるため, 演算は第3項から行われる. そのためカウンタは初期化によって3項目から計算するようにする. ### 完了信号 フィボナッチ演算の完了を通知し, 演算結果を有効にするための信号を実装する. 完了信号(`done_i`)は組み合わせ回路で実装する. ```VHDL done_i <= '1' when (busy_i = '1' and cnt > calc_n - 1) else '1' when (busy_i = '1' and calc_n < 3) else '0'; ``` 演算は3項目から始めるから, 入力された演算回数(`calc_n`)が3より小さい場合はレジスタの初期値を出力すればよい. 完了信号が有効のときに演算結果を出力するが, 複数クロック動作することによって出力結果が変化しないように完了時の結果を保持するようにしよう. 結果的にレジスタは以下のようになる. 入力された演算回数は演算開始時に保持する. 演算中に更新されないようにすること. ### インターフェースとの接続 このモジュールが出力する信号は以下の通り. - `ASI_READY` - `ASO_VALID` - `ASO_DATA` - `ASO_ERROR` `ASI_READY`はモジュールが入力可能かを示す. ビジー信号を反転すると入力可能を表すことができる. `ASO_VALID`は演算結果の出力有効である. 完了信号(`done_i`)に接続する. `ASO_DATA`は演算結果を出力する. 加算した結果を出力するが , ビット幅を合わせる必要がある. また入力された演算回数(`calc_n`)が3より小さい場合はレジスタの初期値を出力する. ```vhdl ASO_DATA <= first_term when (calc_n < 3) else fn(ASO_DATA'range); ``` ### エラー処理 `ASO_ERROR`は演算結果のエラーを通知する. ここでは以下の2つの場合にエラーを通知するようにする. - 加算結果のビットオーバーフロー - 入力された演算回数が演算可能の回数より多い場合 #### ビットオーバーフロー 加算結果のビットオーバーフローは加算によって生じた桁上げをそのまま通知する. なぜかまどろっこしいやり方をしているが, 今後のための冗長性だ. #### 入力エラー 入力された演算回数(`calc_n`)は入力(`ASI_DATA`)よりもビット幅が少ないため, 取りこぼしてそのまま違う演算結果を出力してしまう可能性がある. 対してビット幅を等しくしてしまうと, オーバーフローを起こすとわかっている演算に関してもカウンタがその値に達するまで演算を行ってしまう. そこで明らかにオーバーフローを起こすとわかっている演算回数が指定された場合に, 入力(`ASI_DATA`)を見てエラーとする. これら2つの論理和をとってエラーとして出力する. ## まとめ これでフィボナッチ数を演算する回路ができた. 例としてIntel Cyclone Vコンパイルした結果を以下に示す. ```text +-------------------------------------------------------------------------------+ ; Flow Summary ; +---------------------------------+---------------------------------------------+ ; Flow Status ; Successful - Wed Jan 29 21:57:42 2020 ; ; Quartus Prime Version ; 17.1.0 Build 590 10/25/2017 SJ Lite Edition ; ; Revision Name ; FIB ; ; Top-level Entity Name ; FIB ; ; Family ; Cyclone V ; ; Device ; 5CGXFC7C7F23C8 ; ; Timing Models ; Final ; ; Logic utilization (in ALMs) ; 42 / 56,480 ( < 1 % ) ; ; Total registers ; 80 ; ; 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 ; +------------+-----------------+------------+------+ ; 221.09 MHz ; 221.09 MHz ; CLK ; ; +------------+-----------------+------------+------+ ``` FPGAとしては非常に小さいモジュールだが, C言語のようなプログラムよりも遥かに高速に演算する事ができる. 実はフィボナッチ数の演算は過去の結果を利用するため, 並列化しづらくそのまま回路にしても高速化しない. それでも1クロックサイクルごとに演算が完了するため, 高速に演算することができる. ## ## 参考 [1]<a name="avmm_intel"></a> [3. Avalon Memory-Mapped Interfaces - Avalon Interface Specifications](https://www.intel.com/content/www/us/en/programmable/documentation/nik1412467993397.html#nik1412467936351) [2]<a name="avst_intel"></a> [5. Avalon Streaming Interfaces - Avalon Interface Specifications](https://www.intel.com/content/www/us/en/programmable/documentation/nik1412467993397.html#nik1412467963376) [3]<a name="ctistr_intel"></a> [Nios II Custom Instruction User Guide](https://www.intel.com/content/www/us/en/programmable/documentation/cru1439932898327.html?wapkw=nios%20custom) [4]<a name="fib_suguru"></a> [１００番目までのフィボナッチ数列 - すぐる学習会 -](http://www.suguru.jp/Fibonacci/Fib100.html)