J. Cong et Yy. Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs, ACM T DES A, 5(2), 2000, pp. 193-225
Citations number
27
Categorie Soggetti
Computer Science & Engineering
Journal title
ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS
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.