はじめに
前回は、ABC471の各問題をFPGA目線で眺めました。
今回は小手調べとして、A問題「Nine or Nein」をShrike-Liteへ実装します。
A問題なので処理そのものは簡単です。
今回は、4つの条件を順番に計算するのではなく、4つとも並列に判定する回路にしてみます。
問題
正の整数A,Bが与えられます。
次の値のうち、少なくとも1つが9ならNine、そうでなければNeinです。
A + B
A - B
A * B
A / B
制約は、
1 <= A <= 100
1 <= B <= 100
です。
4つとも同時に判定する
ソフトウェアなら、4つの式を順番に評価しても十分です。
FPGAなので、今回はそれぞれの判定回路を並べます。
┌─ A+B == 9 ─┐
├─ A-B == 9 ─┤
A, B ────────┼─ A*B == 9 ─┼─ OR ─→ Nine / Nein
└─ A/B == 9 ─┘
ただし、このためだけに汎用の乗算器や除算器を作る必要はありません。
乗算
正の整数どうしの積が9になる組は、
1 * 9
3 * 3
9 * 1
だけです。
したがって、3組との比較だけで判定できます。
除算
Bは正なので、
A / B == 9
は、
A == 9 * B
と考えられます。
さらに、
9 * B = (B << 3) + B
なので、乗算器も不要です。
減算も、
A - B == 9
ではなく、
A == B + 9
として判定します。
RTL
判定部分の実装は次のようになりました。
wire sum_nine;
wire sub_nine;
wire mul_nine;
wire [10:0] b_times_nine;
wire div_nine;
wire nine_result;
assign sum_nine = (a_reg + b_reg) == 8'd9;
assign sub_nine = a_reg == (b_reg + 8'd9);
assign mul_nine = ((a_reg == 8'd1) && (b_reg == 8'd9)) ||
((a_reg == 8'd3) && (b_reg == 8'd3)) ||
((a_reg == 8'd9) && (b_reg == 8'd1));
assign b_times_nine = ({3'b000, b_reg} << 3) + {3'b000, b_reg};
assign div_nine = {3'b000, a_reg} == b_times_nine;
assign nine_result =
sum_nine |
sub_nine |
mul_nine |
div_nine;
別々の組み合わせ回路で4種類の判定を同時に行い、結果のORを出力しています。
SPI通信
今回もSPIテンプレートV3を使います。
SPIクロックは4MHzです。
入力はA,Bともに1byteで収まるので、そのまま2byteで送ります。
byte 0 : A
byte 1 : B
回答も1bitあれば十分なので、STATUSと同じ1byteへ押し込みました。
bit 7 : VALID
bit 6 : ERROR
bit 5:1 : 0
bit 0 : ANSWER
正常時は、
0x80 : Nein
0x81 : Nine
です。
VALIDが立ったbyteに答えも入っているので、回答を取りに行くための追加転送はありません。
実装とテストはCodexへ
今回は先にSPEC_abc471a.mdを作り、SPIテンプレートV3と直前のABC468C実装を参照資料として置いたうえで、Codexへ実装を依頼しました。
実装対象は主に、
ffpga/src/main.v
firmware/micropython/abc471a_test.py
です。
spi_target.vと参照資料は変更しない条件にしました。
ホスト側の実装とテストは約7分で完了しました。
AとBはそれぞれ1..100なので、組み合わせは全部で10,000通りしかありません。
そこでIcarus Verilogで全組み合わせを総当たりチェックしています。
SUMMARY EXHAUSTIVE_CASES=10000 PROTOCOL_CASES=6 FAILURES=0 PASS
範囲外入力などのプロトコルテストも合わせてPASSしました。
合成結果
ForgeFPGA Workshopで合成し、Shrike-Liteへ書き込みました。
面積には十分な余裕がありますね。
50MHz制約に対して、到達可能クロックは80.25MHz、タイミングも余裕があります。
実機テスト
MicroPython側では、公式4例に加えて各演算条件、境界値、エラーケースなど20ケースを実行しました。
結果は、
SUMMARY TOTAL=20 PASS=20 FAIL=0 PASS
となりました。
回答時間は2ms程度で収まっています。ACが取れそうですね。
まとめ
ABC471AをShrike-Liteへ実装しました。
A問題らしい、小さくて素直な専用回路になったと思います。
次はE問題に挑戦する予定です。
こちらは998244353のモジュラ計算が入ってくるので、今回ほど素直にはいかなさそうです。
おまけ：AtCoder提出用Verilog
せっかくなので、AtCoderへ提出できるVerilogのコードサンプルも置いておきます。
クロックも遅延も一切考慮しない、Icarus vvp環境にやさしいコードです。
module main;
integer A, B;
integer ret;
reg nine;
initial begin
ret = $fscanf(32'h80000000, "%d %d", A, B);
nine =
(A + B == 9) ||
(A - B == 9) ||
(A * B == 9) ||
(A == 9 * B);
if (nine)
$display("Nine");
else
$display("Nein");
end
endmodule
Verilogのintegerは32bit符号付き整数なので、減算結果が負数になる場合への配慮はいりません。
ただし、Verilogの整数除算でA / B == 9と書くと、たとえば37 / 4 == 9も真になってしまいます。
そのため、Shrike-Lite実装と同じくA == 9 * Bへ変形しています。
上記コードをAtCoderのコードテストで走らせてみると20ms程度で実行完了するみたいです。
前回：
Shrike-LiteでAtCoder問題を解く(35)：Interlude - ABC471の各問題をFPGA目線で見てみる
次回：
Shrike-LiteでAtCoder問題を解く(37) ABC471E（前編） - レジスタ数個なら入ると思った
コード全文と実装資料：(今回もコード実装やそのドキュメント化は生成AIの助けを借りています)
第36回コード全文と実装資料