freelabの日記

FPGAのテクノロジーマッピングの中身はなにしているのか

テクノロジーマッピング, FPGA | 01:18 |

Verilogとかで書いたプログラムを論理式になおす、特にFPGAで実装できるような形式に変換していく処理を論理合成という。

論理合成はFPGAの他にも、CPLDや、ASICで実装する時も必要な処理。

アルゴリズムが実装される物理的な媒体（FPGAとか、CPLDとか、ASICとか）を「テクノロジー」と呼ぶ。論理素子の基本単位がそれぞれの物理媒体によって異なるので、その実装技術の差を指して「テクノロジー」というらしい。

論理合成の処理も、物理媒体に依存した処理「テクノロジーに依存した処理」と、どの物理媒体に対しても共通的に必要な前処理を「テクノロジー非依存の処理」と呼び、分けてアルゴリズムを考えている。

FPGAの場合は、基本素子がLUT（Look up table)なので、論理式をブーリアンネットワークの形式で表現すると、物理的な媒体へのあてはめ「テクノロジーマッピング」が親和性よくなる、らしい。

FPGAの基本単位（素子の単位）のLUTは、例えば、4つの入力値によって出力値を決定する表を格納してある「メモリ」だと考えればいい。物理的には作り方は色々あるらしい。

左がブーリアンネットワークで表現された簡単な論理式の例。a or b -> e , c or d -> f e and f -> g という例。それを、右のようにLUTにあてはめて実装していく。

もう少し大きめのブーリアンネットワークの例。FPGAで実装するには、右のように論理とLUTをあてはめていく。

「テクノロジー」が違うASIC（ゲートアレイ）の場合だと、基本素子の単位であるトランジスターをずらっとならべたもの。

基本素子であるトランジスターの回路図はこんな感じになる。

それをこんな感じで配線すると、NAND（ !(A and B)）として機能する回路になる。

同じことを奇麗な回路で書くとこうなる。こっちの方が分かり易い。

配線した論理ブロック（セル）をさらに配線してつなげることで、複雑な論理式を表現する。

こんな感じで、FPGAか、ゲートアレイか、などによって変わる処理を、テクノロジー依存論理合成処理、と呼んでいる。

話をFPGAのテクノロジマッピングにもどして、何であんなにISEの論理合成、Placement,Routingに時間がかかるのか？なにを悩んでいらっしゃるのか？ですが、回路の遅延とか、必要な面積（LUT数）を減らす努力をされているのです。

小規模な例だとわかり難いが、もっと大きなアルゴリズムをブーリアンネットワークをFPGAにマップしようとすると、良いマッピングを探すのに時間がかかるのもうなずける。

良いマッピングは、第一に、LUTのネットワークの縦方向の深さ（右側の図みたいなもの）、要するに、入力から出力までいくつLUTを経由しているか、を最小にするもの、第二に、できるだけ少ないLUTの個数で表現すること。

第一の目的は、それが「配線遅延」、要するに、一番長い距離（深い段数）を信号が伝わっていくのに必要な時間が遅延時間になる、ので、これが大きいとタイミングメットしない遅い回路、という事になる。高速に動作するFPGA回路を組むにはこれをできるだけ小さいものにするようがんばるので、あんなにISEは時間をかけているらしい。こういう最適化処理は逐次処理ヒューリステッィクが多いので、きっとISEもそうなんだろう。

第二の目的は、すくないLUTで回路が組めれば、ひとつのFPGAにたくさん詰め込めるから経済的です、ということ。

まだまだ効率のよい方法を研究している人もいるようです。今回お勉強のお世話になった九州大学の松永研究室の方の研究資料。

http://ci.nii.ac.jp/naid/110007131412

上記イラストは九州大学の松永先生の講義資料（http://www.c.csce.kyushu-u.ac.jp/~matsunaga/lecture/lsicad/）、リコンフィギャラブルシステム（オーム社）からの引用。と、書いておけば著作権法上の例外に相当するでしょう、間違いなく。"this domain violates imageshack's Tos"とか言ってyfrogのカエルさんが凍っているようなので、追加。でも自動削除じゃ意味ないか。

ツイートする