An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs

In this paper we present a polynomial time technology mapping algorithm, called Flow-Map, that optimally solves the LUT-based FPGA technology mapping problem for depth minimization for general Boolean networks. This theoretical breakthrough makes a sharp contrast with the fact that 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 net- work, solved by network flow computation. Our algorithm also effectively minimizes the number of LUTs by maxim- izing the volume of each cut and by several postprocess- ing operations. We tested the Flow-Map algorithm on a set of benchmarks and achieved reductions on both the network depth and the number of LUTs in mapping solu- tions as compared with previous algorithms.