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 # 3 and remains NP-hard for K-bounded networks when K # 5. Based on these results, we propose two new structural gate decomposition algorithms, named DOGMA and DOGMA-m, which combine the level-driven nodepacking 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 step