LEKO and LEKU Suites
(Logic synthesis Examples with Known Optimal/Upperbounds)
Director : Prof. Jason Cong
Author : Kirill Minkovich
CopyrightÂ© 20052008 the Regents of University of California
Abstract
Fieldprogrammable gatearray (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 logicsynthesis and technologymapping 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 logicoptimization and technology mapping problems are NPhard, if we consider area optimization in addition to delay/depth optimization). In this work, 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 Logic synthesis Examples with Known Optimal (LEKO) and Logic synthesis Examples with Known Upper bounds (LEKU), respectively), we show that although leading FPGA technologymapping algorithms can produce close to optimal solutions, the results from the entire logicsynthesis flow (logic optimization + mapping) are far from optimal. The LEKU circuits were constructed to show where the logic synthesis flow can be improved, while the LEKO circuits specifically deal with the performance of the technology mapping. 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 is much room for further research and improvement in FPGA synthesis.
Circuit Description
The LEKO and LEKU suites are developed at UCLA VLSI CAD LAB.
The examples are given in both BLIF and VHLD format and can be downloaded HERE.
Experimental Result
Table 1. Mapping results on LEKO examples
Circuits 
DAOmap 
ABC 
Quartus 
ISE 
Optimal 

LEKO(G_{25}) 
Area 
83 
80 
72 
80 
70 
Ratio 
1.19 
1.14 
1.03 
1.14 
1.00 

LEKO(G_{125}) 
Area 
650 
609 
561 
588 
525 
Ratio 
1.24 
1.16 
1.07 
1.12 
1.00 

LEKO(G_{625}) 
Area 
4435 
4072 
3737 
3974 
3500 
Ratio 
1.27 
1.16 
1.07 
1.14 
1.00 

Average Ratio (using C_{5}) 
1.23 
1.16 
1.05 
1.13 
1.00 

LEKO(G_{36}) 
Area 
139 
149 
121 
158 
120 
Ratio 
1.16 
1.24 
1.01 
1.32 
1.00 

LEKO(G_{216}) 
Area 
1301 
1336 
1082 
1078 
1080 
Ratio 
1.20 
1.24 
1.00 
1.00 
1.00 

LEKO(G_{1296}) 
Area 
10695 
10650 
8645 
8626 
8640 
Ratio 
1.24 
1.23 
1.00 
1.00 
1.00 

Average Ratio (using C_{6}) 
1.20 
1.24 
1.00 
1.10 
1.00 

Average Ratio 
1.22 
1.20 
1.03 
1.12 
1.00 
Table 2. Logic synthesis results on LEKU examples
Circuits 
DAOmap 
ABC 
Quartus 
ISE 
Upper Bounds 

LEKUCD(G_{25}) 
Area 
22,717 
30,511 
10,381 
* 
70 
Ratio 
325 
436 
148 
* 
1 

LEKUCD(G_{25}) 
Area 
25,247 
35,271 
5,005 
9,717 
70 
Ratio 
361 
504 
72 
139 
1 

Average LEKUCD Ratio 
343 
470 
110 
139 
1 

LEKUCB(G_{25}) 
Area 
322 
191 
239 
280 
70 
Ratio 
4.6 
2.7 
3.4 
4.0 
1 

LEKUCB(G_{36}) 
Area 
356 
339 
206 
290 
120 
Ratio 
3.0 
2.8 
1.7 
2.4 
1 

Average LEKUCB Ratio 
3.8 
2.8 
2.6 
3.2 
1 

Average Ratio 
173 
236 
56 
71 
1 
(Note: *The Xilinx mapper was not able to accept a circuit of this size)
Slides from FPGA presentation
You can download it here (please do not duplicated).
References
1. J. Cong and K. Minkovich, "Optimality Study of Logic Synthesis for LUTBased FPGAs," International Symposium on FieldProgrammable Gate Arrays, Feb. 2006.
a. EE Times article (cover story) about the paper (2/20/2006).
a. FPGA Journal article about this paper (4/25/2006).
2. J. Cong and K. Minkovich, "Optimality Study of Logic Synthesis for LUTBased FPGAs," TCAD: Special Edition for FPGA, 2006.
Please direct your questions to cory_m@cs.ucla.edu. Thanks.