Up
Performance-Driven Functional Decomposition and Circuit Minimization
Abstract
We have developed a circuit minimization method and a functional
decomposition method for producing logic circuits with fewer
levels. Both are
thought to be essential for look-up table (LUT) based field
programmable gate array (FPGA) logic synthesis.
Background
When we design a circuit using an LUT based FPGA, we usually
first transform the desired functions to an LUT network.
The transformed LUT network is thought to be "good" if the number of LUTs and
levels are both small. However, since usual logic synthesis
methods take account for only basic gates such as AND and OR, they do
not always generate good LUT networks. Therefore, we are seeking new
methods for generating good LUT networks directly from logic functions.
Performance-Driven Functional Decomposition
An LUT can realize any boolean function with a fixed number
of inputs. Therefore, it is important to decompose a large
function to small functions for LUT network synthesis.
Most of the previously proposed functional decomposition methods are
based on the form: f = h(g(X1), X2) where
X1
and X2 are disjoint sets of variables.
In contrast, we studied a decomposition form: f = h(g1(X1),
g2(X2)) (Figure 1).
We have developed an efficient method which finds a decomposition form
where the total number of variables in X1 and X2 is the smallest.
Our method decomposed logic
functions with 23% fewer levels than the usual method [1].
Fig. 1: Peformance-driven decomposition
Circuit Minimization
We have been continuously studying the applications of
the circuit minimization method [2], which we developed last year.
We plan to use the method in the design flow in Figure 2.
The minimization method is applied in this flow to share common
sub-functions without increasing levels after the above functional
decomposition.
Furthermore, the logic expression techniques used in our minimization
method were adopted by other researchers who showed their potential.
Fig. 2: Design flow for LUT networks
Future Work
We plan to develop a high-quality logic synthesis method using the
above techniques. We also plan to incorporate the developed method
into PARTHENON.
References
- [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]
- Yamashita, S., Sawada, H. and Nagoya, A.: A New Method to Express Functional Permissibilities and Its Application to FPGA Synthesis (in Japanese), IEICE Technical Report, CPSY97-93/VLD97-105, pp. 37-44 (1997).
Contact: Shigeru Yamashita;
Email: ger@cslab.kecl.ntt.co.jp
Last modified: Wed Oct 14 15:22:27 1998