COMPLEXITY OF THE LOOKUP-TABLE MINIMIZATION PROBLEM FOR FPGA TECHNOLOGY MAPPING

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 loo kup tables needed to implement the circuit. This will increase the siz e of the circuit that can be implemented using the available FPGA stru cture. 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 a ll values of K on a tree input in O(min{nK, nlogn}) time where n is th e number of nodes in the network and K is the input capacity of the LU T's. Based on our algorithm for trees, we present a polynomial time he uristic algorithm for general Boolean networks. Experimental results c onfirm substantial decrease on the number of LUT's on a number of MCNC logic synthesis benchmarks compared to the algorithms that allow no o r just local exploitation of Boolean properties of the circuit. We obt ain 10% to 80% improvement on the number of LUT's compared to the prev ious algorithms (even though we allow very limited operations, e.g., w e do not exploit Boolean properties of the circuits or decompose nodes ).