Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-04
2003-07-22
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S625000
Reexamination Certificate
active
06598064
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed, in general, to processing systems and, more specifically, to a multiplier array containing an odd and an even multiplier array for use in a microprocessor.
BACKGROUND OF THE INVENTION
The demand for ever-faster computers requires that state-of-the-art microprocessors execute instructions in the minimum amount of time. Microprocessor speeds have been increased in a number of different ways, including increasing the speed of the clock that drives the processor, reducing the number of clock cycles required to perform a given instruction, implementing pipeline architectures, and increasing the efficiency at which internal operations are performed. This last approach usually involves reducing the number of steps required to perform an internal operation.
Efficiency is particularly important in mathematical calculations, particularly floating point calculations. However, with the trend to increase the integer unit size to 64 bits, many of the problems that previously present only in floating point units are now also occurring in the integer unit. Some mathematical operations, such as multiplication and division, cause significant delays during program execution. Many attempts have been made to design multipliers that have the least number of gate delays possible and that consume the least amount of chip area. A conventional multiplier has a first stage that contains a partial products generating circuit that receives a multiplicand and a multiplier and generates a plurality of partial products therefore. The partial products are then summed in a second stage that contains either a tree adder or an array adder.
For example, the floating point unit in a microprocessor may contain a multiplier that accepts a 64-bit multiplicand and a 64-bit multiplier and generates 64 partial products, P
0
through P
63
. P
0
is the partial product formed by multiplying the multiplicand by the least significant bit of the multiplier. P
63
is the partial product formed by multiplying the multiplicand by the most significant bit of the multiplier. Each partial product is a 64-bit value.
The 64 partial products may then be summed in tree structure, such as a Wallace tree. The tree structure may comprise a first level of 64/3=22 carry-save adders (CSA), each of which adds three 64-bit partial products to generate an output containing a 74-bit sum and a 74-bit carry value. The 22×2=44 outputs of the first level of CSAs are then summed by a second level of 22/3=15 CSAs, each of which adds three outputs from the first level to generate an output containing a 74-bit sum and a 74-bit carry value. The tree structure continues to narrow in subsequent levels of CSAs, wherein each level sums the outputs of the preceding level of CSAs. The 128-bit sum and 128-bit carry outputs of a final CSA are then added in a carry propagate adder (CPA) stage to produce a 64-bit sum output and a single carry bit output. Six levels of CSAs are required to reduce the 64 partial products to the output of the final CSA. Thus, the delay through the tree structure is six times the delay of an individual carry-save adder.
Alternatively, the 64 partial products may be summed in an array of 64 CSAs. In a 64 CSA array, a first CSA may add, for example, the two least significant partial products, P
0
and P
1
. A second CSA then adds the third partial product, P
2
, to the output of the first CSA. A third CSA then adds the fourth partial product, P
3
, to the output of the second CSA. The process continues until a sixty-third CSA adds the sixty-fourth partial product, P
63
, to the output of the sixty-second CSA. Finally, the 64-bit sum and 64-bit carry outputs of the sixty third final CSA are added in a carry propagate adder (CPA) stage to produce a 64-bit sum output and a single carry bit output. Thus, the delay through the array structure is sixty-three times the delay of an individual carry-save adder.
Both the array structure and the tree structure have distinct advantages and disadvantages. The array structure has a comparatively large delay, one for each CSA. However, the array structure is fairly easy to lay out on a silicon wafer because of the repeating pattern of each succeeding CSA. The gate delay is constant for each stage and can be effectively minimized.
The tree structure has a comparatively small delay, at least theoretically. However, the tree structure is limited by the asymmetric routing of its signal lines. When the tree structure is laid out on a silicon wafer and is compressed into a more or less rectangular shape in order to minimize wafer space, there is a large amount of non-uniform line length and non-constant routing density. These problems tend to offset the speed performance realized by the reduced number of gate delays.
Therefore, there is a need in the art for improved microprocessor that execute mathematical operations more rapidly. In particular, there is a need for an improved multiplier that has the simple design advantages of an array structure for summing partial products, but which does not suffer the excessive delays associated with conventional array structures.
SUMMARY OF THE INVENTION
The limitations inherent in the prior art described above are overcome an improved multiplier circuit according to the principles of the present invention. In an advantageous embodiment, the multiplier circuit comprises: 1) a partial products generating circuit capable of receiving a multiplicand value and a multiplier value and generating therefrom a plurality of partial products; 2) a first summation array comprising a first plurality of adders capable of summing a first subset of the plurality of partial products to thereby produce a first summation value; and 3) a second summation array comprising a second plurality of adders capable of summing a remaining subset of the plurality of partial products to thereby produce a second summation value, wherein the remaining subset of the plurality of partial products comprises all of the plurality of partial products not included in the first subset of the plurality of partial products.
According to one embodiment of the present invention, the first subset comprises even ones of the plurality of partial products.
According to another embodiment of the present invention, the remaining subset comprises odd ones of the plurality of partial products.
According to still another embodiment of the present invention, each of the first and second pluralities of adders comprises a carry-save adder.
According to yet another embodiment of the present invention, the multiplier circuit further comprises a final stage carry-save adder capable of summing the first summation value and the second summation value.
According to a further embodiment of the present invention, the first summation value comprises a first N-bit sum value and a first N-bit carry value and the second summation value comprises a second N-bit sum value and a second N-bit carry value and wherein the final stage carry-save adder compresses the first and second summation values to produce a final summation value comprising a final N-bit sum value and a final N-bit carry value.
According to a still further embodiment of the present invention, the multiplier circuit further comprises a carry-propagate adder capable of adding the final N-bit sum value and the final N-bit carry value to produce a 64-bit resulting sum value and a 1-bit resulting carry value.
According to a yet further embodiment of the present invention, the multiplier circuit is disposed in at least one of a floating point unit and an integer unit in a data processor.
The foregoing has outlined rather broadly the features and technical advantages of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features and advantages of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that th
Mai Tan V.
National Semiconductor Corporation
LandOfFree
Split multiplier array and method of operation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Split multiplier array and method of operation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split multiplier array and method of operation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108186