Iterative division with reduced latency

Patent metadata

Field	Value
Publication number	US-10289386-B2
Application number	US-201615122724-A
Country	US
Kind code	B2
Filing date	Apr 21, 2016
Priority date	Apr 21, 2016
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

A multiplier unit may be configured to generate a final approximation of an iterative arithmetic operation performed on two operands. Circuitry coupled to the multiplier unit may perform a shift operation and a mask operation on the final approximation to generate shifted and un-shifted approximations, respectively. The circuitry may generate a first remainder using the un-shifted approximation and a sign value of a second remainder using the first remainder. Using the sign value of the second remainder, the circuitry may perform a rounding operation on the shifted approximation to generate a final answer.

First claim

What is claimed is:

1. An apparatus, comprising:
an arithmetic logic unit that includes:
a multiplier stage configured to generate, upon reaching a specified level of precision, a final approximation of an iterative arithmetic operation performed on at least two operands; and
rounding circuitry coupled to the multiplier stage, wherein the rounding circuitry is configured to:
receive the final approximation;
perform, using a shift register, a shift operation on the final approximation to generate a shifted approximation;
in parallel with performing the shift operation on the final approximation:
perform a mask operation on the final approximation to generate an un-shifted approximation;
generate a first remainder value using the un-shifted approximation and the two operands;
generate a sign value of a second remainder value using the first remainder value; and

perform a rounding operation on the shifted approximation using the sign value to generate a final answer of the iterative arithmetic operation.

2. The apparatus of claim 1 , wherein to generate the sign value of the second remainder value, the rounding circuitry is further configured to invert a sign of the first remainder value.

3. The apparatus of claim 1 , wherein to perform the mask operation on the final approximation, the rounding circuitry is further configured to set a trailing number of bits in the final approximation to zero, wherein the trailing number of bits is based on a precision and a shift value, wherein the shift value is a positive integer less than a number of data bits included in the final approximation, and wherein the precision is a positive integer less than the number of data bits included in the final approximation.

4. The apparatus of claim 3 , wherein to generate the first remainder value using the un-shifted approximation and the two operands, the rounding circuity is further configured to determine a difference between a product of the un-shifted approximation and a first operand of the two operands and a second product.

5. The apparatus of claim 3 , wherein the rounding circuitry is further configured to perform the rounding operation using the precision.

6. The apparatus of claim 1 , wherein the rounding circuitry is further configured to perform a different mask operation on results of the shift operation.

7. An apparatus, comprising:
an arithmetic logic unit configured to perform an arithmetic operation on at least two operands, wherein the arithmetic logic unit includes:
a multiplier circuit configured to used the at least two operands to iteratively generate a final approximation for the arithmetic operation in response to reaching a specified level of precision; and
a rounding circuit configured to round the final approximation to generate a final result for the arithmetic operation, wherein the rounding circuit is configured to generate the final result by operating, in parallel, on both shifted and unshifted versions of the final approximation, thereby reducing latency of the arithmetic operation.

8. The apparatus of claim 7 , wherein to generate the final result, the rounding circuit is further configured to perform a mask operation on the final approximation to generate the unshifted version of the final approximation.

9. The apparatus of claim 8 , wherein to perform the mask operation on the final approximation, the rounding circuit is further configured to set a trailing number of bits in the final approximation to zero, wherein the trailing number of bits is based on a precision and a shift value, wherein the shift value is a positive integer less than a number of data bits included in the final approximation, and wherein the precision is a positive integer less than the number of data bits included in the final approximation.

10. The apparatus of claim 9 , wherein the rounding circuit is further configured to determine a difference between a product of the unshifted version of the final approximation and a first operand of the two operands and a second product.

11. The apparatus of claim 9 , wherein the rounding circuit is further configured to round the final approximation using the precision.

Assignees

• Oracle Int Corp

Inventors

• Ebergen Josephus
• Olson Christopher
• Nadehzin Dmitry
• Rager David
• Lee Austin

Classifications

• G06F17/17

  Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method ({G06F17/18 takes precedence } ; interpolation for numerical control G05B19/18) · CPC title

• G06F5/01

  for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)} · CPC title

• G06F7/523 Primary

  Multiplying only · CPC title