Pipelining of Arithmetic Functions

Abstract

Two addition and three multiplication algorithms were studied to see the effect of pipelining on system efficiency. A definition of efficiency was derived to compare the relative merits of various algorithms and implementations for addition and multiplication. This definition is basically defined as bandwidth cost. Previous comparisons of adders and multipliers have generally been based on latency. In a pipeline environment, latency (or its inverse bandwidth) is not as important. Any bandwidth is possible up to the physical limitations on gate delay variations and pulse skew. The formal definition for efficiency is efficiency = N/D·G where N is the number of bits in the operands, D is the delay (uniform) of each pipeline stage in units of gate delays, and G is the total number of gates, including any used for latching. In cases where gate variations and pulse skewing are well defined, pipelining using the Earle latch results in increased efficiency. The most efficient adder is a maximally pipelined conditional-sum adder (three stages with a delay of four gates per stage). Its efficiency is 6.30×10^-3. The most efficient multiplier is a maximally pipelined tree multiplier (eight stages with a delay of four gates per stage). Its efficiency is 3.48×10^-4.