IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1994 · 109 citations · 19 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsField-programmable Gate ArraysOptimizationCircuit ComplexityComputational ComplexityDigital Logic DesignField-programmable Gate Array ArchitectureLogic SynthesisLookup TablesBoolean Circuit ComplexityBoolean FunctionsCircuit MinimizationCircuit Size ComplexityComplexity Of Boolean FunctionsLocal ExploitationLut Size OptimizationPolynomial-time Algorithms
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).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
19
The complexity of satisfiability problems
Thomas J. Schaefer · 1978 · 1.8K citations · Full text
Improved logic synthesis algorithms for table look up architectures
Rajeev Murgai, Narendra Shenoy, Robert K. Brayton et al. · 2002 · 209 citations