Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs
In this paper we study structural gate decomposition in general, simple gate networks for depth-optimal technology mapping using K-input Lookup-Tables (K-LUTs). We show that (1) structural gate decomposition in any K-bounded network results in an optimal mapping depth smaller than or equal to that of the original network, regardless of the decomposition method used; and (2) the problem of structural gate decomposition for depth-optimal technology mapping is NP-hard for K-unbounded networks when K greater than or equal to 3 and remains NP-hard for K-bounded networks when K greater than or equal to 5. Based on these results, we propose two new structural gate decomposition algorithms, named DOGMA and DOGMA-m, which combine the level-driven node-packing technique (used in Chortle-d) and the network flow-based labeling technique (used in FlowMap) for depth-optimal technology mapping. Experimental results show that (1) among five structural gate decomposition algorithms, DOGMA-m results in the best mapping solutions; and (2) compared with speed_up (an algebraic algorithm) and TOS (a Boolean approach), DOGMA-m completes decomposition of all tested benchmarks in a short time while speed_up and TOS fail in several cases. However, speed_up results in the smallest depth and area in the following technology mapping steps.
decomposition technology mapping fpga computer-aided design of vlsi delay minimization logic optimization programmable logic simplification synthesis system design