CONG AND HWANG UCLA CSD TR-950001 Abstract Simultaneous Depth and Area Minimization in LUT-based FPGA Mapping

In this paper, we present an improvement of the FlowMap algorithm, named CutMap, which combines depth and area minimization in the mapping process by computing min-cost min-height K-feasible cuts for nodes which are on critical paths for depth minimization and computing min-cost K-feasible cuts for nodes which are not on any critical path for area minimization. CutMap guarantees depth-optimal mapping solutions in polynomial time as the FlowMap algorithm but uses considerably fewer LUTs. We have implemented CutMap and tested it on the MCNC logic synthesis benchmarks. For depth-optimal mapping solutions, CutMap uses 20 % fewer K-LUTs than FlowMap without post-processing, and uses 13 % fewer K-LUTs than FlowMap when post-processing operations for area minimization are applied to both solutions. When targeting for Xilinx X3000 FPGA family, CutMap uses 11 % fewer CLBs than FlowMap. We also tested CutMap followed by the depth relaxation routines in FlowMap_r algorithm, which achieves area minimization by depth relaxation. CutMap followed FlowMap_r performs better than FlowMap_r. 1 CONG AND HWANG UCLA CSD TR-95000