Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-01-29
2002-02-26
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S504000
Reexamination Certificate
active
06351760
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computational and calculation functional units of computers, controllers and processors. More specifically, the present invention relates to functional units that perform division operations.
2. Description of the Related Art
Computer systems have evolved into versatile systems with a vast range of utility including demanding applications such as multimedia, network communications of a large data bandwidth, signal processing, and the like. Accordingly, general-purpose computers are called upon to rapidly handle large volumes of data. Much of the data handling, particularly for video playback, voice recognition, speech process, three-dimensional graphics, and the like, involves computations that must be executed quickly and with a short latency.
One technique for executing computations rapidly while handling the large data volumes is to include multiple computation paths in a processor. Each of the data paths includes hardware for performing computations so that multiple computations may be performed in parallel. However, including multiple computation units greatly increases the size of the integrated circuits implementing the processor. What are needed in a computation functional unit are computation techniques and computation integrated circuits that operate with high speed while consuming only a small amount of integrated circuit area.
Execution time in processors and computers is naturally enhanced through high speed data computations, therefore the computer industry constantly strives to improve the speed efficiency of mathematical function processing execution units. Computational operations are typically performed through iterative processing techniques, look-up of information in large-capacity tables, or a combination of table accesses and iterative processing. In conventional systems, a mathematical function of one or more variables is executed by using a part of a value relating to a particular variable as an address to retrieve either an initial value of a function or a numeric value used in the computation from a large-capacity table information storage unit. A high-speed computation is executed by operations using the retrieved value. Table look-up techniques advantageously increase the execution speed of computational functional units. However, the increase in speed gained through table accessing is achieved at the expense of a large consumption of integrated circuit area and power.
A division instruction is highly burdensome and difficult to implement in silicon, typically utilizing many clock cycles and consuming a large integrated circuit area.
What is needed is a method for implementing division in a computing circuit that is simple, fast, and reduces the amount of computation circuitry.
SUMMARY OF THE INVENTION
A computation unit computes a division operation Y/X by determining the value of a divisor reciprocal 1/X and multiplying the reciprocal by a numerator Y. The reciprocal 1/X value is determined using a quadratic approximation having a form:
Ax
2
+Bx+C,
where coefficients A, B, and C are constants that are stored in a storage or memory such as a read-only memory (ROM). The bit length of the coefficients determines the error in a final result. Storage size is reduced through use of “least mean square error” techniques in the determination of the coefficients that are stored in the coefficient storage. During the generation of partial products x
2
, Ax
2
, and Bx, the process of rounding is eliminated, thereby reducing the computational logic to implement the division functionality.
A method of computing a floating point division operation uses a piece-wise quadratic approximation to determine a value 1/X where X is a floating point number having a numerical format including a sign bit, an exponent field, and a mantissa field. A floating point division Y/X is executed by computing the value 1/X and multiplying the result by a value Y. The value 1/X is computed in a computing device using a piece-wise quadratic approximation in the form:
1/X=Ax
2
+Bx+C.
The value x is defined as a plurality of lower order bits of the mantissa. Coefficients A, B, and C are derived for the division operation to reduce the least mean square error using a least squares approximation of a plurality of equally-spaced points within an interval. In one embodiment, an interval includes 256 equally-spaced points. The coefficients are stored in a storage and accessed during execution of the division computation instruction.
In some embodiments, a lookup table in storage is indexed using the leading or higher order bits of the mantissa. Since the most significant bit of the mantissa is always 1, some embodiments use a plurality of higher order bits but not including the most significant bit to index into the lookup table storage.
The method produces a “pre-rounded” Y/X result that is rounded to the nearest value. The pre-rounded result is truncated at a round bit position and incremented at the round bit position to generate an incremented quotient that is within one LSB of a correct solution. The incremented quotient multiplied by the divisor is compared with the dividend by subtraction. If the remainder is negative, then the pre-rounded result is more than half an LSB below the correct value and is incremented. If the remainder is positive, then the prerounded result is less than half an LSB below the correct value and is not incremented. If the remainder is zero, the result is selected based on the LSB of the pre-rounded result.
REFERENCES:
patent: 4336599 (1982-06-01), Wong
patent: 4477879 (1984-10-01), Wong
patent: 4682302 (1987-07-01), Williams
patent: 4734876 (1988-03-01), Williams
patent: 4737925 (1988-04-01), Williams
patent: 4748518 (1988-05-01), Suzuki
patent: 4757467 (1988-07-01), Dieterich et al.
patent: 4823301 (1989-04-01), Knierim
patent: 4852038 (1989-07-01), Wagner et al.
patent: 4857882 (1989-08-01), Wagner et al.
patent: 4949296 (1990-08-01), Malinowski
patent: 4991132 (1991-02-01), Kadota
patent: 5097434 (1992-03-01), Stouraitis
patent: 5184317 (1993-02-01), Pickett
patent: 5245564 (1993-09-01), Quek et al.
patent: 5268857 (1993-12-01), Chen et al.
patent: 5280439 (1994-01-01), Quek et al.
patent: 5305248 (1994-04-01), Ammann
patent: 5337266 (1994-08-01), Arnold
patent: 5359551 (1994-10-01), Pickett
patent: 5537345 (1996-07-01), Nakano
patent: 5563818 (1996-10-01), Agarwal et al.
patent: 5600581 (1997-02-01), Dworkin et al.
patent: 5633818 (1997-05-01), Taniguchi
patent: 5675822 (1997-10-01), Kelley
patent: 5729481 (1998-03-01), Schwarz
patent: 5737255 (1998-04-01), Schwarz
patent: 5737257 (1998-04-01), Chen et al.
patent: 5751619 (1998-05-01), Agarwal et al.
patent: 5764555 (1998-06-01), McPherson et al.
patent: 5764990 (1998-06-01), Sullivan
patent: 5768170 (1998-06-01), Smith
patent: 6115733 (2000-09-01), Oberman et al.
Lecture Notes in Control and Information Sciences, 38, System Modeling and Optimization, Springer-Verlag, NY, 1982, pp. 276-283, Tsai et al: ‘A Robustized Maximum Entropy Approach to System Identification’ XP000920525.
Shankar Ravi
Sudharsanan Subramania I.
Koestner Ken J.
Malzahn David H.
Skjerven Morrill & MacPherson LLP
Sun Microsystems Inc.
LandOfFree
Division unit in a processor using a piece-wise quadratic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Division unit in a processor using a piece-wise quadratic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Division unit in a processor using a piece-wise quadratic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2934527