|
|
|
FPGAの詳しい中身
|
|
|
|
================
|
|
|
|
|
|
|
|
実験で使うXilinx社のFPGAの論理ブロックは、「6入力LUTと全加算器[^1]とフリップフロップ[^2]」がこの順番でつながっています[^3]。ただし、6入力LUTは同一入力信号を持つ5入力LUT二つとしても使えます。これが四つ集まったものをスライスと呼んでいます。スライス内の四つの全加算器はキャリー信号が専用線でつながっており、高速な4bit加算器として動作します。
|
|
|
|
|
|
|
|
つまり、以下のような組み合わせ論理回路はFPGAと相性が良いです（トップレベルの箇条書きは一般論で、ぶら下げている箇条書きは実験で使うFPGAのシリーズに特有の話です）。
|
|
|
|
|
|
|
|
* 一つのLUTに入るような論理回路
|
|
|
|
* 6入力以内の、任意の1bit出力論理回路
|
|
|
|
* 特に、4:1のセレクタ（4入力＋選択信号が2bit）が6入力LUT一つで実現できることを覚えておくと便利
|
|
|
|
* 5入力以内の、任意の2bit出力論理回路
|
|
|
|
* 二進法で表された二数の加減算および大小比較演算[^4]
|
|
|
|
* LUTでちょっとした論理演算をした後、その結果を加算器に通す場合（スライス内で完結するので高速）
|
|
|
|
* LUTでnotを取ることで、減算ができる
|
|
|
|
* 制御信号入力によってAにBを足すかCを足すかを切り替える
|
|
|
|
* キャリー信号用の専用線を活用した最適化が可能な場合[^5]
|
|
|
|
|
|
|
|
|
|
|
|
逆に、以下のような組み合わせ論理回路は（上記と比較すると）FPGAと相性が悪いです。
|
|
|
|
|
|
|
|
* 加減算の結果を、LUTの入力とする場合（二スライス必要で、配線遅延もかかる）
|
|
|
|
* ``assign result = op == `OP_ADD ? a + b : a - b;``とか書いただけでこれになるので回避はかなり面倒
|
|
|
|
|
|
|
|
|
|
|
|
以下のような組み合わせ論理回路は、FPGAに限らず、一般に効率が悪いです。
|
|
|
|
とりあえず、FPGAの場合になぜ効率が悪いのかを書いておきます（トップレベルの箇条書きは一般論で、ぶら下げている箇条書きは実験で使うFPGAのシリーズに特有の話です）。
|
|
|
|
|
|
|
|
* 多数の入力を持つ複雑な論理回路[^6]
|
|
|
|
* 9入力以上[^7]になると論理回路の複雑さが資源消費量に影響し、最悪の場合指数的に大きくなっていく
|
|
|
|
* 大量にある入力の中から、一つを選択する論理回路
|
|
|
|
* レジスタファイルをフリップフロップで作ろうとしたり、データメモリを分散RAMで作ろうとした場合など
|
|
|
|
* 素直に[分散RAMやブロックRAM](FPGARAM)を使おう
|
|
|
|
* 出力のビット数が非常に多いような論理回路
|
|
|
|
* ワンホットエンコーディングなど
|
|
|
|
* よほどビット幅が小さくない限り、制御信号は二進法で表すのが無難
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
## 脚注
|
|
|
|
以下は実験で使うFPGAのシリーズに特有の話をかなり含みます。
|
|
|
|
|
|
|
|
[^1]: XORとセレクタしか真の回路としては存在していないため、正確には全加算器の一部。直前にあるLUTが「入力キャリーがあればキャリーを出力するか否か＝入力二数の和が1であるか否か」を生成し、XORとセレクタに入力することで全加算器を実現している。セレクタは選択信号が1であればキャリー入力を通し、0であれば「入力キャリーによらず出力キャリーが決まる場合、その値（入力キャリーによって出力キャリーが変化する場合はドントケア）」を通すようになっている。後者は実は加算のオペランドの片方（どちらでもよい）が流用できる。なぜそれでよいのか、考えてみてほしい。なお、このような変な方法になっているのは、キャリーの伝搬をなるべく高速に（一ゲート遅延で）行えるようにするため。
|
|
|
|
[^2]: 実は、加算器の出力につながっているフリップフロップ以外に、LUTの出力が直につながっているフリップフロップも存在する。したがって一スライスに合計で八個のフリップフロップが存在する。
|
|
|
|
[^3]: 6入力LUTの代わりに上位互換品である64bit分散RAMが入っているスライスもある（全体の1/4程度？）。
|
|
|
|
[^4]: 4bit加算器の最上位のキャリー出力は、隣のブロック（スライス二つまとまりのことをブロックと呼ぶ）の4bit加算器のキャリー入力に専用線でつながっているので、4bitを超える幅の加算器もかなり高速に動作する。実質的に加算器専用回路が内蔵されていると言える。
|
|
|
|
[^5]: 例えば、32bit整数のすべてのビットが0かどうかは、0xffffffffを足して繰り上がるかで判定できる。このように、出力が1bitの論理関数のうち非常に特殊（だが頻出）なものは「キャリーが出力されるか」といった形で加算器のみを使って合成可能である。数ビットの結果をまとめたものを加算器の入力とすればさらに効率が上がる。
|
|
|
|
[^6]: パリティの計算（全ビットの排他的論理和を取って1bitにまとめる）、といったものは多段のLUTに自明に分割できる単純な論理回路である。一方、Leading zeros count（上位何ビットが連続して0かを数える）、といったものは多段のLUTへの分解（中間計算結果に何を取るべきか）が自明ではない複雑な論理回路であり、ヒント無しで合成すると非常に大きな回路が生成されてしまう。
|
|
|
|
[^7]: 一応、8入力までの任意の論理関数は一スライスで実現可能であるが、Vivadoはそれを最終手段とみなしているようである。一スライスに四つある6入力LUTの出力をスライス内にある二段のセレクタで選択することで8入力LUTを実現するのだが、たった1bitの出力に一スライス使うのは非常にもったいない。多くの場合、Vivadoはそういった論理関数を二段のLUTに分割する。一段目のLUT出力を他の場所で再利用できれば合計の消費LUT数を減らせるからである。一段目のLUT出力はかなり自由に選べるので、ほとんどの場合、うまく選べば他の場所で再利用できる形にできる。 |
