Beyond the Combinatorial Limit in Depth Minimization for LUT-Based FPGA Designs

In this paper, we present an integrated approach to synthesis and mapping to go beyond the combinatorial limit set up by the depth-optimal FlowMap algorithm. The new algorithm, named FlowSYN, uses the global combinatorial optimization techniques to guide the Boolean synthesis process during depth minimization. The combinatorial optimization is achieved by computing a series of minimum cuts of fixed heights in a network based on fast network flow computation, and the Boolean optimization is achieved by efficient OBDD-based implementation of functional decomposition. The experimental results show that FlowSYN improves FlowMap in terms of both the depth and the number of LUTs in the mapping solutions. Moreover, FlowSYN also outperforms the existing FPGA synthesis algorithms for depth minimization