Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-27
2004-05-25
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06742012
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the field of data processing systems. More particularly, this invention relates to data processing systems of the type that perform multiplication operations.
There are a number of ways in which multiplication of two W bit numbers M and N may be performed. For example, a W×W bit multiplier may be provided for producing the multiplication result M×N directly. However, the larger the multiplier circuit is, then generally the more power and circuit area it will consume, and accordingly in applications where reduction in power and circuit area are of importance, it is known to provide a W×W/2 multiplier that can perform two separate multiplications which are then summed together to produce the result M×N. Hence, the multiplication M×N is performed as follows:
M
lower
×N+M
upper
×N
In the above equation, M
lower
indicates the least significant W/2 bits of M, whereas M
upper
indicates the most significant W/2 bits of M. The first multiplication above will be referred to as the lower multiplication, whilst the second multiplication will be referred to as the upper multiplication.
Both of the above multiplications produce a result which is 3W/2 bits wide, but the upper multiplication result is shifted to be W/2 bits more significant than the lower multiplication result. Hence, when the two multiplication results are added, the final multiplication result will be 2W bits wide as indicated below:
Lower
Product
Upper
Product
+
A
A
A
B
B
B
C
C
C
C
(where each capital letter represent a W/2 bit number)
Such a multiplication is typically achieved by calculating the lower multiplication result M
lower
×N first, and then recirculating part of the result for accumulation into the upper multiplication M
upper
×N. It should be noted that the least significant W/2 bits of the final multiplication result are identical to the least significant W/2 bits of the lower product, but the same does not apply for the most significant W/2 bits of the final multiplication result when compared with the most significant W/2 bits of the upper product, because a carry may propagate up the chain.
Although the upper and lower products are shown offset from each other by W/2 bits, they are produced in the same bit positions in the final adder of the multiplier. This has the consequence that the least significant W/2 bits of the final multiplication result, which are available once the lower product has been calculated, must be stored immediately, because they will be overwritten by the rest of the multiplication result after the upper product has been calculated and added to the relevant bits of the lower product. Extra logic then needs to be provided to produce the final multiplication result from the two intermediate results, i.e. the previously stored least significant W/2 bits of the multiplication result and the rest of the multiplication result subsequently output by the final adder of the multiplier. In addition, further logic is also required to allow full carry propagation when performing an accumulation of the two separate multiplication results as discussed above.
Generally, it is desirable to reduce power consumption and circuit complexity wherever possible, and accordingly it would be desirable to provide a technique which enables two W bit data words to be multiplied together using a multiplying circuit that is arranged to perform a multiplication of a W2 bit data value by a W bit data value whilst enabling reduction in the power consumption and complexity of the multiplying circuit in relation to the above discussed prior art.
SUMMARY
Viewed from a first aspect, the present invention provides apparatus for processing data, said apparatus comprising: a multiplying circuit for performing a multiplication of a W/2 bit data value by a W bit data value; an instruction decoder responsive to a multiply instruction to control said multiplying circuit to generate a multiplication result for the computation M×N, where M and N are W bit data words, the multiplying circuit being arranged to execute a first operation in which the data word N is multiplied by the most significant W/2 bits of the data word M to generate a first intermediate result having 3W/2 bits, and to then execute a second operation in which the data word N is multiplied by the least significant W/2 bits of the data word M to generate a second intermediate result having 3W/2 bits, the first intermediate result being shifted by W/2 with respect to the second intermediate result and added to the second intermediate result to generate the multiplication result.
In accordance with the present invention, a multiply instruction is provided which causes the multiplying circuit to perform the two constituent multiplication operations in reverse order to that performed in the earlier-described prior art approach. Since the first operation is used to multiply the data word N with the most significant W/2 bits of the data word M, this first operation will not directly produce any bits of the multiplication result, and accordingly any final adder circuitry provided within the multiplying circuit can be turned off when the first operation is executing, thereby reducing power consumption. Further, since none of the bits of the multiplication result are produced by the first operation, the multiplying circuit will not output any bits after execution of the first operation which require storing, and further there is no need for any extra logic as was required in the prior art approach to concatenate a data value output after execution of the first operation with a data value produced in a subsequent operation.
The prior art approach, whereby the least significant W/2 bits of the multiplicand are multiplied by the multiplier, and then the upper W/2 bits of the multiplicand are multiplied by the multiplier, with the appropriately shifted results then being summed to produce the final multiplication result, is the most intuitive approach, as it appears in keeping with the requirement to propagate a carry from the least significant bit to the most significant bit where necessary. Further, this prior art approach would appear to provide good processing speed in certain instances, since considering the example where a 2W bit result is to be produced, the least significant W/2 bits of the result are generated from the lower product and the remaining 3W/2 bits are generated from the upper product, i.e. only two operations seem necessary.
However, in practice, the perceived speed of the prior art approach is often adversely affected, since, for example, the register bank into which the result needs to be placed may comprise W bit registers, and may only have one write port. In such situations it takes two cycles to write to the register bank the 3W/2 bits of the result produced by the upper product.
In contrast to the prior art approach, the approach of the present invention, whereby the two operations are reversed, is entirely counterintuitive, but has been found to produce the above-described surprising benefits of reducing the overall complexity of the data processing apparatus, and facilitating reduction in power consumption.
In accordance with a first embodiment, the multiply instruction specifies a W bit multiplication result, and the second operation is further arranged to cause the multiplying circuit to sum the least significant W bits of the first and second intermediate result to generate a third intermediate result having 3W/2 bits, the multiplication result being given by the least significant W bits of the third intermediate result. In accordance with this embodiment, the W bit multiplication result is produced in one go at the end of the second operation. It will be seen that when compared with the standard prior art approach, where the least significant W/2 bits are produced after execution of the first operation, the most significant W/2 bits are produced after execution of the second
Arm Limited
Malzahn David H.
Nixon & Vanderhye P.C.
LandOfFree
Apparatus and method for performing multiplication operations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for performing multiplication operations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for performing multiplication operations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3239180