Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-11-06
2001-01-09
Mai, Tan V. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S525000
Reexamination Certificate
active
06173303
ABSTRACT:
TECHNICAL FIELD
The present invention relates to multiplier circuits and, in particular, to a multiplier circuit that eliminates partial product combination operations where it is detected that those operations will not affect a final result of the multiplication.
BACKGROUND
Multiplication is one of the most time-consuming arithmetic operations for a processor to perform. As a result, much effort has been expended at making the multiplication operation more efficient. In many instances, the success of a particular effort has been measured by determining if it results in an acceptable tradeoff between the number of clock cycles required to execute a multiply operation, versus the amount of hardware required to implement the execution. For example, a 16-bit by 16-bit multiply instruction can be executed in one clock cycle (or a small number clock cycles, accounting for instruction execution overhead) if a 16×16 hardware multiplier is used, but the same instruction will take more clock cycles if a smaller multiplier is used.
Other approaches have been taken as described, for example, in U.S. Pat. Nos. 5,557,563 and 4,276,607. The disclosures of these patents are summarily described here and, for full details, the reader is referred directly to their disclosures.
U.S. Pat. No. 5,557,563 to Larri et al. describes a processor circuit that terminates a multiply instruction based on the one of the input operands being small, limiting the number of bits of the result. The circuit described by Larri et al. can terminate the multiply operation after one, two, three or four iterations of the multiplier core. See, e.g., col. 5, lines 57-58.
U.S. Pat. No. 4,276,607 to Wong describes a processor circuit that detects trailing zeros in a multiplier operand, and performs the multiplication operation only beginning with that word which is the lowest order word having a non-zero content.
What is desired is a circuit and method that can further reduce the number of clock cycles (or, at least, the average number of clock cycles) of a processor required to perform a multiply instruction.
SUMMARY
In accordance with the invention, multiplication circuitry is provided to perform a multiply operation to multiply a multiplicand operand and a multiplier operand to form a total product of the multiplication operation, where the multiplier operand includes a plurality of multiplier operand portions. The multiplication circuitry includes multiplier circuitry configured to multiply each of the multiplier operand portions and the multiplicand operand, in a sequence, to form a sequence of partial products corresponding to the sequence of multiplier operand portions. The multiplier circuitry further includes combining circuitry configured, for each multiplier operand portion, to combine the partial product corresponding to that multiplier operand portion with a previous partial result, to generate a new partial result corresponding to that multiplier operand portion.
Detection circuitry is configured to determine, for each multiplier operand portion and based on that multiplier operand portion, or on both that and the previous multiplier operand portions if the new partial result corresponding to that multiplier operand portion would not change the previous partial result corresponding to a previous multiplier operand portion. For example, the detection circuitry may be specifically configured to determine whether the multiplier operand portion is all zeros or all ones. Control circuitry is configured to control operations of the combining circuitry responsive at least to the determination of the detection circuitry for that multiplier operand portion.
REFERENCES:
patent: 4276607 (1981-06-01), Wong
patent: 4868777 (1989-09-01), Nishiyama
patent: 5126963 (1992-06-01), Fukasawa
patent: 5260898 (1993-11-01), Richardson
patent: 5262973 (1993-11-01), Richardson
patent: 5339266 (1994-08-01), Hinds et al.
patent: 5557563 (1996-09-01), Larri
patent: 5586069 (1996-12-01), Dockser
patent: 5642306 (1997-06-01), Mennemeier
patent: 5748516 (1998-05-01), Goddard et al.
Chevillat et al, “Pipelined Hardward Multiplier with Extended Precision”, IBM Tech. Discl. Bull. vol. 23 No. 9 Feb. 1981, pp. 4322-4323.*
Avigdor Yoram
Levy Limor
Limbach & Limbach LLP
Mai Tan V.
National Semiconductor Corp.
LandOfFree
Multiply circuit and method that detects portions of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiply circuit and method that detects portions of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiply circuit and method that detects portions of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527215