はじめに

これまで「Shrike-LiteでAtCoderを解く」では、小さな実在FPGAへAtCoder問題を実装してきました。

でも実機には限界があります。LUTもFFもBRAMも有限です。

そこで今回は、いったん現実を忘れます。

面積が無限にある理想的なFPGAなら、AtCoderの問題はどう見えるんだろう？

LUTが1億個欲しければ置く。FFが10億個欲しければ置く。2300個並列にしたければ2300個並べる。

そんな 仮想理想FPGA 用のVerilogコードを書き、Icarus vvp環境でシミュレートしてみます。

このシリーズで遊びたいのは、

計算機を変えると、同じ問題がどう見えるのか

です。

最初の題材はABC471Gです。

ABC471GをFPGA目線で読む

ABC471 G - Caeser Syllables

ちょっと不思議な問題文ですね。

音節とか、母音とか、競プロ的ではない単語が並んでいます。

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さんのご協力を仰ぎました。

実装例と実装仕様の資料は以下にアップロードしています。

第1回コード全文と実装資料

完成した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回コード全文と実装資料