FPGAのコンパイルが遅い理由

結論：NP問題のナップサック問題だから

よくFPGAはコンパイルが遅いと言われます。
ではなぜ遅いのかちゃんと技術的にこうだろう、と指摘しているのを見たことがないので
自分なりにコンパイルプロセスを俯瞰してみて、なぜ遅いのか？を推測したいと思います。

デバイスメーカーの公式見解ではありません

ソフトウェアのコンパイル

ソフトウェアのコンパイルはソースコードを機械語に順番に置き換えることを コンパイル と呼んでいます。場合によってはビルドとも呼ばれていますね。

記述ミスさえなければ機械的に変換するだけになるのでコンピュータの性能に依存して処理時間が主に決まります。

FPGAのコンパイル

FPGAで動くHDLのコンパイルは機械的に回路素子に変換した後に
FPGA上の回路素子に変換したものがFPGA上に配置できるかチェックされます。
ここでチェックがほぼ素通りできるぐらいであれば、そんなにコンパイル時間はかかりません。

デバイスメーカーがやっている簡単なトレーニングで使われるようなものだと5分程度で終わるようになっています。

HDLの記述を大量にやって、FPGA上に配置できる回路素子の数がギリギリになってくると途端にチェックされる時間（配置できるか右往左往する時間）が増えてコンパイル時間が大幅に長くなります。
（自分の経験だと12時間は当たり前の悪いと24時間超えを見たことがあります）

考えてみると、これは NP問題のナップサック問題であることがわかります。

ナップサック問題の身近な例

SSDやHDDにデータを保存する方法が良い例だと思います。
すこし勉強したことがある人は知っていると思いますが、ストレージはセクタと呼ばれる一定領域に区切っておいて、データがどこにあるかのインデックスと組み合わせて
ユーザから来る多種多様なデータを保存して管理しています。

なので、セクタ区切りが 4kBだったりすると 1kBのデータは3kBの無駄と合わせて管理されています。

Windowsで右クリックしてプロパティで出てくる

サイズ（実際のファイルのデータ量）
ディスク上のサイズ（セクタ単位で区切られてストレージ上で使うデータサイズ）

が身近な例です。

では、これを例えば256GBなら256GB、1TBなら1TBのストレージを

任意データ長の追加＆削除に合わせてストレージ管理してください

というのを考えてみてください。
追加だけならともかく削除も組み合わせられると、とても難しくなります。

例えば簡単に10Byteのストレージだったとして
+1 + 4 +2 -4 +3 +2 +2 とデータが追加される様を考えると

何も考えず上から順にいれるとこの通り。入れられなくなってしまいます。

どんなデータが来るか分かれば 対処の仕方もあるのはわかります。
なので、最終的にどんなデータが来るかわかったので調整すれば全て入れることはできます。

何がどう追加されてもいいように対処しようとすると
先の「一定範囲に区切って（セクタ）、その区切り単位への目次（インデックス）で管理する」が次善策になります。
後で使い切れるように調整するのはストレージの例で言うと デフラグ ですね。（昔はよく聞きましたけど、もうデフラグしてるのは聞きませんね）

FPGAで動くHDLをコンパイルした時にも同じようなことが起こっていると考えていて、なのでコンパイル時間が長いのです。

余談：NP問題を解くのが量子コンピュータ

数が増えてくると組み合わせが爆発的に増えて計算時間が実質的に終わらない状態になるのをNP問題と言います。解く側にすれば厄介なNP問題ですが、この計算困難さはセキュリティに活用されたりもしています。

またNP問題を現実的に解く方法として考えられているのが量子コンピュータです。
量子コンピュータの方式ごとに解けるNP問題に種類があるようで、FPGAコンパイル用の量子コンピューティングのクラウドサービスが出ないか期待しています。