An Exact Gate Decomposition Algorithm for Low-Power Technology Mapping

With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC de-signs. In technology mapping, how decomposition is done can have a significant impact on the power dissipation of the final implementation. In the literature, only heuristic algorithms are given for the low-power gate decomposi-tion problem. In this paper, we prove many properties an optimal decomposition tree must have. Based on these op-timality properties, we design an efficient exact algorithm to solve the low-power gate decomposition problem. More-over, the exact algorithm can be easily modified to a heuris-tic algorithm which performs much better than the known heuristics.