HDLでFizzBuzz

プログラムの定番問題をHDLで解くには. <a name='more'></a> Wikipedia[[1](#wikipedia)]より > 最初のプレイヤーは「1」と数字を発言する。次のプレイヤーは直前のプレイヤーの次の数字を発言していく。ただし、3で割り切れる場合は「**Fizz**」（Bizz Buzzの場合は「**Bizz**」）、5で割り切れる場合は「**Buzz**」、両者で割り切れる場合（すなわち15で割り切れる場合）は「**Fizz Buzz**」（Bizz Buzzの場合は「**Bizz Buzz**」）を数の代わりに発言しなければならない。 有名なFizzBuzz問題をHDLで記述してみよう. ## プログラム C言語でFizzBuzz問題の主要なポイントを記述すると以下のようなものになる. ```c for (int i=0;i<max_num;i++) { if (i % 3 == 0 && i % 5 == 0) { printf("FizzBuzz\n"); } else if (i % 3 == 0) { printf("Fizz\n"); } else if (i % 5 == 0) { printf("Buzz\n"); } else { printf("%d\n", i); } } ``` 要点は2点. - 最大値(`max_num`)までのループ - 剰余による場合分け この2点をHDLに置き換えることを中心に考えていく. 実際に作ったもののgithubリポジトリは以下. <a href="https://github.com/toms74209200/FIZZ_BUZZ"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8uKtPH7tmLDNQTpuj40IXQmS2XErE5OCY-CN-hyTBnVz2QHxkzC8WGjzsD3EMjyzOIMLKC4ozBz2LsccAtdcYSK_cCXsFSKmlez-zGGItNs0n4-5bNWClZN9z-dxA4988-jns-GKQS0Th/s1600/65f7929e06734a7aa8738e7da595ef17.png" width="400px"></a> ## HDLでの実装 HDLで記述する場合, コンソールは使えない（シリアル通信などはFizzBuzz問題から逸脱する）ため, 代わりのインターフェースを考える. ### インターフェース | Name | I/O | P/N | Description | | -------------------- | ---- | ---- | --------------------------------------------------- | | RESET_n | I | N | Reset | | CLK | I | P | Clock | | SINK_READY | O | P | Sink data ready | | SINK_VALID | I | P | Sink data valid | | SINK_DATA[31:0] | I | P | Sink data: Max Fizz Buzz count | | SOURCE_VALID | O | P | Source data valid | | SOURCE_DATA[31:0] | O | P | Source data: Fizz Buzz count | | SOURCE_FIZZBUZZ[2:0] | O | P | Source Fizz Buzz selector(2:FizzBuzz,1:Buzz,0:Fizz) | 入出力はほとんどAvalon-STに従う. `SINK_VALID`が有効のときの`SINK_DATA[31:0]`の値をループの最大値として演算を行い, `SOURCE_DATA[31:0]`に値を出力する. ただし`SOURCE_FIZZBUZZ[2:0]`は`Fizz`, `Buzz`, `FizzBuzz`を選択する信号で, それぞれに対応するビットが立つ.  ### ループ `for`文によるループは`i`をインクリメントして活用するというところにポイントがある. そこでHDLではカウンタを用意してそのカウンタの値を参照する. `for`文内の初期化式 (`int i=0;`) と再初期化式 (`i++`) に当たる. 出力に使うので, カウンタの信号種別は`integer`ではなく`std_logic_vector`である. ```vhdl signal cnt : std_logic_vector(SINK_DATA'range); -- Fizz Buzz counter ~~ 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 + 1; end if; elsif (SINK_VALID = '1') then cnt <= cnt + 1; end if; end if; end process; ``` `for`文内の継続条件式 (`i<max_num;`) は, 上のHDLにおける`busy_i`信号と`done_i`信号の制御に対応する. `for`文では継続条件式が成り立つとき, 中の文を実行する. HDLでは`busy_i`信号をフラグとして他の回路を実行する. ```vhdl signal done_i : std_logic; -- Fizz Buzz end signal busy_i : std_logic; -- Fizz Buzz busy ~~ -- ============================================================================ -- Fizz Buzz end -- ============================================================================ done_i <= '1' when (busy_i = '1' and cnt = cnt_max) else '0'; -- ============================================================================ -- Fizz Buzz count busy -- ============================================================================ process (CLK, RESET_n) begin if (RESET_n = '0') then busy_i <= '0'; elsif (CLK'event and CLK = '1') then if (done_i = '1') then busy_i <= '0'; elsif (SINK_VALID = '1') then busy_i <= '1'; end if; end if; end process; ``` ### 剰余による場合分け C言語のプログラム例では剰余によって場合分けをしているが, 本来求めたい3の倍数・5の倍数かを判別するにはいくつか方法がある. 1. 実際に除算を行う（剰余を求める） 2. 倍数カウンタを使ってその倍数のときにフラグを立てる 3. 除算を小数点の乗算に直す 1.は回路規模が大きく, また演算時間もかかる. 今回は3と5とで2回除算を行わなければならないため, 現実的でない. 2.は調べたい数が大きくなると演算時間も増大するが, 今回の場合は`cnt`のインクリメントに合わせて倍数カウンタを動かせばよいので, 演算時間は影響しない. この方法は『素数カウンタ』[[2](#prime_hdl)]のときに採用したので, 今回は使わない. 3.は除算の除数が定数のときのみ使える. 例えば$1/3$は小数で表すと$0.33 \cdots$である. これを被除数にかければ, 3の除算が行えたことになる. 16進数に直すと$1/3 = 0.33 \cdots$は0x555...になる（小数点位置はMSB）. $30 \times 0.333$を16進数に直すと以下のように計算できる. ```textplane 1E(0d30) *) 0.5555(0d0.333) --------- 9.FFF6 ``` ビット幅を考慮すると小数点以下8桁が0xFFであれば（根拠はない）, 余りがないといえる. よって数が3の倍数および5の倍数かどうか判別するには, $0.33 \cdots$ (0x55...) と$0.55 \cdots$ (0x33...) とをそれぞれかけて小数点以下が$0.99 \cdots$ (0xFF...) かどうかを判別すればよい. これをHDLにすると以下のようになる. ```vhdl constant FixedNum1d3 : std_logic_vector(SOURCE_DATA'range) := X"5555_5555"; -- 1/3 fixed point representation(Q32) constant FixedNum1d5 : std_logic_vector(SOURCE_DATA'range) := X"3333_3333"; -- 1/5 fixed point representation(Q32) ~~ signal product_3i : std_logic_vector(cnt'length*2-1 downto 0); -- Multiple product 1/3 signal product_5i : std_logic_vector(cnt'length*2-1 downto 0); -- Multiple product 1/5 ~~ -- ============================================================================ -- Multiplier -- ============================================================================ process (CLK, RESET_n) begin if (RESET_n = '0') then product_3i <= (others => '0'); product_5i <= (others => '0'); elsif (CLK'event and CLK = '1') then if (busy_i = '1') then product_3i <= cnt * FixedNum1d3; product_5i <= cnt * FixedNum1d5; elsif (SINK_VALID = '1') then product_3i <= (others => '0'); product_5i <= (others => '0'); end if; end if; end process; -- ============================================================================ -- Fizz Buzz selector -- ============================================================================ fizz_buzz_i <= "100" when (product_3i(cnt'left downto cnt'left-15) = X"FFFF" and product_5i(cnt'left downto cnt'left-15) = X"FFFF") else "010" when (product_5i(cnt'left downto cnt'left-15) = X"FFFF") else "001" when (product_3i(cnt'left downto cnt'left-15) = X"FFFF") else (others => '0'); ``` ここで判別したい数 (`cnt`) と除数を小数にしたもの (`FixdNum1d*`) のビット幅は32のため, これらの積は64ビットになる. また除数を小数にしたもの (`FixdNum1d*`) の小数点位置はMSB (32) だから積の小数点位置は31ビット目にあたる. 条件は31ビット目以下16ビットが0xFFFFかどうかである. ## シミュレーション コンソールでそれっぽく表示させるために, テストベンチシミュレーションを使う. テストベンチのソースはVHDLだと記述がややこしいので, SystemVerilogを使う. といってもとくに特別な操作は必要なく, `SOURCE_FIZZBUZZ` に合わせて出力する文字列を変えるだけだ. これをコマンドラインで実行すると, プログラムで作ったFizzBuzzと同じような出力を得られる. もしFPGA実機で実行するとその実行時間はクロックの周波数に依存して, クロック毎にFizzBuzzに対応する出力を行う. シリアル通信などを使ってコンソールに出力すると, 当然その通信がボトルネックになる. そのためこの通信を加味するとCPUよりも実行時間は長くなるだろう. FPGAの場合はこういった通信がボトルネックになることが多い. ## 参考 [1]<a name="wikipedia"></a> [Fizz Buzz - Wikipedia](https://ja.wikipedia.org/wiki/Fizz_Buzz) [2]<a name="prime_hdl"></a> [toms.log: ハードウェアで素数を数える](https://toms-log.blogspot.com/2019/03/blog-post_18.html)