|
This dissertation explores the issues of logic synthesis,
technologymapping and partitioning for field programmable gate
arrays andproposes the corresponding algorithms to solve them.
On thesynthesis of LUT-based FPGAs, an improved algorithm based
on Roth-Karp decomposition is proposed to make the given logic
networksfeasible. On the input variable partitioning, a novel
heuristicalgorithm, which selects a good bound set in Roth-
Karpdecomposition, is presented. And this algorithm is
incorporatedinto a new decomposition flow scheme. The issue of
compatible classencoding is formulated as a symbolic-output
encoding problem andthen an encoding algorithm is developed to
specifically solve it.This new encoding algorithm is designed to
specifically exploit thefeature of the two-output LUT
architecture. For timing-driventechnology mapping, an iterative
area/performance trade-offalgorithm is presented. The approach
begins with finding a level-considered area-optimized initial
network for the given circuit. Aniterative algorithm is then
applied to get the set of complete area/level trade-off mapping
solutions. Experimental results show thatthis algorithm can
provide not only an excellent area/level trade-off curve but
also the level-optimized solutions that competefavorably with
those provided by most existing level optimizationalgorithms.
For performance-driven circuit clustering with
capacityconstraint, an iterative area/delay trade-off clustering
algorithmis proposed. The approach begins with finding an
initial delay-considered area-optimized acyclic clustering
solution. Thereclustering algorithm is then applied to get the
set ofcomprehensive area/delay trade-off clustering solutions.
Experimental results show that the delay-optimized
solutionsprovided by this algorithm have almost the same
performance withthat of the delay optimal solutions provided by
the existing delayoptimal algorithm while the required area
overhead is significantlyreduced. When both capacity and pin
constraints are concerned, thisalgorithm is still capable of
providing comprehensive area/delaytrade-off clustering
solutions. Hence, this algorithm can be easilyapplied to
performarea/delay trade-off operations for multi-FPGAsystems.
|