今回はABC470Dを使って、少し変な遊びをしてみます。
これまでShrike-Liteでは、1120 LUTという小さなFPGAに回路を押し込んできました。
LUTが足りない。
配線が長くなってタイミングが通らない。
BRAMも少ない。
毎回、狭小住宅にどうやって家具を詰め込むか考えているようなものです。
ところが今回、突然そんな制約のない環境が手に入りました。
仮想理想FPGAです。
実装した論理回路が実際のFPGAに載るかどうかは忘れることにしましょう。
たとえばFFが10億個あってもいい。
配線遅延はゼロ。
routingもfanoutも気にしない。
入力だって、最初から全部FFに持たせてしまっていいことにします。
しかも配線遅延がないのなら、組み合わせ回路だけで表現できる処理は、どれだけ巨大でも時間コストはゼロです。
……。
やりたい放題じゃないか。
では、こんな環境でABC470Dを作ったらどうなるでしょう。
もちろん、何でも組み合わせ回路だけで終わるとは限りません。
途中の状態を確定させたり、次の処理へ渡したりするところではレジスタが必要になるはずです。
なら、そのレジスタ段数を極限まで削ったら？
つまり、
物理制約のない「仮想理想FPGA」なら、ABC470Dを何クロックまで縮められるんだろう？
今回はこれに挑戦してみます。
評価するのは、まずlogical clock数です。
Icarus Verilogがその巨大な仮想回路をシミュレーションし終えるまでの経過時間も、別の指標として測ります。
以下では、これをSIM時間と呼びます。
さて、50万件のクエリは何クロックまで縮むでしょうか。
1. まずは素直に実装してみる
ABC470Dでは、順列Aに対して最大500,000件のクエリを処理します。
クエリは2種類です。
-
1 x y：現在の順列のx番目とy番目を交換する -
2：現在の順列を逆順列へ置き換える
普通に解くなら、クエリを先頭から1件ずつ処理すればよい問題です。
では、これを仮想理想FPGAへ持っていくと何クロックになるでしょうか。
入力はTIME=0で全部持っていてよいことにする
まず、入力時間は今回は数えないことにしました。
N、初期順列A、Q件のクエリは、すべてTIME=0でFPGA内部に存在しているものとします。
かなり都合のよいルールですが、今回は「I/Oをどれだけ速くできるか」ではなく、
計算部分そのものを何クロックまで縮められるか
を見たいので、これで進めます。
A_invって1クロックで作れるんじゃない？
この問題では、現在の順列Aと、その逆順列A_invを両方持っておくと便利です。
普通のプログラムなら、
for i = 1 .. N
A_inv[A[i]] = i
とN要素を順番に処理します。
でも仮想理想FPGAなら、N個全部を同じclockで書けばよいのでは？
Aは順列なので、A[i] はすべて異なります。
つまり、
A_inv[A[1]]
A_inv[A[2]]
...
A_inv[A[N]]
のWrite先は競合しません。
なら1clockでよさそうです。
実装してみました。
1clockでできました。
物理的にどう配線するのかは知りません。
今回の舞台は仮想理想FPGAですからね。
クエリは1件1クロックでよさそう
次にクエリです。
クエリ type 2は、AとA_invのどちらを現在の順列として見るかをbitで切り替えれば済みます。
クエリ type 1では、たとえば通常向きなら、
a = A[x]
b = A[y]
として、同じclockで、
A[x] <- b
A[y] <- a
A_inv[a] <- y
A_inv[b] <- x
と更新できます。
これなら1クエリ1clockです。
Qは最大500,000なので、
500000 clocks
あれば全クエリを処理できます。
最後に1クロック必要だな
クエリ処理が終わったあと、最終状態をanswerへ確定させるclockも1つ必要です。
最初のA_inv生成が1clock。
クエリがQ clocks。
最後のanswer確定が1clock。
したがって、
Q + 2 clocks
です。
Q=500,000なら、
500002 clocks
になりました。
50MHz換算なら約10msです。
悪くありません。
でも、ここで少し気になりました。
クエリごとに1クロックって、FPGAとしてはずいぶん律儀じゃない？
2. クエリを何個かまとめて処理できないか
クエリ type 1は2つの位置をswapします。
では、
swap(1,2)
swap(3,4)
swap(5,6)
ならどうでしょう。
互いに違う場所しか触っていません。
これ、同じclockで全部やってしまってよさそうです。
何個ずつまとめればいいんだろう
そこで、1clockに最大K件のクエリ type 1をまとめる実装を作ってみました。
先頭から見ていき、
- そのclockですでに使っている位置と重ならない
- クエリ type 2にぶつからない
間は、同じclockへ詰め込みます。
途中で位置の競合を見つけたら、そこでそのclockは終了します。
Kは、
4
8
16
32
64
128
256
512
と変えて測ってみました。
大きくすれば、1clockで処理できるクエリは増え、logical clockは減りそうです。
ただし、そのぶんIcarus側では「このクエリも同じclockに入れてよいか」を調べる仕事が増えていきます。
面積は「仮想で理想」ですが、Icarusは現実のPC上でクロックを刻みます。
AtCoderの制限時間は2秒です。
あまり欲張ると、仮想FPGAは速いのにIcarusが間に合わない、ということになりそうです。
では、logical clockをかなり減らしつつ、Icarusもまだ現実的に動けるあたりを探してみましょう。
今回は、
K = 256
を基準にすることにしました。
2000クロックぐらいで終わるぞ
互いに競合しにくい500,000件のクエリ type 1を並べると、
Baseline 500002 clocks
K=256 1956 clocks
まで減りました。
約2000clockです。
1clockあたり平均約256件。
これはかなり気持ちいい結果です。
ランダムなswapでも、
2134 clocks
まで減りました。
「50万クエリ」と言われると大きく見えますが、256件ずつ片づければ2000clock程度です。
面積は正義です。
でも最悪ケースは何も変わっていない
ところが、
swap(1,500000)
swap(1,500000)
swap(1,500000)
...
のように、毎回同じ位置を触るクエリを並べるとどうなるでしょう。
同じclockでは1件しか実行できません。
結果は、
500002 clocks
でした。
256件分の実行器を用意したのに、255件分は毎clock暇です。
平均ケースは猛烈に速くなりました。
でも、
最悪ケースは最初の1 query / clock版と同じ。
なんだかもったいない。
なら、前から順番に詰めること自体をやめればよいのでは？
3. 先読みして、実行できるものから処理すればいい
たとえばクエリが、
A1
A2 ← A1と依存
B1
B2 ← B1と依存
C1
C2
...
と並んでいたとします。
固定幅版では、A2で引っかかると、その後ろにあるB1やC1まで同じclockへ入れられません。
でもB1やC1はAとは無関係です。
だったら、
少し先まで見て、今実行できるクエリだけ先に拾えばいいんじゃない？
という話になります。
CPUでいうOut-of-Order実行です。
256 issue / 1024 lookahead
そこで、
ISSUE_WIDTH = 256
LOOKAHEAD = 1024
としてみました。
先頭から最大1024件を見て、
- それ以前に同じ位置を触る未実行queryがない
- クエリ type 2のbarrierを越えない
ものをreadyとします。
その中から最大256件を同じclockで実行します。
このために、
- live query
- 各位置のtouch依存
- dependency count
- ready管理
などを追加しました。
だいぶCPUっぽくなってきました。
おお、さらに良くなった
固定幅版が苦手な入力を作って試しました。
2段の依存鎖を大量に並べたケースでは、
K=256 250003 clocks
OoO 1956 clocks
になりました。
固定幅版では約2件 / clockしか処理できなかったのに、OoOではほぼ256件 / clockまで戻っています。
これはかなり効きました。
先頭の1件に邪魔されて後ろの実行器が遊んでいた問題を、先読みでかなり解消できます。
じゃあ最悪ケースも速くなった？
ところが、
swap(1,2)
swap(2,3)
swap(1,2)
swap(2,3)
...
のように、直前のクエリと必ず依存する列を作ると、そうはいきません。
1024件先まで見ても、readyになるのはほぼ1件だけです。
logical clock / SIM時間で見ると、
Fixed K=256 500002 clocks / 9.030秒
OoO 500002 clocks / 15.978秒
でした。
logical clockは減っていません。
しかもIcarus側では、
- 1024件先を見る
- 依存関係を管理する
- readyを探す
仕事が増えたため、SIM時間はむしろ悪化しました。
最悪ケースでは、速くならないどころか作業量だけ増えている。
これは困りました。
すべての最悪ケースに対策する？
では、同じswapが続くなら相殺する？
クエリ type 2が連続したら消す？
もっと先まで見ればいい？
依存パターンごとに専用の簡約を入れる？
……。
考え始めると、いくらでも出てきます。
でも、
あらゆる「嫌なクエリ列」を先回りして最適化するの？
いやいや。
それは無理でしょう。
何か発想の転換がないと、このまま行き詰まりになりそうな予感がします......
今回のまとめ
仮想理想FPGAでABC470Dを何clockまで縮められるか、思いつくまま試してみました。
実装した成果物などは以下に置いてあります。
色々試行錯誤してみましたが、最悪ケースでQ + 2 clocksを短縮するのはなかなか難しそうです。
しかも賢いschedulerを追加すればするほど、Icarusの実仕事は増えていきます。
さて。
50万件のクエリを速く実行するには、次に何をすればよいのでしょうか。
次回、もう少し考えてみます。
ちょっと補足
AtCoderのVerilogジャッジはIcarus Verilog + vvpで2012モードが使えるので、今回の実装はSystemVerilog（.sv）で書いています。
「いつもと拡張子が違うじゃないか」と思われた方、ゴメンナサイ。
それから、記事中のSIM時間は筆者のローカルPC（Windows 11 / 12th Gen Intel Core i7-12700H）上でIcarus Verilogを実行して測定した値です。AtCoderのジャッジ環境で測定した値ではありません。
ご了承ください。
前回：
Shrike-LiteでAtCoder問題を解く(32)：Detour：ABC470A - 公式ジャッジにVerilogで参加してみる
次回：
Shrike-LiteでAtCoder問題を解く(34)：Detour：ABC470D(後編) - 50万クエリ、結局ひとつの変換じゃない？
今回の全コード：
第33回コード全文