Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs

In this paper we study structural gate decomposition in general, simple gat e 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 o f 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 t o 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 decomposi tion algorithms, named DOGMA and DOGMA-m, which combine the level-driven no de-packing technique (used in Chortle-d) and the network flow-based labelin g technique (used in FlowMap) for depth-optimal technology mapping. Experim ental results show that (1) among five structural gate decomposition algori thms, DOGMA-m results in the best mapping solutions; and (2) compared with speed_up (an algebraic algorithm) and TOS (a Boolean approach), DOGMA-m com pletes decomposition of all tested benchmarks in a short time while speed_u p and TOS fail in several cases. However, speed_up results in the smallest depth and area in the following technology mapping steps.