Horizontally pipelined multiplier circuit

A multiplier circuit (300, 400, 500, 600) uses a horizontal pipelining of the circuitry (301, 401, 501, 601) in order to reduce the number of gate-drain delays within the various data paths through the array (301, 401, 501, 601). Additionally, a combination of vertical and horizontal pipelining (550, 650) may also be implemented. The multiplier circuit (400, 600) may implement a modified Booth's algorithm. A horizontal pipeline latch (350, 450, 550, 650) operates to divide the array (301, 401, 501, 601) into two portions, where the first portion (360, 460, 560, 660) operates on the least significant bits of the resulting product, while the second portion (361, 461, 561, 661) operates on the most significant bits of that product.

FIELD OF THE INVENTION 
The present invention relates in general to multiplier circuits, and in 
particular, to a multiply-accumulate circuit. 
BACKGROUND OF THE INVENTION 
Multiply or multiply-accumulate ("MAC") circuits are an integral part of 
all digital signal processors ("DSPs") and many microprocessors and 
microcontrollers. These circuits are logically complex, and even after 
many generations of optimization contain many long propagation delay paths 
from input to output. These paths often become the critical delay path of 
the entire DSP or microprocessor. 
In many cases, the critical feature of a multiplier circuit is that it 
complete one multiply operation on each clock cycle. Therefore, it is 
important that the multiplier circuit not cause too much delay resulting 
in a slower clock speed. The fact that the output of the multiplier 
circuit is delayed by one clock cycle is of no consequence as long as 
there is an output on each clock cycle. This makes the multiplier circuit 
amenable to pipelining. 
This problem can be more readily seen by referring to FIG. 1, which 
illustrates MAC 100 implementing a modified Booth's algorithm. MAC 100 
includes X-input latch 102 and Y-input latch 103. Latches 102 and 103 
receive from external circuitry (not shown) two operands (hereinafter also 
referred to as the multiplicand and the multiplier), which are to be 
multiplied by each other and simultaneously added to the previous result 
to produce an accumulating product, which is eventually produced and 
stored within result latch 106. The previous result is input to array 101 
via feedback loop 120. Latches 102 and 103 may be of any size, for 
example, MAC 100 may be operable to multiply two 16-bit operands, or 
operands of different bit lengths. 
Coupled to Y-input latch 103 is recoder circuit 104, which is typically a 
part of a MAC implementing a modified Booth's algorithm. 
The outputs of X-input latch 102 and recoder 104 are entered into 
multiplexer/adder array 101, which is also comprised of conventional 
combinational logic circuitry implemented within MACs. Array 101 is shown 
as a non-rectangular parallelogram, which depicts the general shape of the 
circuitry when horizontal and vertical data flow through array 101 has 
been aligned to an orthogonal axis. 
The output from array 101 is entered into accumulator 105, which performs 
the final addition of the partial products of the Booth's algorithm and of 
the previously accumulated result. Such a chain of multiply-accumulate 
operations may be depicted as: (x1*y1)+(x2*y2)+(x3*y3) . . . . An example 
of a typical MAC and the various elements within a MAC are described in 
U.S. Pat. No. 4,575,812, issued Mar. 11, 1986 to Kloker, et al., which is 
hereby incorporated by reference herein. 
As an example of the usage of a MAC within a DSP, each of the "x" values 
may represent a data sample, while each of the "y" values may represent a 
coefficient of an impulse response as a signal is passed through a filter. 
Dashed line 190 represents the direction of travel of output bits through 
array 101. Dashed line 192 represents the direction of travel of the 
output values from recoder 104 through array 101. And, dashed line 191 
generally represents the direction of travel of the X-input bits and the 
carry-save values through array 101. 
Latches 102, 103, and 106 set the bounds on the propagation delay through 
combinational logic block 150. Several examples of critical signal paths 
of this delay are represented by the heavy lines 110-112 originating at 
the top of Y-input latch 103 to the far left portion of result latch 106. 
A signal path comprises all the circuitry in combinational logic block 150 
through which a particular signal "travels." Signal paths 110-112 include 
a number of gate-drain delays of transistors during operation of 
combinational logic block 150. Paths 110 and 112, plus many more that can 
be envisioned between these two, are roughly equal in delay. Optimizing 
one signal path, such as path 111 will then necessitate the need to 
optimize another path, such as path 110. The problem is that any one path 
through combinational logic block 150 cannot be optimized at the expense 
of another. 
As noted above, the goal is for the operation of combinational logic block 
150 to occur in one clock cycle. The faster the throughput of the data 
through combinational logic block 150 (the less the number of gate drain 
delays), the faster the clock that can be utilized to operate MAC 100, and 
correspondingly, the faster the clock that may be used to time the 
operation of the microprocessor, microcontroller, or DSP embodying MAC 
100. 
One way to solve the foregoing problem and reduce the amount of delay 
caused by the gate-drain delays within the circuitry combinational logic 
block 150 is to pipeline the functions of MAC 100. When such a prior art 
circuit as MAC 100 is pipelined, it is typically done by putting a latch 
at the output of recoder 104, placing a latch circuit between array 101 
and final adder/accumulator 105, or both. However, it is obvious by 
viewing MAC 100 that neither of these is an optimum location for such a 
pipeline latch. An optimum location would be at approximately the halfway 
point of all the parallel signal paths in combinational logic block 150. 
This would be a diagonal line from the upper left of FIG. 1 to the lower 
middle. However, a diagonal break for such a pipeline is not feasible 
because the accumulator result must be delayed by only one clock before it 
is fed back by feedback path 120 to the input of array 101, and such a 
diagonal break would not permit this. 
Thus, there is a need in the art for a multiplier circuit where the 
gate-drain delays through the multiplexer, adder array within the 
multiplier circuit are minimized.

DESCRIPTION OF THE PREFERRED EMBODIMENT 
In the following description, numerous specific details are set forth such 
as specific word or byte lengths, etc. to provide a thorough understanding 
of the present invention. However, it will be obvious to those skilled in 
the art that the present invention may be practiced without such specific 
details. In other instances, well-known circuits have been shown in block 
diagram form in order not to obscure the present invention in unnecessary 
detail. For the most part, details concerning timing considerations and 
the like have been omitted inasmuch as such details are not necessary to 
obtain a complete understanding of the present invention and are within 
the skills of persons of ordinary skill in the relevant art. 
Refer now to the drawings wherein depicted elements are not necessarily 
shown to scale and wherein like or similar elements are designated by the 
same reference numeral through the several views. 
Referring next to FIG. 2, there is illustrated one pipeline scheme used 
within a MAC implementing a modified Booth's algorithm. MAC 200 is similar 
to MAC 100 in that X-input latch 202, Y-input latch 203, recoder 204, 
multiplexer(mux)/adder array 201, accumulator 205, and result latch 206 
are similar to those corresponding elements implemented within MAC 100. 
However, MAC 200 is modified to include adder 207 and pipeline register 
208 between array 201 and accumulator 205. Adder 207 is included at the 
output of array 201 to collect carry values produced within mux/adder 
array 201. 
A multiplexer/adder array typically uses "carry-save" adders, which are 
faster than "carry-propagate" adders. For such a carry-save adder array, 
there is a final adder near the output which resolves the plurality of 
"saved" carry bits with the plurality of "sum" bits into a plurality of 
sum bits with a single carry bit. In MAC 100, this function is combined 
with the accumulate function in final adder/accumulator 105. In MAC 200, 
this function is performed separately, since adder 207 is separated from 
accumulator 205 by pipeline register 208. 
In MAC 200, the multiply function, X*Y=Z, is separated from the accumulate 
function, A=Z+A.sub.PREVIOUS, by pipeline register 208. This architecture 
is used because only a single latch is used in accumulator feedback path 
220. In contrast, if the output of result latch 206 is fed back to array 
201, then two latches would be in this feedback loop. Feedback path 220 is 
not coupled to the input of array 201, but is instead coupled to the input 
of accumulator 205 from result latch 206. However, with such a 
configuration, an accumulator input at the input, or the top, of array 201 
is not used. 
Again, example gate-drain delay paths 210-212 are shown. The configuration 
of MAC 200 reduces the number of gate-drain delays within the longest path 
in MAC 200 relative to the longest gate-drain delay path within MAC 100. 
This reduction is due to the fact that delays within recoder 204 and 
accumulator 205 are now in parallel, and not in series. Recoder 204 is now 
in series with adder 207, which is faster than placing recoder 204 in 
series with accumulator 205. Since the delay in recoder 204 is small, the 
improvement in total delay is also small. 
Referring next to FIG. 4, there is illustrated one embodiment of the 
present invention. Y-input latch 403, recoder 404, and mux/adder array 401 
operate in a manner similar to the operation of the corresponding elements 
described above with respect to FIGS. 1 and 2. However, the operation of 
array 401 has been divided into array portions 460 and 461. Furthermore, 
accumulators 405 and 462 operate in a manner similar to accumulator 205, 
except that the duties of the accumulator circuit have been divided into 
the two accumulator portions 405 and 462. 
MAC 400 utilizes a vertical break in array 401 and the accumulator 
resulting in a "horizontal" pipeline. Horizontal pipeline latch 450 
captures (1) all signals crossing the boundary from array portion 460 to 
array portion 461, which signals as noted above with respect to FIG. 1, 
comprise particular carry-save values and recoder outputs, which are being 
bussed across array 401, and (2) the carry propagation from accumulator 
portion 405 to accumulator portion 462. 
X-input latch 402 is identical to latch 202. An additional X-delayed latch 
442 is added to delay the most significant bits of the output of latch 
402. X-delayed latch 442 is used to align in time the X-input data into 
array 461 with the recoded Y-input data that has been delayed by pipeline 
latch 450. 
In MAC 400, a single clock delay is preserved in accumulator feedback paths 
420 and 421, because path 420 or path 421 does not pass through pipeline 
latch 450. 
The output of accumulator 405 is coupled to result latch 406. 
Furthermore, results from accumulator 462 are passed to result latch 463. 
The two values within result latches 406 and 463 may be re-synchronized by 
result delay latch 441, which is coupled to the output of result latch 
406. 
In circuit 400, the least significant portion of the multiply-accumulate 
function operates in a different clock cycle than the most significant 
portion. In circuit 200, the multiply function operates in a different 
clock cycle than the accumulate function. 
An advantage of circuit 400 is that it reduces the number of gate-drain 
delays significantly, thus allowing for a faster clock signal to be used 
in operating MAC 400. This is accomplished because the long serial path 
through the recoder followed by the accumulator has been broken by 
pipeline latch 450 closer to the path's midpoint; thus, the longest path 
length is reduced. 
The location of pipeline latch 450 within array 401 may be varied as 
desired. Typically, the location of pipeline latch 450 is set to equalize 
the length of the longest path in the most significant portion with the 
longest path in the least significant portion of circuit 400. Recall that 
the least significant portion of circuit 400 passes through array 460 and 
accumulator 405, while the most significant portion of circuit 400 passes 
from latch 442 through array 461 and accumulator 462. 
Circuit 400 is an example of an implementation of the horizontal pipeline 
within a multiply-accumulate circuit using the modified Booth's algorithm. 
The horizontal pipeline can be similarly utilized in a multiply only 
circuit without accumulate, or in a multiplier only or MAC that does not 
use the modified Booth's algorithm. Two of these options are illustrated 
in FIG. 3. 
Referring next to FIG. 3, there is illustrated multiplier 300, which is a 
multiplier only and not a multiply-accumulate circuit. Accumulators have 
been replaced with carry-propagate adders 340 and 362, and recoder 304 is 
shown as being optional, depending on whether or not multiplier 300 
implements a modified Booth's algorithm. Furthermore, Y-input latch 303, 
X-input latch 302, X delayed latch 342, array portion 360, pipeline latch 
350, and array portion 361 operate similar to corresponding elements 
Y-input latch 403, X-input latch 402, X delayed latch 442, array portion 
460, pipeline latch 450, and array portion 461 of MAC 400. However, since 
an accumulate function is not needed, feedback portions 420 and 421 have 
been removed. 
Multiplier 300 represents a more general multiplier, not necessarily 
implementing a modified Booth's algorithm. Nevertheless, multiplier 300 
employs the same advantages with respect to the gate-drain delay 
parameters as MAC 400 in that pipeline latch 350 operates similarly to 
pipeline latch 450. 
Referring next to FIG. 6, there is illustrated another alternative 
embodiment of the present invention, which utilizes vertical and 
horizontal pipeline latches. MAC 600 is similar to MAC 400 except that 
there is no analog to X-delayed latch 442; X-input latch 602 is instead 
similar to X-input latch 202 of MAC 200. Furthermore, MAC 600 includes 
pipeline latch 650. This is an extended version of latch 450 and has both 
a vertical and a horizontal component. 
Multiplexer-adder array 601 is identical to array 401. It is shown as 
separate parts 660 and 661 to maintain data alignment with the accumulator 
which has been divided into two portions, 605 and 662. Pipeline latch 650 
consists of both horizontal and vertical components and separates the most 
significant portion 662 of the accumulator from portion 605. Similar to 
adder 207 described previously, adder 607 is required to resolve the 
interim sum and plurality of saved carry signals from mux/adder array 601 
into a final output and single carry signal. Adder 607 can be placed on 
either side of pipeline latch 650. When adder 607 is configured as shown 
in FIG. 6, MAC 600 is usually slightly faster, but when adder 607 is 
placed above pipeline latch 650, MAC 600 is significantly smaller. This is 
because approximately half the number of signals would have to be latched 
in this case. 
As can be seen by the dissimilarity of the implementation of accumulator 
feedback signals 621 and 620, accumulator portions 605 and 662 operate 
differently. This is because only a single latch is allowed in an 
accumulator feedback path. Portion 605 uses feedback path 621 which is 
similar to path 120 of MAC 100. This is a more efficient circuit 
implementation, but it is not used with respect to portion 662 because the 
resultant feedback loop would include both result latch 663 and pipeline 
latch 650. Furthermore, feedback path 620 is similar to feedback path 220 
in MAC 200. 
MAC 600 incorporates an efficient pipeline to MAC 100 because not only are 
the delay paths equalized on each side of pipeline latch 650, but the 
number of gate-drain delays in each of these paths is approximately half 
the number of gate drain delays in the longest path of MAC 100. 
Circuit 600 is an example of an implementation of the combination 
horizontal-vertical pipeline within a multiply-accumulate circuit using 
the modified Booth's algorithm. The combination horizontal-vertical 
pipeline can be similarly utilized in a multiply only circuit without 
accumulate or in a multiplier only or a MAC that does not use the modified 
Booth's algorithm. Two of these options are illustrated in FIG. 5. 
Referring next to FIG. 5, there is illustrated multiplier circuit 500, 
which is similar to MAC 600, except that adder 607 has been removed, and 
accumulator portions 605 and 662 have been replaced with carry-propagate 
adders 540 and 562, respectively. Furthermore, recoder 504 is optional 
depending on whether or not multiplier circuit 500 implements a modified 
Booth's algorithm. Nevertheless, the advantages of MAC 600 are also 
included within multiplier circuit 500 in that multiplier circuit 500 has 
reduced gate-drain delay paths, therefore permitting multiplier circuit 
500 to operate with a faster clock signal. 
Referring next to FIG. 7, there is illustrated, in block diagram form, 
processor or DSP 700, which includes any one of circuits 200, 300, 400, 
500, or 600 discussed above. This illustrates that the multiplier or MAC 
circuits (with or without an implementation of modified Booth's algorithm) 
may be used within a microprocessor or a DSP. 
Although the present invention and its advantages have been described in 
detail, it should be understood that various changes, substitutions and 
alterations can be made herein without departing from the spirit and scope 
of the invention as defined by the appended claims.