はじめに
前回は、ABC470BをShrike-Liteへ実装しました。
今回はABC470Aを見ていたのですが、問題そのものとは別のところで気になるものを見つけました。
AtCoderの提出言語にVerilogがある。
昔AtCoderを触っていたころ、こんな選択肢は見た記憶がありません。
しかも現在の実行環境を見ると、
- Verilog 2012
- Icarus Verilog 12.0
- コンパイル：
iverilog - 実行：
vvp
となっています。
つまり、普通にVerilogのコードを提出して公式ジャッジへ参加できるようです。
これはやってみるしかありません。
まず標準入出力をどうするんだ
競技プログラミングで新しい言語を使うと、最初に立ちはだかるのはだいたいアルゴリズムではありません。
標準入力をどうやって読むんだ？
今回もそこから始まりました。
Cならscanf、Pythonならinput()でいいのですが、Verilogで標準入力と言われても困ります。
普段のVerilogなら、入力はこんな感じです。
input wire [7:0] data;
いや、そうじゃない。
AtCoderは標準入力から数字を送ってきます。
少し調べると、Icarus Verilogでは標準入力をファイルディスクリプタとして扱えます。
integer n;
integer rc;
rc = $fscanf(32'h80000000, "%d", n);
Icarus Verilogの実装でも、0x80000000はSTDINとして扱われています。
出力はもっと簡単で、
$display("%0d", n);
で標準出力へ出せます。
これで競プロができそうです。
ところでIcarusってことは……
ここで別の疑問が出てきました。
これはFPGAへ合成するわけではありません。
Icarus Verilogでシミュレーションするだけです。
ということは、
回路面積の制限がないのでは？
さらに、
initial begin
// いろいろ処理
end
の中で#10のような遅延も、posedge clkのようなイベント待ちも書かなければ、シミュレーション上は全部同じ時刻に処理されます。
つまり……
実質無限面積、処理時間ゼロの理想FPGAが爆誕したのでは？
かなり怪しい話になってきました。
もちろん現実にはIcarus Verilogを動かしているCPUが処理しているので、本当に時間がゼロになるわけではありません。
AtCoder側でも、生成されたプログラムはvvpで実行されます。
したがって競うことになるのは、回路のクロック周波数ではなく、
Icarus Verilogがそのシミュレーションを何秒で処理できるか
ということになりそうです。
これはもう、いつものFPGAとはかなり違います。
ABC470Aをやってみる
今回のお題はABC470A - Fizzです。
正の整数Nが与えられ、1からNまで順番に、
- 3の倍数なら
Fizz - それ以外なら数字
を出力します。
Nは最大100です。
普通のプログラミング言語なら、ほとんど説明することもない問題です。
ではVerilogで書いてみます。
module Main;
integer n;
integer i;
integer rc;
initial begin
rc = $fscanf(32'h80000000, "%d", n);
for (i = 1; i <= n; i = i + 1) begin
if (i % 3 == 0)
$display("Fizz");
else
$display("%0d", i);
end
end
endmodule
……書けました。
何でしょう、この感じ。
integerがあって、
forがあって、
ifがあって、
剰余演算して、
$displayする。
妙なC言語を書いている気分です。
FPGAを作っている感じがほとんどありません。
コードテストで動かしてみる
まずはAtCoderのコードテストで試してみます。
入力はサンプルの、
10
です。
期待する出力は、
1
2
Fizz
4
5
Fizz
7
8
Fizz
10
です。
実行。
……
出ました。
普通に動きます。
VerilogがAtCoderの標準入力を読み、答えを標準出力へ出しています。
ワクワクします。
しかし何かがおかしい
動いたのですが、かなり違和感があります。
いつものFPGAなら、
- 何bitで値を持つか
- どのクロックで動かすか
- 1クロックでどこまで計算するか
- FSMをどう構成するか
- LUTやFFをどれだけ使うか
といったことを考えます。
今回は何も考えていません。
integerを用意してforで回しただけです。
しかもクロックすらありません。
これは「FPGAでABC470Aを解いた」と言ってよいのでしょうか。
少なくとも、これまでShrike-Liteでやってきたこととはかなり違います。
Icarus VerilogはHDLのシミュレータです。
回路を作って実行しているというより、
Verilogで書いたシミュレーション記述をCPUで実行している
と考えたほうが実態に近そうです。
理想FPGAが誕生したと思ったら、どうもそうではありませんでした。
ただし、これはこれで面白い。
次回
今回は、とりあえずAtCoderのコードテストでVerilogが動くところまで確認しました。
しかし、せっかくVerilogを使うなら、
always @(posedge clk)
ぐらいは書きたいところです。
次回はABC470Dを題材に、クロックという概念をAtCoderへ持ち込んでみます。
果たして、競技プログラミングの2秒という制限時間と、Verilogシミュレーション上のクロックはどういう関係になるのでしょうか。
Shrike-Liteとは何の関係もない話ですが、もう一回寄り道をしますね。
前回：
Shrike-LiteでAtCoder問題を解く(31)：ABC470B - DistRAMで色を数える
次回：
Shrike-LiteでAtCoder問題を解く(33)：Detour：ABC470D - 仮想理想FPGAなら何クロックで解ける？