高速化指向の関数分解と論理回路の簡単化

概要

LUT(Look-Up Table)型FPGA(Field Programmable Gate Array)向けの回路設計に不可欠な二つの要素技術として、段数の少ない高速な回路合成を目指した関数分解手法と、LUTからなる多段回路を簡単化する手法を考案した。

背景

LUT型FPGAを用いた回路設計では、通常所望の論理をLUTの多段回路へと変換した後に、実際のデバイスへの配置配線を行う。この配置配線の段階までに、高品質なLUTの多段回路(LUT数が少なくかつ段数が少ない回路)を合成しておくことが望ましい。しかし、従来の論理合成手法は、主にAND、OR等の基本ゲートをターゲットとしているため、LUT向けの適用では改善の余地が残る。そこで、我々は高品質なLUTの多段回路を論理関数から直接合成するための新しい手法について研究を進めている。

高速化指向の関数分解

LUTはある入力数(3から6が多い)以下の任意の論理関数を実現できる論理ブロックである。そこでLUT向けの論理設計では、入力数の多い論理関数をより入力数の少ない関数に分解する(関数分解という)手法が重要となる。これまでに提案されている手法の多くは、互いに素となる変数集合X¹と X²に限定して、f = h(g(X¹), X²)となる形の分解を基本にしている。それに対し我々は回路段数の削減を目指し、f = h(g₁(X¹), g₂(X²))という形の分解(図1)について検討を行った。X¹およびX²の変数の数の合計が最小となる分解を分枝限定法に基づいて効率的に求める手法を考案し、この手法を再帰的に用いてベンチマーク回路の論理関数を分解する予備実験を行ったところ、従来手法に比べて平均で23%少ない段数で分解できることを確認した[1]。

図 1: 高速化指向の関数分解手法

論理回路の簡単化

前年度に考案した「LUTの性質をうまく利用して回路を簡単化する手法」について、今年度はその評価および利用法についての検討を引き続き行った[2]。具体的には、図2に示すような設計フローに用いることを検討中である。上述の関数分解だけでは、各出力関数に対して段数の少ないLUTの多段回路を合成可能である反面、複数出力間で部分関数を共有して回路を簡単にすることはできない。そこで、引き続き本簡単化手法を適用して、段数を増やさずにLUTの共有を図るというものである。なお、本手法で用いた論理関数の自由度の表現方法に関しては、解説論文や応用研究が外部からも発表され、その可能性の高さが示された。

図 2: LUT型FPGAの合成フロー

今後の予定

上述した技術と既存の技術等と組み合わせ、より高性能な論理合成手法へと発展させる。また、開発した論理合成手法をPARTHENONに組み入れる予定である。

参考文献

[1]: Yamashita, S., Sawada, H. and Nagoya, A.: New Methods to Find Optimal Non-Disjoint Bi-Decompositions, Proc. of Asia and South Pacific Design Automation Conference 1998 (ASP-DAC '98), pp. 59-68 (1998).
[2]: 山下茂, 澤田宏, 名古屋彰: 論理関数の自由度の新しい表現方法とそのFPGA向け論理設計への応用, 電子情報通信学会技術研究報告, CPSY97-93/VLD97-105, pp. 37-44 (1997).

連絡先: 山下茂; Email: ger@cslab.kecl.ntt.co.jp

Last modified: Tue Oct 27 20:08:17 1998