In this project, we study structural gate decomposition algorithms applicable
to 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 will result in an optimal mapping depth smaller
than or equal to that of the original network, regardless of the decomposition
method used, and (2) depth-optimal structural gate decomposition on simple-gate
networks is NP-hard.
We propose two new structural gate decomposition algorithms, named DOGMA
and DOGMA-m, which combine the level-driven node packing technique (Chortle-d)
and the network flow based labeling technique (FlowMap) for depth-optimal
technology mapping. Compared with previous structural gate decomposition
algorithms, an algebraic decomposition algorithm speed_up, and a Boolean
decomposition approach TOS, experimental results show that
(1) both the optimal mapping depth and the optimal duplication-free mapping
area are reduced by 16% when 5-bounded networks are decomposed structurally
into 2-bounded networks
(2) DOGMA-m results in the smallest mapping depth and mapping area among
five structural gate decomposition algorithms
(3) DOGMA-m can complete gate decompositions for all tested benchmarks
in a short time while speed_up and TOS can not, but speed_up results in
the smallest mapping depth and mapping area among the structural, algebraic,
and Boolean approaches under comparison.
|