前回、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へ入れてみる

次のクエリは、

です。

ここでは 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回コード全文と実装資料