Title :
An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs
Author :
Cong, J. ; Ding, Y.
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
Abstract :
Presents a polynomial time technology mapping algorithm, called Flow-Map, that optimally solves the lookup-table (LUT)-based field-programmable gate array (FPGA) technology mapping problem for depth minimization for general Boolean networks. This theoretical breakthrough makes a sharp contrast with the fact that the conventional technology mapping problem in library-based designs is NP-hard. A key step in Flow-Map is to compute a minimum height K-feasible cut in a network, solved by network flow computation. The algorithm also effectively minimizes the number of LUTs by maximizing the volume of each cut and by several postprocessing operations. The Flow-Map algorithm was tested on a a set of benchmarks and achieved reductions of both the network depth and the number of LUTs in mapping solutions as compared with previous algorithms.<>
Keywords :
computational complexity; delays; logic CAD; logic arrays; minimisation of switching nets; table lookup; Flow-Map; benchmarks; cut volume maximization; delay optimization; depth minimization; field-programmable gate array; general Boolean networks; library-based designs; lookup-table based FPGA designs; minimum height K-feasible cut; network depth; network flow computation; optimal technology mapping algorithm; polynomial time algorithm; postprocessing operations; Complexity theory; Delay effects; Design automation; Logic arrays; Minimization methods; Table lookup;
Conference_Titel :
Computer-Aided Design, 1992. ICCAD-92. Digest of Technical Papers., 1992 IEEE/ACM International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-3010-8
DOI :
10.1109/ICCAD.1992.279398
