Power optimized partial product reduction interconnect ordering in parallel multipliers

When designing the reduction tree of a parallel multiplier, we can exploit a large intrinsic freedom for the interconnection order of partial products. The transition activities vary significantly for different internal partial products. In this work we propose a method for generation of power-efficient parallel multipliers in such a way that its partial products are connected to minimize activity. The reduction tree is designed progressively. A simulated annealing optimizer uses power cost numbers from a specially implemented probabilistic gate-level power estimator and selects a power-efficient solution for each stage of the reduction tree. VHDL simulation using ModelSim shows a significant reduction in the overall number of transitions. This reduction ranges from 15% up to 32% compared to randomly generated reduction trees and is achieved without any noticeable area or performance overhead.