はじめに
これまで「Shrike-LiteでAtCoderを解く」では、小さな実在FPGAへAtCoder問題を実装してきました。
でも実機には限界があります。LUTもFFもBRAMも有限です。
そこで今回は、いったん現実を忘れます。
面積が無限にある理想的なFPGAなら、AtCoderの問題はどう見えるんだろう？
LUTが1億個欲しければ置く。FFが10億個欲しければ置く。2300個並列にしたければ2300個並べる。
そんな 仮想理想FPGA 用のVerilogコードを書き、Icarus vvp環境でシミュレートしてみます。
このシリーズで遊びたいのは、
計算機を変えると、同じ問題がどう見えるのか
です。
最初の題材はABC471Gです。
ABC471GをFPGA目線で読む
ちょっと不思議な問題文ですね。
音節とか、母音とか、競プロ的ではない単語が並んでいます。
V[j]=1なら母音、0なら非母音。
数列 A[i] に対し、各 k=0...K-1 について、
A'[i] = (A[i] + k) mod K
と変換したときの音節数を求めます。
最大は、
N <= 7,000,000
K <= 2,300
です。
音節数って、要するに何？
問題を一読しただけでは、いまひとつ何をすればいいのかわかりません。
そんなときの鉄則、入力例をサンプルにして、手作業で問題の指示通りに操作をしてみます。
試しに入力例1を使ってみましょう。
N = 4
K = 6
A = [4, 2, 4, 1]
V = [1, 1, 0, 0, 1, 0]
V[j]に従って、k = 0の時の、Aの要素を置き換えてみます。
A[0] = 4ですから、最初の要素は V[4] = 1です。
同様に
A[1] = 2 -> V[2] = 0
A[2] = 4 -> V[4] = 1
A[3] = 1 -> V[1] = 1
です。完成した母音と非母音の列は
1 0 1 1
です。
この記号列の音節数を求めれば、k = 0の時の答えになります。
音節数は 1の出現回数、ただし、1が連続して出現する場合は、その部分をまとめて1回と数えます、というような指示がありますから、
記号列 1 0 1 1 の音節数は 2
です。
この変換とカウントの作業をk = 1, 2, .., 5まで繰り返せばすべての答えが得られます。つまり
k = 1 のとき、A' = [5, 3, 5, 2]
k = 2 のとき、A' = [0, 4, 0, 3]
k = 3 のとき、A' = [1, 5, 1, 4]
k = 4 のとき、A' = [2, 0, 2, 5]
k = 5 のとき、A' = [3, 1, 3, 0]
に対して、V[j]で0/1列への変換を行い、音節数をそれぞれカウントすればいいのです。
音節数のカウント方法は？
さて、それではどうやって音節数をカウントすればいいのでしょうか。
直感的に「新しい1の列が始まったら1音節カウント加算」すればいいのではないか、とすぐに思いつくでしょう。
つまり、
音節数 = 0 -> 1 の立ち上がり回数
でよさそうです。
なんだ。
FPGAでは急に見慣れた問題になりました。
いわゆる立ち上がりエッジカウンタです。
立ち上がりエッジの検出は 直前が 0 で、現在が 1を見つければ十分ですね。
つまり k = 0, 1, ..., K - 1 に対して、
current = V[(A[i]+k)%K]
rise = current & ~prev
でよい。
rise=1ならcounterを増やし、prev=currentとして次へ進みます。
思ったより簡単なんじゃないの？
G問題がそんなに簡単なわけないでしょ
さて、問題の理解と愚直解法のアイデアは手に入りました。
でもG問題ですから、愚直解法で間に合うはずがありません。
まずは愚直解法の最大計算量を見積もってみましょう。
問題入力の作成は面倒そうな計算をしていますが、N回ループを回せばAを生成できそうです。
そして生成されるAの最大長Nは700万要素！ 70万じゃなくて700万です。
この700万要素のAについて、kを変えて得られる最大2300通りのA'が愚直解法の対象です。
700万 x 2300 = 161億要素。
これをV[j]で置換してから、隣り合う2要素を順に見て立ち上がりエッジを検出し、検出数をカウントすれば愚直回答の出来上がりです。
入力生成から計算完了まで、O(N) + O(NK) ですから、計算量O(NK)ですね。
161億要素の検査ですから、さすがに5秒で回すのは厳しそうです。
でも、「161億もあるからどうにもならない」というほど桁違いの量でもないような気がします。
いや、仮想理想FPGAならどう？
普通のCPUで愚直解法だと、kをループすることになります。
でも今、我々が頭に浮かべているのは仮想理想FPGAです。
最大K 2300個？
2300個程度なら2300個並べればいいんじゃない？
A[i]
|
+-----------------+-----------------+
| | |
k=0 k=1 ... k=2299
| | |
(A[i]+0)%K (A[i]+1)%K ...
| | |
V[...] V[...] ...
| | |
0->1検出 0->1検出 ...
| | |
counter[0] counter[1] ...
面積？ 配線？
知りません。
仮想理想FPGAです。
これなら各レーン700万要素の検査で済みますから、おおよそ700万クロック、50MHz換算で140ms程度で処理できそうな気がします。
2300並列版の構成を考える
並列に設置した2300レーンそれぞれに
prev[k] : 1bit
counter[k] : 32bit
を持たせ、1個のAを全レーンへ配ります。
それだけです。すごく簡単。
2300並列版を実装してみる
今回もVerilog実装には全面的にCodexさんのご協力を仰ぎました。
実装例と実装仕様の資料は以下にアップロードしています。
完成したVerilogコードをIcarus Verilogでコンパイルし、vvpで実行して動作確認を行います。
公式例、小規模代表、ランダムケースを別に作成したPythonコードの結果と参照比較してPASS。
ほら、やっぱり簡単じゃん。
※ 本記事のテストや測定はすべて筆者のローカル環境(Win 11, i7-12700H, MEM 64GB)で行っています。
Icarusで動かしてみよう
さて、Icarus Verilog / vvpでのシミュレーションを続けます。
K=2300のままNをどんどん増やしていきます。
N=1000から始めて、5分待っても答えが返ってこなくなったらストップ、の仕組みです。
| N | logical clock | vvp実時間 | 結果 |
|---|---|---|---|
| 1,000 | 1,000 | 4.555秒 | PASS |
| 10,000 | 10,000 | 45.427秒 | PASS |
| 100,000 | 100,000 | 300秒 | TIMEOUT |
あら。N = 10万で5分タイムアウトしました。
最後に完走したN = 10,000の測定値からN = 700万のときの処理時間を単純に線形で推測すると、
約31,799秒 = 約8時間50分
……。
仮想理想FPGAなら0.14秒相当なのに、vvpでは約9時間予想。
Icarus、飛べてません。
何が起きた？
Verilog上では2300個の回路を並べました。
でもvvpが動いているのは普通のCPUです。
Verilog:
2300個の回路が同時並列に動く
vvp:
巨大な2300レーン回路をCPUで順に評価する
要するに、
2300並列って書いても、Icarus SIMでは2300個ぶん逐次処理してるよね。
仮想理想FPGAには軽かった翼が、Icarusには重すぎました。
2300個とも似た仕事をしている
少し考えてみると、各レーンが欲しいのは、
current[k] = V[(A[i]+k)%K]
です。
2300個の別問題を解け、ではなく、そっくりな2300個の問題を同時処理しろ、です。
ということは、
2300個を、Icarusがまとめて扱いやすい形へ変えられない？
これから仮想理想FPGAの世界に、少しだけIcarusの都合を反映させてみます。
次回
次回は、仮想理想FPGAの愚直解法を改造しながら、Icarus vvp環境でどこまで処理時間を短縮できるか、にチャレンジします。
Fly! Icarus, Fly High!
以前の仮想理想FPGA関連記事：
Shrike-LiteでAtCoder問題を解く(32)：Detour：ABC470A - 公式ジャッジにVerilogで参加してみる
Shrike-LiteでAtCoder問題を解く(33)：Detour：ABC470D(前編) - 仮想理想FPGAなら何クロックで解ける？
Shrike-LiteでAtCoder問題を解く(34)：Detour：ABC470D(後編) - 50万クエリ、結局ひとつの変換じゃない？
次回：
仮想理想FPGAでAtCoderを解く(2) - ABC471G② - Fly! Icarus, Fly High!
コード全文と実装資料：(コード実装やドキュメント作成は生成AIの助けを借りています)
第1回コード全文と実装資料