前回
仮想理想FPGAでは、
2300個なら2300個並べればいい
で済みました。
論理時間は700万clock、50MHzなら約0.14秒相当。
ところがIcarus vvpではN=700万ケースの所要時間が約8時間50分予測。
朝イチで計算を始めても、最大ケースでは定時に終わらないかもしれません。
そこで、同じ計算をIcarus向けに変形して高速化を図ってみます。
※ 今回のコードや実装資料はGithubに上げてあります。文末のリンクからご参照ください。
※ 本記事のテストや測定はすべて筆者のローカル環境(Win 11, i7-12700H, MEM 64GB)で行っています。
高速化①: 2300個のlookupを一つにまとめる
仮想理想FPGAでは2300本の個別回路がそれぞれA'[i]からV[A'[i]]への変換を組み合わせ回路で一気に行います。
しかしIcarusのSIM環境では、2300個の変換を個別にシミュレーションするため、この部分がかなり重くなっているようです。
そこで、この変換をIcarusがまとめて処理しやすいようにVerilog記述を変更します。
変更には、次の特性を利用します。
A'[i]をk=0, 1, 2,...の順番に並べてからV[A'[i]]に変換すると、かならずVの要素の循環になっている
具体例で見てみる
直感的にわかりづらいかも、と思いますので、具体例を公式入力例1で示しますね。
N = 4
K = 6
V = [1, 1, 0, 0, 1, 0]
A'(k=0) = [4, 2, 4, 1] = A
A'(k=1) = [5, 3, 5, 2]
A'(k=2) = [0, 4, 0, 3]
A'(k=3) = [1, 5, 1, 4]
A'(k=4) = [2, 0, 2, 5]
A'(k=5) = [3, 1, 3, 0]
N = 4, K = 6ですから、6レーンの並列回路に4回データが入ってくる、という問題です。
まず、各レーンに入る1回目の入力だけを横に並べます。
k=0 4
k=1 5
k=2 0
k=3 1
k=4 2
k=5 3
→ [4, 5, 0, 1, 2, 3]
これをVで変換すると、
[V[4], V[5], V[0], V[1], V[2], V[3]]
= [1, 0, 1, 1, 0, 0]
です。
つまりA[0]=4なら、
V[4], V[5], V[0], V[1], V[2], V[3]
と、Vを4番から順番に一周した並びになります。
2回目の入力も同じです。
A[1]=2なので、
V[2], V[3], V[4], V[5], V[0], V[1]
となります。
だったら、毎回2300個のV lookupを行わなくてもよさそうです。
そこで、あらかじめVを二つ連結したVVを作ります。
VV = [V, V]
= [V[0], V[1], V[2], ..., V[5], V[0], V[1], V[2], ... ,V[5]]
= [1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0]
そうすれば最初の入力を受け取ったIcarusは A[0] = 4を見るだけで、VV[4], VV[5], VV[6], VV[7], VV[8], VV[9]を各レーンに配ることができます。
いままで1回分の6入力が来るたびに6個のV lookupを個別に処理していましたが、これならVVから6bitをまとめて取り出す処理として記述できます。
2300レーンbitsetなら
最大K=2300なら、
V = 2300bit
VV = 4600bit
あとはA[i]に対応する位置から2300bit抜けば、
current[2299:0]
を一気に作れます。
2300個の判定器が、1個の2300bitベクタ生成器になりました。
高速化②: 立ち上がり検出も2300bitベクタにする
高速化①では、2300個のV lookupを4600bitのVVからまとめて取り出す形へ変更しました。
次のターゲットは立ち上がり検出回路です。
ここも仮想FPGAでは2300個の独立回路がそれぞれに検出を行う仕組みですが、Icarusでは2300レーンを巡回しながら処理を行っているはずです。
立ち上がり検出は「ひとつ前の値 = 0」かつ「今の値 = 1」であれば、立ち上がりとみなします。
先ほど、AからVへの変換出力を2300 bitsetにしましたから、bit演算を利用すれば、そのまま2300bitの値を使えそうです。
前の2300bit値を prev、今の2300bit値を currentとして、
(NOT prev) AND current
のbit演算結果がそのまま立ち上がり検出出力。
演算終了後
prev = current
として、次の入力に備える。
ここはシンプルな変更で済みそうです。
結果発表：二つの2300bit化は効いた？
さて、2300bit効率化の話を二つも読んでもらったので、ここで一度結果を見てみましょう。
K=2300, N=10,000では、
変更前 45.427秒
変更後 17.655秒
約2.6倍速くなりました。
おお。
ちゃんと効いてます😁
さらに変更前はN=100,000で300秒TIMEOUTでしたが、今回は、
N=100,000 174.193秒
で完走しました。
では最大ケースN=7,000,000はどのくらいになりそうでしょうか。
最後の完走点から単純に線形外挿すると、
変更前 約8時間50分
変更後 約3時間23分
5時間以上縮まりました。
朝イチで1回、午後にもう1回。
それでもまだ業務時間内です😂
なお、ここまで解法そのものは変えていません。
やっていることは、同じ愚直解法をIcarusが処理しやすいVerilog記述へ変えただけです。
高速化③: 2300個の立ち上がりカウンタを集約する
さて、AからVへの変換と立ち上がり検出回路は、2300bit値をまとめて一度に計算する、という方式に変更できました。
しかし、検出回数をカウントする回路は、まだ2300レーンそれぞれにあるカウンタが担当しています。
それらのカウンタは最大値700万が十分入るように32bit幅を持っています。
Icarusは2300個の多bit加算器を毎入力ごとに巡回処理しているはずです。
そこでカウンタもまとめて処理できる方法を考えてみます。
カウンタをbit単位で持つ
いままでは「2300本のレーン」それぞれに32bitカウンタを一つずつ用意していました。
これを「カウント数集計の32bit」それぞれに2300bitカウントプレーンを一つ用意することにします。
と突然言われても、直感的にわかりにくいと思いますので、例を挙げて説明します。
2300個の32bitカウンタは「0番レーンのカウントは1,000,000、1番レーンのカウントは999,995、...、2299番レーンのカウントは1,000,005」のようなそれぞれのカウント値を2進数で持っています。
ここでそれぞれのカウンタが持つデータをbit単位でみると、
0番カウンタ 1,000,000 = b'00000000 00001111 01000010 01000000
1番カウンタ 999,995 = b'00000000 00001111 01000010 00111011
2番カウンタ 999,997 = b'00000000 00001111 01000010 00111101
：
2299番カウンタ 1,000,005 = b'00000000 00001111 01000010 01000101
です。32bitカウンタが2300個ですね。
これを、縦方向に2300個ずつ固めます。上の例だと、
bit0 (1の位)カウントプレーン [0, 1, 1, ..., 1] (2300要素)
bit1 (2の位)カウントプレーン [0, 1, 0, ..., 0] (2300要素)
bit2 (4の位)カウントプレーン [0, 0, 1, ..., 1] (2300要素)
：
bit31 (2^31の位)カウントプレーン [0, 0, 0, ..., 0] (2300要素)
のように、2300レーンのカウント値を位ごとに集約した、32個のカウントプレーンに置き換えます。
上記例ではわかりやすくするために配列表記にしましたが、実際には 10101100.... のような2300桁bitsetがカウントプレーンの中身です。
それでどうするの？
この32個の各桁ごとの2300bitカウントプレーンにはそれまでの各レーンのカウント数情報が入っています。
そこに立ち上がり検出の結果として2300 bitsetの値が到着します。これをrise（立ち上がり）と呼びましょう。
riseの2300bitがあらわしているのは「どのレーンのカウンタに +1するか」の情報です。
rise[p] = 1 なら p番レーンのカウントを +1
rise[p] = 0 なら p番レーンはそのまま
さて、この仕組みでうまく計算を行うために、内部的にもうひとつ2300 bitsetのレジスタを用意します。
carry（繰り上がり）bitsetです。同じく2300bit幅にします。
これで計算の下準備は完了です。
これで計算できるの？
まずは普通に10進数の2つの数を足し算をするとき、どうやって計算をしているかを思い出してみましょう。
筆算だと、まずは「1の位」同士を足しますよね。
足して10未満なら、その結果を下に記入して次の桁に。
足して10以上なら、その結果の1の位を下に書いて、次の桁に繰り上がりがあることを記録する。
続いて、10の位でも同じ作業を繰り返す。さらに100の位、1000の位と同じ作業を続ける。
2進数でもやることは同じです。
まず1の位を計算する、そして繰り上がりの有無を記録しながら2の桁、4の桁と計算を進める、を繰り返せばいいのです。
さあ、準備は整った
まず、2300レーン分の1の位を表すbit0 カウントプレーンと、2300レーンのそれぞれに+1を行うかどうかの情報が入っているrise をみます。
この二つがあれば、2300レーン分の足し算の1の位がどうなるかと、2の位への繰り上がりがあるかどうかがわかります。
bit0カウントプレーン plane[0]のp番めとriseのp番めのbitの組み合わせが (0,1)か(1,0)の時、加算後のp番レーンの1の位は1です。
(0,0)か(1,1)の場合は0になります。
つまり、p番めのbitについては、
1の位の答え[p] = plane[0][p] XOR rise[p]
2の位への繰上り[p] = plane[0][p] AND rise[p]
と求められます。
これを2300レーン分まとめて見ると、
1の位の答え = plane[0] XOR rise
2の位への繰上り = plane[0] AND rise
です。
計算できたら、
plane[0] を「1の位の答え」で更新
carry に「2の位への繰上り」を保存
します。
これで1の位の計算が終わりました。
続いて2の位の計算です。
riseは+2とか+3を実行してくれ、と言ってくることはありません。要求は常に+1か+0のどちらかです。
つまり、2の位やそれより大きな位の計算にriseを使う必要はありません。
ただし、1の位の計算結果として繰り上がりが発生している場合があります。
ですから、2の位の計算結果を確定させるには、plane[1]とcarryの和をとればいいのです。
2の位の答え = plane[1] XOR carry
4の位への繰上り = plane[1] AND carry
計算できたら、
plane[1] を「2の位の答え」で更新
carry に「4の位への繰上り」を保存
します。
4の位も8の位もまったく同じです。
その桁のplaneと、ひとつ下の桁から来たcarryについてXORとANDを計算すれば、その桁の答えと次の桁への繰上りが求められます。
実際のVerilogでも、各桁の更新前の値から繰り上がりを計算するように記述します。
Icarusの計算量はだいぶ減ったんじゃないかな
2300個のカウンタの代わりに32個のカウントプレーンをもって計算する方法を採用しました。
結果として、
2300個の32bitカウンタを1個ずつ +1する
代わりに、
32個の2300bitカウントプレーンへ XOR / ANDを順番にかける
ことで、2300個のカウンタ更新をまとめて記述できます。
立ち上がり検出器から2300bitの検出結果が送られてくるたびに、2300個のカウンタを巡回していたのが、32個のカウントプレーンを巡回してbit演算を実行することになりました。
これは処理速度が上がる予感がします。
結果発表：カウンタの2300bit slice化は効いた？
さて、長い説明に付き合ってもらったので、そろそろ結果を見てみましょう。
まず K=2300, N=10,000。
変更前（高速化①＋②） 17.655秒
変更後（bit-sliced） 4.124秒
約4.3倍速くなりました。
おお。
かなり効いてます😁
N=100,000でも、
変更前 174.193秒
変更後 41.090秒
で、こちらも約4.2倍です。
では最大ケース N=7,000,000 はどうなりそうでしょうか。
今回も最後の十分大きい完走点 N=100,000 から単純に線形外挿すると、
高速化①＋②まで 約3時間23分
bit-sliced後 約47分56秒
ついに1時間を切りました。
最初の2300レーン版は約8時間50分でしたから、
約8時間50分
↓
約3時間23分
↓
約47分56秒
まで来たことになります。
しかも、まだ解法そのものは変えていません。
やっていることは相変わらず、
全kについて
全Aを見て
0→1を数える
です。
2300個のカウンタを、Icarusがまとめて処理しやすい形に並べ替えただけ。
愚直のまま、ついに少し浮かびました。
でもまだ47分。
AtCoderの5秒迷宮からの脱出は、はるかに遠いですね。
高速化④: カウンタのbit数を調整する
カウンタの値は最大でも700万です。23bitあれば0〜8,388,607を表せるので十分です。
以前は、カウンタ更新の度に32bit演算を2300回行っていました。
これを23bit演算を2300回にしても、ほとんど処理速度は変わらなさそう、と考えて放置していました。
仮想理想FPGAのリソース制約無制限設定に甘えた設計です。
ですが、高速化③でカウンタの演算方法を変更しました。
今のカウンタ更新演算は2300bit演算を32回になっています。
これを2300bit演算を23回にすれば、そのまま計算量が減りそうです。
結果発表：カウンタ幅の23bit化は効いた？
では結果です。
まず K=2300, N=10,000。
32bit版 4.124秒
23bit版 2.819秒
約1.46倍速くなりました。
32回の2300bit演算を23回に減らした効果が、ちゃんと出ています。
N=100,000でも、
32bit版 41.090秒
23bit版 28.911秒
まで短縮しました。
こちらも約1.42倍です。
では最大ケース N=7,000,000 はどのくらいになりそうでしょうか。
今回も N=100,000 の実測値から単純に線形外挿すると、
32bit版 約47分56秒
23bit版 約33分44秒
さらに14分ほど縮まりました。
ここまでのN=700万ケース予測時間を並べると、
最初の2300レーン版 約8時間50分
高速化①＋② 約3時間23分
bit-sliced化 約47分56秒
23bit化 約33分44秒
です。
今回は新しい仕掛けを追加したわけではありません。
使っていない上位9bitぶんの計算をやめただけ。
それでも30分台まで来ました。
Icarus君、少しずつ高度を上げています😁
次回
ここまでは、解法そのものを変えずに、
同じデータをIcarusが処理しやすい形へ持ち替える
ことで高速化してきました。
次は、データの持ち方ではなく、そもそもカウンタを更新する回数を減らせないか考えてみます。
Fly! Icarus, Fly High!
めざせ迷宮脱出😁
前回：
仮想理想FPGAでAtCoderを解く(1) - ABC471G① - 2300並列なら2300個並べればいい
次回：
仮想理想FPGAでAtCoderを解く(3) - ABC471G③ - 続・Fly! Icarus, Fly High!
コード全文と実装資料：(コード実装やドキュメント作成は生成AIの助けを借りています)
第2回コード全文と実装資料