Academic
Publications
Optimality Study of Logic Synthesis for LUT-Based FPGAs

Optimality Study of Logic Synthesis for LUT-Based FPGAs,10.1109/TCAD.2006.887922,IEEE Transactions on Computer-aided Design of Integrated Circuits and

Optimality Study of Logic Synthesis for LUT-Based FPGAs   (Citations: 10)
BibTex | RIS | RefWorks Download
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 ,near-optimal 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 NP-hard 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
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.
    • ...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 hard-to-synthesize substructures [5, 10]...

    Zdenek Vasiceket al. Formal verification of candidate solutions for post-synthesis evolutio...

    • ...Not only their ever-increasing 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 (look-up table) mappers...
    • ...Designers have objected to the Cong & Minkovich’s LEKU circuits [20], since they are artificially constructed...

    P. Fišeret 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 Schmidtet 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 Deniziaket al. An symbolic decomposition of functions with multi-valued 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 open-source 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 4-input 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 4-LUTs needed to construct the XOR tree isd(m 1)=3e, where m is the number of the original circuit’s outputs...

    Petr Fiet al. Small but Nasty Logic Synthesis Examples

Sort by: