フィボナッチをFPGAで書いてみた

とんぷーさんが書いたGoで再帰使うと遅くなりますがそれが何だがとてもためになった。これを読んでたら、FPGAでフィボナッチを書いてみたくなったのでやってみた。再帰ではなくてループを使ったので比較はできないけれど、50MHzクロックのFPGAで、fib(42)は5.5usで計算できた。

ステッカーは中身とあんまり関係ないのだ

JavaでFibを書く

今回は手っ取り早くJavaで書いて、Synthesijer (sjr)でHDLに落とすことにした。こんなコード：

Fib.java

public class Fib {

	public int result;
	
	private int fib(int n) {
		int cur = 0, next = 1;
		for (int i = 0; i < n; ++i) {
			int tmp = cur;
			cur = next;
			next += tmp;
		}
		return cur;
	}

	public void run() {
		result = fib(42);
	}
}

まずはJava上でこれを実行して動作確認。その後、sjrにかけるとFib.vという長いVerilog HDLファイルが生成される。これで本体は完成。

実行時間の計測

でも、これ一体どの程度の速さで動くのだろう？ それを確かめるため、フィボナッチ計算に何クロックかかったかを計測してLEDに表示する簡単なコードをVerilog HDLで書いた。こんな具合：

Top.v

reg [31:0] timer;

always @(posedge clk or posedge reset) begin
  if (reset) begin;
    timer <= 32'd0;
  end else if (result != 32'd267914296) begin // fib(42) = 267914296
	   timer <= timer + 32'd1;
  end
end

Fibの出力結果が267914296になるまでクロックの数を数えて、LED表示する仕組み。

回路合成・実行

こうしてHDLファイルがひと通り用意できたら、Altera Quartus IIを使って回路合成し、FPGAボードのDE0にロードする。フィボナッチ数の計算がすぐに始まって、上記写真のようにLED上に「191」と表示された。10進数で401クロック。1クロックは50MHz = 20nsなので、401 x 20 = 8020ns つまり8usで計算できたことになる。

3/9追記

みよしさんがsjrの最適化をアップデートしてくれたので、最新版（20150307）で試してみたら、273クロック＝5.46usに短縮された！

まとめ

ハード開発のプロの人が生HDLで書いてクロック上限を追い込めば、もっと速くなるはず。でもまあ、ハード素人がJavaでさくっと書いて遊べるsjrはあいかわらずすばらしいと思った。

今回のコードはこちら。