Improved heuristics for optimal parallel multiplier synthesis

Abstract

Parallel multipliers are of increasing importance for VLSI design, largely driven by the significant increase in demand for computer graphics and digital signal processing. The fastest (and, when pipelined, most area-efficient) multiplier class is partial product reduction tree (PPRT) based multipliers. The previous best known heuristic for PPRT design (published by Stelling et al.) is capable of producing the fastest possible circuits but suffers an infeasible computational burden. This paper introduces some results which significantly reduce the search space of this heuristic. Consequently, the speed of netlist generation is increased, and the circuits generated retain optimal performance. In addition, larger optimal multipliers may be synthesised due to the easing of the computational burden.