HDLでFizzBuzz

プログラムの定番問題をHDLで解くには.

Wikipedia[1]より

最初のプレイヤーは「1」と数字を発言する。次のプレイヤーは直前のプレイヤーの次の数字を発言していく。ただし、3で割り切れる場合は「Fizz」（Bizz Buzzの場合は「Bizz」）、5で割り切れる場合は「Buzz」、両者で割り切れる場合（すなわち15で割り切れる場合）は「Fizz Buzz」（Bizz Buzzの場合は「Bizz Buzz」）を数の代わりに発言しなければならない。

有名なFizzBuzz問題をHDLで記述してみよう.

プログラム

C言語でFizzBuzz問題の主要なポイントを記述すると以下のようなものになる.

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リポジトリは以下.

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である.

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信号をフラグとして他の回路を実行する.

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]のときに採用したので, 今回は使わない. 3.は除算の除数が定数のときのみ使える. 例えば$1/3$は小数で表すと$0.33 \cdots$である. これを被除数にかければ, 3の除算が行えたことになる. 16進数に直すと$1/3 = 0.33 \cdots$は0x555...になる（小数点位置はMSB）. $30 \times 0.333$を16進数に直すと以下のように計算できる.

       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にすると以下のようになる.

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 に合わせて出力する文字列を変えるだけだ.

	if (SOURCE_FIZZBUZZ == 3'b100)
	$display("FizzBuzz");
	else if (SOURCE_FIZZBUZZ == 3'b010)
	$display("Buzz");
	else if (SOURCE_FIZZBUZZ == 3'b001)
	$display("Fizz");
	else
	$display("%0d",SOURCE_DATA);

view raw fizzbuzz_disp.sv hosted with ❤ by GitHub

これをコマンドラインで実行すると, プログラムで作ったFizzBuzzと同じような出力を得られる.

もしFPGA実機で実行するとその実行時間はクロックの周波数に依存して, クロック毎にFizzBuzzに対応する出力を行う. シリアル通信などを使ってコンソールに出力すると, 当然その通信がボトルネックになる. そのためこの通信を加味するとCPUよりも実行時間は長くなるだろう. FPGAの場合はこういった通信がボトルネックになることが多い.

参考

[1] Fizz Buzz - Wikipedia

[2] toms.log: ハードウェアで素数を数える