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 designs. 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 decomposition problem. We prove many properties an optimal decomposition tree must have. Based on these optimality properties, we design an efficient exact algorithm to solve the low power gate decomposition problem. Moreover the exact algorithm can be easily modified to a heuristic algorithm which performs much better than the known heuristics.