Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(10)
Circuit Optimization
Circuit Synthesis
Design Automation
Empirical Study
Field Programmable Gate Array
Logic Design
Logic Synthesis
Optimal Method
Optimal Solution
Technology Mapping
Subscribe
Academic
Publications
Optimality Study of Logic Synthesis for LUTBased FPGAs
Optimality Study of Logic Synthesis for LUTBased FPGAs,10.1109/TCAD.2006.887922,IEEE Transactions on Computeraided Design of Integrated Circuits and
Edit
Optimality Study of Logic Synthesis for LUTBased FPGAs
(
Citations: 10
)
BibTex

RIS

RefWorks
Download
Jason Cong
,
Kirill Minkovich
ABSTRACT FPGA
logic synthesis
and technology mapping,have been studied extensively over the past 15 years. However, progress within the last few years has slowed considerably (with some notable exceptions). It seems natural to then question whether the current
logic synthesis
and
technology mapping
algorithms ,for FPGA designs are producing ,nearoptimal solutions. Although there are many empirical studies that compare,different FPGA synthesis/mapping algorithms, little is known about how far these algorithms are from the optimal (recall that both logic,optimization and technology mapping,problems,are NPhard if we consider area optimization in addition ,to delay/depth optimization). In this paper we present a novel ,method ,for constructing arbitrarily large circuits that have ,known ,optimal solutions after technology ,mapping. Using these circuits and ,their derivatives (called LEKO and LEKU, respectively), we show that although leading FPGA technology,mapping ,algorithms can produce ,close to optimal ,solutions, the results from the entire
logic synthesis
flow (logic optimization + mapping) are far from optimal. The best industrial and academic,FPGA synthesis flows are around ,70 times larger in terms of area on average, and in some cases as much as 500 times larger on LEKU examples. These results clearly indicate that there ismuch,room ,for further research and improvement ,in FPGA synthesis. Categories and Subject Descriptors B.6.3 [Hardware]:
Logic Design
– Design Aids General Terms
Journal:
IEEE Transactions on Computeraided Design of Integrated Circuits and Systems
, vol. 26, no. 2, pp. 230239, 2007
DOI:
10.1109/TCAD.2006.887922
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(6)
...It was shown that commonly used logic synthesis algorithms are not capable of efficient synthesis and optimization for some circuit classes, especially for large circuits and circuits containing hardtosynthesize substructures [
5
, 10]...
Zdenek Vasicek
,
et al.
Formal verification of candidate solutions for postsynthesis evolutio...
...Not only their everincreasing size becomes a problem; there have been discovered very small circuits, for which synthesis tools produce extremely bad results [
20
]...
...Even though circuits presented in [
20
] were artificially constructed, their design is rather realistic, e.g., judging by their Rent’s exponent...
...Up to the knowledge of the authors, circuits “difficult” for conventional and current synthesis processes were introduced in [
20
] for the first time, originally to test the performance of LUT (lookup table) mappers...
...Designers have objected to the Cong & Minkovich’s LEKU circuits [
20
], since they are artificially constructed...
P. Fišer
,
et al.
On logic synthesis of conventionally hard to synthesize circuits using...
...Cong and Minkovich [
1
] published a methods for the construction of combinational circuits with known optimal implementation (LEKO) or with known upper bound (LEKU)...
...These examples were primarily designed to test the technology mapping [
1
]...
...For detailed description, please refer to [
1
]...
...The tools were, apparently, able to rediscover an acceptable circuit structure; they are actually better than concluded in [
1
]...
Jan Schmidt
,
et al.
The Case for a Balanced Decomposition Process
...For a set of benchmarks with known optimal implementation, obtained results were on average 70 times larger in terms of area[
1
]...
Stanislaw Deniziak
,
et al.
An symbolic decomposition of functions with multivalued inputs and ou...
...Yet, Cong and Minkovich [
1
] published circuits with known optimal implementation (LEKO) or with known upper bound (LEKU), which are very hard for any synthesis process and causes it to yield results far from optimum; circuits obtained by the synthesis are up to 40x larger than expected...
...When these LEKU benchmarks are synthesized using either opensource or commercial LUT mapping tools, the resulting number of LUTs is sometimes by two orders of magnitude larger than the known lower bound [
1
]...
...The number of 4input LUTs has been chosen as a circuit’s complexity metrics (also in correspondence with [
1
]), so that the upper bound could be easily determined: the minimum number of 4LUTs needed to construct the XOR tree isd(m 1)=3e, where m is the number of the original circuit’s outputs...
Petr Fi
,
et al.
Small but Nasty Logic Synthesis Examples
References
(36)
An Integrated Technology Mapping Environment
(
Citations: 14
)
Alan Mishchenko
,
Satrajit Chatterjee
,
Robert Brayton
,
Maciej Ciesielski
Conference:
International Workshop on Logic & Synthesis  IWLS
, 2005
FPGA technology mapping: a study of optimality
(
Citations: 39
)
Andrew C. Ling
,
Deshanand P. Singh
,
Stephen Dean Brown
Conference:
Design Automation Conference  DAC
, pp. 427432, 2005
Multilevel generalized forcedirected method for circuit placement
(
Citations: 95
)
Tony F. Chan
,
Jason Congy
,
Kenton Sze
Conference:
International Symposium on Physical Design  ISPD
, pp. 185192, 2005
An Enhanced Multilevel Algorithm for Circuit Placement
(
Citations: 52
)
Tony F. Chan
,
Jason Cong
,
Tim Kong
,
Joseph R. Shinnerl
,
Kenton Sze
Conference:
International Conference on Computer Aided Design  ICCAD
, pp. 299306, 2003
Optimality and scalability study of existing placement algorithms
(
Citations: 78
)
ChinChih Chang
,
Jason Cong
,
Min Xie
Conference:
Asia and South Pacific Design Automation Conference  ASPDAC
, pp. 621627, 2003
Sort by:
Citations
(10)
Formal verification of candidate solutions for postsynthesis evolutionary optimization in evolvable hardware
Zdenek Vasicek
,
Lukas Sekanina
Journal:
Genetic Programming and Evolvable Machines  GPEM
, vol. 12, no. 3, pp. 305327, 2011
On logic synthesis of conventionally hard to synthesize circuits using genetic programming
(
Citations: 2
)
P. Fišer
,
J. Schmidt
,
Z. Vašíček
,
L. Sekanina
Conference:
Workshop on Design and Diagnostics of Electronic Circuits and Systems  DDECS
, 2010
A symbolic RTL synthesis for LUTbased FPGAs
Stanislaw Deniziak
,
Mariusz Wisniewski
Conference:
Workshop on Design and Diagnostics of Electronic Circuits and Systems  DDECS
, pp. 102107, 2009
The Case for a Balanced Decomposition Process
Jan Schmidt
,
Petr Fiser
Conference:
Euromicro Symposium on Digital Systems Design  DSD
, pp. 601604, 2009
Case studies in determining the optimal field programmable gate array design for computing highly parallelisable problems
J. E. Rice
,
K. B. Kent
Journal:
Iet Computers and Digital Techniques  IET COMPUT DIGIT TECH
, vol. 3, no. 3, 2009