前回、ABC470Dを「仮想理想FPGA」で何クロックまで縮められるか試してみました。
最初は1クエリ1clock。
次に256件ずつまとめて並列実行。
さらに1024件先読みのOut-of-Order実行まで作ってみました。
それがうまく効いて、logical clock数をかなり減らせたケースもありました。
しかし最悪ケースの場合、たとえば、強い依存関係を持つクエリ列を作ると、
500002 clocks
のままです。
しかもschedulerを賢くするほど、IcarusのSIM時間は増えていきました。
これは困った。
もっと先読みする？
依存パターンごとに専用の最適化を作る？
いやいや。
そんなことを始めたら、いくらでも「嫌なクエリ列」を作れます。
そこで、少し考え方を変えてみることにしました。
1. そもそも、50万件のクエリを実行する必要があるのか？
ここまでずっと、
50万件のクエリを、どう速く実行するか
を考えていました。
でも、ABC470Dの入力を少し違う目で見てみます。
初期順列があって、
query 1
query 2
query 3
...
query 500000
が続き、最後に答えが出ます。
これって結局、
初期順列を最終順列へ変換する、少し長く書かれた1個の関数
なのでは？
だったら、50万件を実行待ちの命令として持つ必要はありません。
最初に全部読んで、
この50万件が結局どんな変換を表しているのか
だけを作ってしまえばいい。
……。
これ、いけるんじゃない？
2. Haskellの話を思い出した
以前、Haskellでの競プロについて書かれた資料を読んだときに、妙に印象に残った考え方がありました。
処理を「どういう手順で実行するか」ではなく、
結局これは、何を何へ写す変換なのか
として見る。
Haskellを使い込んでいるわけではないので、そんな考え方が身についていたわけではありません。
でも今回、
「50万件のクエリを、先に1個の変換へまとめてしまえば？」
と考えたところで、この話を思い出しました。
50万件あるから大変なのではなく、
50万行で書かれた1個の関数だと思えばいい。
そう考えると、急に景色が変わってきます。
3. クエリを外側へ合成してみる
いきなり数式から考えるのはやめて、まず公式サンプル1で試してみます。
ここでは、初期順列を固定した P、現在の順列を C と呼ぶことにします。
公式サンプル1の初期順列は、
P = (2, 1, 3, 5, 4)
です。
ここに補助順列 U, V と、向きを表す inverted を用意します。
最初は、
U = (1, 2, 3, 4, 5)
V = (1, 2, 3, 4, 5)
inverted = 0
です。
(1, 2, 3, 4, 5) は何も入れ替えないidentity、つまり恒等順列です。
最初のswapはVへ入れてみる
最初のクエリは、
1 2 4
です。
まだ inverted = 0 なので、このswapを V へ合成してみます。
U = (1, 2, 3, 4, 5)
V = (1, 4, 3, 2, 5)
inverted = 0
すると、V で並べ替えた位置から初期順列 P を読むだけで、
P[V[1]] = P[1] = 2
P[V[2]] = P[4] = 5
P[V[3]] = P[3] = 3
P[V[4]] = P[2] = 1
P[V[5]] = P[5] = 4
となり、
C = (2, 5, 3, 1, 4)
です。
公式サンプルの1クエリ目と一致しました。
反転したら、今度はUへ入れてみる
次のクエリは、
2
です。
ここでは U も V も触らず、
inverted = 1
とするだけにしてみます。
そして次のクエリ、
1 2 3
が来ました。
今度は反転中なので、swapを V ではなく U へ合成します。
U = (1, 3, 2, 4, 5)
V = (1, 4, 3, 2, 5)
inverted = 1
じゃあ、ここから答えはどう出す？
反転中なので、現在の順列は、
C = V^-1 ∘ P^-1 ∘ U^-1
で求められます。
今回の例では、たまたま P, U, V はどれも自分自身が逆順列です。
たとえば C[1] を求めると、
1
-> U^-1 で 1
-> P^-1 で 2
-> V^-1 で 4
なので、
C[1] = 4
です。
同じように全要素を求めると、
C = (4, 3, 1, 5, 2)
となります。
これも公式サンプルの3クエリ目まで実行した結果と一致します。
つまり、
通常向きならVへ。反転中ならUへ。
向きbitに応じて、swapを合成する側を切り替えればよさそうです。
しかもクエリは先頭から順番に流れてきます。
だったら、そのたびに現在の順列そのものを書き換えるのではなく、
次のswapを、いま持っている変換の外側へ合成し続ければいいのでは？
クエリ type 2が来たら、向きを反転するだけ。
これを50万件続けても、50万件の命令列が残るわけではありません。
最後に残るのは、
U
V
inverted
だけです。
あれ？ 50万クエリ、ひとつの変換に畳めるんじゃない？
本当にこれでいいの？ 数式で確認する
ここから少しだけ関数合成の話をします。
数式が苦手なら、この部分は読み飛ばしてもらって大丈夫です。
通常向きでは、現在の順列 C を、
C = U ∘ P ∘ V
と表します。
反転向きでは、
C = V^-1 ∘ P^-1 ∘ U^-1
です。
この2つはちょうど互いに逆順列になっています。
だからクエリ type 2では、U や V を作り直さず、
inverted ^= 1
と、どちらの式を見るか切り替えるだけで済みます。
クエリ type 1で位置 x, y をswapするときは、通常向きなら、
V <- V ∘ T(x,y)
反転中なら、
U <- T(x,y) ∘ U
とすれば、上の表現を保ったまま次のswapを外側へ合成できます。
U, V と、それぞれの逆写像を持っておけば、この更新は1クエリあたり定数個の配列アクセスで済みます。
つまり直感で考えた、
向きによってUとVを切り替えながら、外側へswapを合成し続ける
で本当に大丈夫そうです。
4. Permutation Compilerを作ってみた
この方式を、今回は Permutation Compiler と呼ぶことにしました。
やっていることは単純です。
TIME=0で全入力を読み、
query 1
query 2
query 3
...
query Q
を1件ずつ U, V, inverted へコンパイルします。
ここは今回の仮想理想FPGAルールでは0 clockです。
そして最後に、完成した変換を answer[] へ展開します。
通常向きなら、
answer[i] = U[P[V[i]]]
を全 i について同じclockで実行します。
逆向きでは、少し見方を変えます。
「answer[i] に何が入るか」を探すのではなく、
初期順列
Pの各要素が、最終的にanswer[]のどこへ行くか
を計算します。
初期位置 k の要素について、
answer[U[P[k]]] = V^-1[k]
と書けば、P^-1 を作る必要がありません。
P と U はどちらも順列なので、異なる k が同じ書込み先へぶつかることもありません。
したがって、これも全 k について同じclockで実行できます。
つまり、
query compile 0 clocks
answer確定 1 clock
--------------------------
合計 1 clock
です。
……。
1クロック？
5. 本当に全部1クロックだった
まず小規模テストを大量に流しました。
公式3例に加えて、特殊ケース、ランダムケースを含めてSystemVerilog版を検証しました。
すべてPASS。
さらに、前回まで使っていた最大規模 N=Q=500000 のケースでも測定しました。
| ケース | logical clocks | 50MHz換算 | SIM時間 |
|---|---|---|---|
| 高並列 | 1 | 20ns | 6.107秒 |
| ランダム | 1 | 20ns | 6.450秒 |
| 高競合 | 1 | 20ns | 5.827秒 |
| Interleaved dependency | 1 | 20ns | 6.034秒 |
| Cancellation-rich | 1 | 20ns | 5.154秒 |
| Strong dependency | 1 | 20ns | 5.449秒 |
高並列でも。
全競合でも。
強い依存関係があっても。
相殺できても、できなくても。
全部1 clockです。
前回あれだけ悩んだ「嫌なクエリ列」という概念そのものが消えました。
6. 104分かかったIcarusが、5.449秒で帰ってきた
特に面白かったのがStrong dependencyです。
前回作った、
swap(1,2)
swap(2,3)
swap(1,2)
swap(2,3)
...
を50万件並べたケースです。
この入力では、前回のOoO版はどう頑張っても、
500002 clocks
でした。
さらに相殺処理まで有効にすると、相殺できるクエリが1件もないのに、毎clock先読みとnormalizationを繰り返します。
結果、
OoO ON
500002 clocks
6266.929秒
中央値で約104.45分かかりました。
ところがPermutation Compilerでは、
1 clock
5.449秒
です。
logical clockが減っただけではありません。
IcarusのSIM時間まで、約1150倍短くなりました。
もちろん、
1 logical clockだからSIM時間も短い
という意味ではありません。
logical clockとSIM時間は別の指標です。
今回は、OoO schedulerや依存管理そのものを捨てて、クエリを単純な変換合成へ置き換えた結果、Icarus側の仕事まで減りました。
なんだか、ずいぶん遠回りをした気もします。
でも、その遠回りをしたからこそ、
速く実行するのではなく、実行するもの自体を消す
という発想にたどり着けた気がします。
7. ところで、0クロックにはならないの？
ここまで来ると、
「最後の
answer[]も組み合わせ回路の出力にすれば0 clockでは？」
という話も出てきます。
たしかに、配線遅延も組み合わせ回路遅延も0とするなら、理屈の上ではそうできます。
ただ、それでは「いつ答えが確定したのか」が少し曖昧になります。
そこで、この仮想理想FPGAでは、
最終回答をanswerレジスタへ格納した時点を計算完了とする
ことにします。
答えが組み合わせ回路上に見えているだけでは、まだ未提出。
「これが答えです」とanswerへ確定するために、最低1clockは必要。
したがって、このルールでは、
1 logical clockが下限
です。
今回のABC470Dは、その下限まで到達しました。
8. 1クロックなら何でも偉いのか？
ここでもう一つ、面白い問題が出てきます。
物理制約を完全に無視するなら、有限の入力に対しては、全入力パターンと答えを巨大な真理値表にしてしまえば、どんな問題でも1 clockにできます。
でも、それではさすがに面白くありません。
今回やりたいのは、
できるだけ小さく、意味のある「答えを出す関数」を見つけて、それを面積へ展開すること
なのだと思います。
ABC470Dでは、50万件のクエリを巨大な場合分けへ展開するのではなく、
U
V
inverted
という比較的コンパクトな変換表現へ畳み込めました。
1 clockという数字だけではなく、
どうやって1 clockへ持っていったか
が、面白いところなのだと思います。
今回のまとめ
前回は、50万件のクエリをどう速く実行するか考えました。
256件ずつ並列化し、
Out-of-Order実行まで作り、
それでも最悪ケースでは500002 clocksでした。
今回は、そこから発想を変えて、
50万件のクエリを、1個の変換へコンパイルする
ことにしました。
結果、
どんなクエリ列でも
1 logical clock
です。
しかもStrong dependencyでは、
OoO ON 500002 clocks / 6266.929秒
Permutation Compiler 1 clock / 5.449秒
となりました。
50万件を速く実行したのではありません。
50万件を「実行する」という考え方そのものを捨てました。
第33回からずいぶん遠くまで来ました。
でも、仮想理想FPGAで遊んでみたおかげで、良い景色を見れたと思います。
おまけ：とにかくACを狙う版も作ってみた
今回のPermutation Compiler版は、logical clockでは1 clockですが、筆者のローカルPC上ではSIM時間が5秒以上かかっています。
そこで、
「FPGAらしさはどうでもいいから、とにかくVerilogでACを取りたい」
という版も、おまけで作ってみました。
こちらはもうFPGAらしさを完全に捨てて、Icarus上でできるだけ速く動くことだけを狙っています。
気がつけば、アルゴリズムよりI/Oをどう軽くするかの方を一生懸命最適化していました。
その結果、最大規模のRandomケースでは、ローカル環境で 3.410秒 まで短縮できました。
かなり速くなりましたが、目標の2秒未満には届いていません。
AtCoderのジャッジ環境では実行速度も変わるので、これでACを取れるかどうかは、実際にSubmitしてみないと分かりません。
興味のある方は、ぜひ試してみてください。
コードと測定結果はGitHub側に置いておきます。
前回：
Shrike-LiteでAtCoder問題を解く(33)：Detour：ABC470D(前編) - 仮想理想FPGAなら何クロックで解ける？
次回：
Shrike-LiteでAtCoder問題を解く(35)：Interlude - ABC471の各問題をFPGA目線で見てみる
コード全文と実装資料：(今回もコード実装やそのドキュメント化は生成AIの助けを借りています)
第34回コード全文と実装資料