The systematic exploration of pipelined array multiplier performance

The throughput of a combinational array multiplier is shown to be asymptotically suboptimal using performance measures derived from VLSI models of computation. Applying a systematic transformation called retiming, a class of asymptotically optimal pipelined array multipliers is obtained. The optimum circuit performance within this class must be deternmined empirically through repeated iterations of multiplier layout generation, circuit extraction, and electrical simulation. The structure of these pipelined multipliers facilitates such an empirical investigation by admitting very regular layouts that can be generated quickly and interactively.