LEKO/LEKU

Software description:

LEKO and LEKU Suites [GitHub]

(Logic synthesis Examples with Known Optimal/Upper-bounds)

Abstract

Field-programmable gate-array (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 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 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 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.

Experimental Result

Table 1. Mapping results on LEKO examples

Circuits		DAOmap	ABC	Quartus	ISE	Optimal
LEKO(G₂₅)	Area	83	80	72	80	70
LEKO(G₂₅)	Ratio	1.19	1.14	1.03	1.14	1.00
LEKO(G₁₂₅)	Area	650	609	561	588	525
LEKO(G₁₂₅)	Ratio	1.24	1.16	1.07	1.12	1.00
LEKO(G₆₂₅)	Area	4435	4072	3737	3974	3500
LEKO(G₆₂₅)	Ratio	1.27	1.16	1.07	1.14	1.00
Average Ratio (using C₅)		1.23	1.16	1.05	1.13	1.00
LEKO(G₃₆)	Area	139	149	121	158	120
LEKO(G₃₆)	Ratio	1.16	1.24	1.01	1.32	1.00
LEKO(G₂₁₆)	Area	1301	1336	1082	1078	1080
LEKO(G₂₁₆)	Ratio	1.20	1.24	1.00	1.00	1.00
LEKO(G₁₂₉₆)	Area	10695	10650	8645	8626	8640
LEKO(G₁₂₉₆)	Ratio	1.24	1.23	1.00	1.00	1.00
Average Ratio (using C₆)		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
LEKU-CD(G₂₅)	Area	22,717	30,511	10,381	*	70
LEKU-CD(G₂₅)	Ratio	325	436	148	*	1
LEKU-CD(G₂₅)	Area	25,247	35,271	5,005	9,717	70
LEKU-CD(G₂₅)	Ratio	361	504	72	139	1
Average LEKU-CD Ratio		343	470	110	139	1
LEKU-CB(G₂₅)	Area	322	191	239	280	70
LEKU-CB(G₂₅)	Ratio	4.6	2.7	3.4	4.0	1
LEKU-CB(G₃₆)	Area	356	339	206	290	120
LEKU-CB(G₃₆)	Ratio	3.0	2.8	1.7	2.4	1
Average LEKU-CB 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 LUT-Based FPGAs," International Symposium on Field-Programmable 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 LUT-Based FPGAs," TCAD: Special Edition for FPGA, 2006.

Publications:

Optimality Study of Logic Synthesis for LUT-Based FPGAs

Year:

2006

Main menu