LUT-Based FPGA Technology Mapping for Depth and Area Minimization

In this project, we study technology mapping algorithms for simultaneous depth and area minimization for LUT-based FPGAs. The FlowMap algorithm guarantees the minimum mapping depth for any K-bounded network by computing a min-height K-feasible cut at each node.

We propose to compute min-cost K-feasible cuts in addition to FlowMap's cut computation for area minimization. Three methods are proposed for the min-cost cut computation. Two of them obtain exact solutions based on max-flow and cut enumeration techniques, respectively, while the third method trades cost for speed. Adaptive max-flow computation is employed to ensure the scalability of our algorithms.

Experimental results show that our algorithms obtain the same optimal mapping depth as computed by FlowMap with 8% to 20% of area reduction. Due to adaptive max-flow computation, our algorithm is one order of magnitude faster than FlowMap on large industrial designs. When cut enumeration is employed, our algorithm is 10 times faster than FlowMap for K=4 but is only 2.5 times faster for K=6.

In summary, we have achieved scalable LUT mapping algorithms for simultaneous depth and area minimization in this project.

Cong, J. and Y. Hwang, "Simultaneous Depth and Area Minimization in LUT-Based FPGA Mapping", Proc. ACM/SIGDA Int'l Symp. on Field-Programmable Gate-Arrays, Monterey, California, Feb. 1995.