Efficient implementation of multiprecision arithmetic

Details Efficient implementation of multiprecision arithmetic Efficient implementation of multiprecision arithmetic

1999-10-01

2003-09-23

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06625634

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to microprocessors, and more particularly, to an efficient implementation of multiprecision arithmetic.
BACKGROUND
Reduced Instruction Set Computing (RISC) microprocessors are well-known. RISC microprocessors are characterized by a smaller number of instructions, which are relatively simple to decode, and by requiring that all arithmetic/logic operations be performed register-to-register. RISC instructions are generally of only one length (e.g., 32-bit instructions). RISC instruction execution is of the direct hard-wired type, as opposed to microcoding. There is a fixed instruction cycle time, and the instructions are defined to be relatively simple so that each instruction generally executes in one relatively short cycle.
A RISC microprocessor typically includes an instruction for performing multiprecision arithmetic. However, a typical multiprecision add instruction or multiprecision subtract instruction is implemented using a condition code register.
FIG. 1
illustrates an implementation of a multiprecision add operation in a typical microprocessor.
FIG. 1
shows an n-bit adder
100
that can perform an addition operation and a subtraction operation. The add/sub control wire is set to zero for addition, which allows for the Y vector to be applied unchanged to one of the adder inputs along with a carry-in signal, C
0
. When the add/sub control wire is set to one, indicating subtraction, the Y vector is 1's complemented (that is bit complemented), and C
0
is set to 1 to complete the 2's complementation of Y. When adding unsigned numbers, the carry-out C
n
serves as the overflow indicator.
FIG. 1
also shows a condition code register
102
that includes a carry bit
104
which functions as a condition code flag. The condition code flag provides the carry-out signal C
n
of the n-bit adder
100
. The condition code flag is set to 1 if a carry-out results from an add operation, otherwise the condition code flag is set to 0. Additionally, the condition code flag is set to 1 if no carry-out results from a subtract operation, otherwise the condition code flag is set to 0.
An important aspect of condition code flags generally is the role of the C (Carry) flag in performing multiprecision (multiple-precision) arithmetic. For example, consider adding two operands, X and Y, each occupying several words in memory. The addition can be performed by a program loop that adds individual words in successive iterations. The C flag must be preserved from one iteration to the next in order to propagate the carries through the complete addition operation.
However, it is desirable to eliminate condition codes in the architecture of a microprocessor.
SUMMARY
An efficient implementation of multiprecision (multiple precision) arithmetic is provided. For example, an implementation of multiprecision arithmetic is provided that eliminates condition codes, such as condition codes for a carry bit and a borrow bit, and eliminates an add-with-carry instruction for multiprecision addition and a subtract-with-borrow instruction for multiprecision subtraction. In one embodiment, the present invention provides a cost-effective and high performance implementation of multiprecision arithmetic execution on a microprocessor.
In one embodiment, a method for multiprecision arithmetic, includes executing an add instruction, the add instruction adding a first operand and a second operand, and executing a generate carry instruction, the generate carry instruction generating the carry for addition of the first operand and the second operand.
In one embodiment, a method for multiprecision arithmetic, includes executing a subtract instruction, the subtract instruction subtracting a first operand and a second operand, and executing a generate borrow instruction, the generate borrow instruction generating the borrow for subtraction of the first operand and the second operand.


REFERENCES:
patent: 4893267 (1990-01-01), Alsup et al.
patent: 5574939 (1996-11-01), Keckler et al.
patent: 5657291 (1997-08-01), Podlesny et al.
patent: 5721868 (1998-02-01), Yung et al.
patent: 5742782 (1998-04-01), Ito et al.
patent: 5761475 (1998-06-01), Yung et al.
patent: 5764943 (1998-06-01), Wechsler
patent: 5778248 (1998-07-01), Leung
patent: 6263424 (2001-07-01), Tran et al.
patent: 0395348 (1990-10-01), None
patent: 0672681 (1994-12-01), None
Piepho, R.S., et al; “A Comparison of RISC Architectures”IEEE Micro, IEEE Inc., New York, U.S. vol. 9, No. 4, Aug. 1, 1989, pp. 51-62.
“Multiple Queued Condition Codes”,IBM Technical Disclosure Bulletin, IBM Corp., New York, U.S., vol. 31, No. 2, Jul. 1998, pp. 294-296.
M. Fillo et al.: “The M-Machine Multicomputer,” Proceedings of the Annual International Symposium on Microarchitecture, U.S., Los Alamitos, IEEE Comp. Soc. Press, vol. SYMP. 28, 1995, pp. 146-156, XP000585356 ISBN: 0-8186-7349-4.
M. Berekovic et al.: “Hardware Realization of a Java Virtual Machine For High Performance Multimedia Applications;” 1997 IEEE Workshop on Signal Processing Systems. SIPS 97 Design and Implementation Formerly VLSI Signal Processing, pp. 479-488, XP002139288, 1997, New York, NY, USA, IEEE.
S.W. Keckler et al.: “Processor Coupling: Integrating Compile Time and Runtime Scheduling for Parallelism;” Proceedings of the Annual International Symposium on Computer Architecture, U.S., New York, IEEE, vol. SYMP. 19, 1992, pp. 202-213, XP000325804 ISBN: 0-89794-510-6.

Affiliated with

Also associated with

Rating

Efficient implementation of multiprecision arithmetic does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient implementation of multiprecision arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient implementation of multiprecision arithmetic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3043611