Complexity of the lookup-table minimization problem for FPGA technology mapping
- 1 November 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 13 (11) , 1319-1332
- https://doi.org/10.1109/43.329262
Abstract
One of the main objectives in the process of mapping a digital circuit onto a LUT-based FPGA structure is minimizing the total number of lookup tables needed to implement the circuit. This will increase the size of the circuit that can be implemented using the available FPGA structure. In this paper, we show that even restricted cases of the lookup-table minimization for FPGA technology mapping are NP-complete (even when K is a small constant), and that it can be solved optimally for all values of K on a tree input in O(min{nK, nlogn}) time where n is the number of nodes in the network and K is the input capacity of the LUT's. Based on our algorithm for trees, we present a polynomial time heuristic algorithm for general Boolean networks. Experimental results confirm substantial decrease on the number of LUT's on a number of MCNC logic synthesis benchmarks compared to the algorithms that allow no or just local exploitation of Boolean properties of the circuit. We obtain 10% to 80% improvement on the number of LUT's compared to the previous algorithms (even though we allow very limited operations, e.g., we do not exploit Boolean properties of the circuits or decompose nodes).Keywords
This publication has 14 references indexed in Scilit:
- A near optimal algorithm for technology mapping minimizing area under delay constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Area and delay mapping for table-look-up based field programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Improved logic synthesis algorithms for table look up architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Performance directed synthesis for table look up programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Chortle: a technology mapping program for lookup table-based field programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On area/depth trade-off in LUT-based FPGA technology mappingPublished by Association for Computing Machinery (ACM) ,1993
- Performance directed technology mapping for look-up table based FPGAsPublished by Association for Computing Machinery (ACM) ,1993
- Technology mapping of lookup table-based FPGAs for performancePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Chortle-crf: Fast technology mapping for lookup table-based FPGAsPublished by Association for Computing Machinery (ACM) ,1991
- The Synthesis of Two-Terminal Switching CircuitsBell System Technical Journal, 1949