Small multiplier after initial approximation for operations with increasing precision

Patent metadata

Field	Value
Publication number	US-11853718-B2
Application number	US-202318097316-A
Country	US
Kind code	B2
Filing date	Jan 16, 2023
Priority date	Oct 17, 2014
Publication date	Dec 26, 2023
Grant date	Dec 26, 2023

Abstract

In an aspect, a processor includes circuitry for iterative refinement approaches, e.g., Newton-Raphson, to evaluating functions, such as square root, reciprocal, and for division. The circuitry includes circuitry for producing an initial approximation; which can include a LookUp Table (LUT). LUT may produce an output that (with implementation-dependent processing) forms an initial approximation of a value, with a number of bits of precision. A limited-precision multiplier multiplies that initial approximation with another value; an output of the limited precision multiplier goes to a full precision multiplier circuit that performs remaining multiplications required for iteration(s) in the particular refinement process being implemented. For example, in division, the output being calculated is for a reciprocal of the divisor. The full-precision multiplier circuit requires a first number of clock cycles to complete, and both the small multiplier and the initial approximation circuitry complete within the first number of clock cycles.

First claim

What is claimed is:

1. A method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration, comprising:
producing an initial approximation of the output value based on the input value;
performing a first multiplication of a first iteration by a limited-precision multiplier;
performing, in a full-precision multiplier, remaining multiplications for each iteration; and
outputting said output value after performing said remaining multiplications.

2. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , wherein the full-precision multiplier requires three clock cycles, the producing of the initial approximation of the output value requires one clock cycle and the performing of the first multiplication of the first iteration requires two clock cycles.

3. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , wherein the output value is an approximation of a reciprocal of the input value and further comprising multiplying the output value with a dividend.

4. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , wherein the output value is an approximation of a reciprocal of the square root of the input value and further comprising multiplying the output value with the input value.

5. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , further comprising performing two iterations in producing a double-precision evaluation of the output value.

6. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , further comprising using the limited-precision multiplier once and the full-precision multiplier twice in producing a single-precision evaluation of the output value.

7. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , in which the initial approximation has a first number of bits of precision, the first number of bits of precision being fewer than a required number of bits of precision in the output value.

8. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , in which the limited-precision multiplier comprises circuitry capable of maintaining, in an output, at least twice the number of bits of precision of the initial approximation and fewer bits of precision than required to produce a single-precision floating point mantissa.

9. The method of evaluating an output value of a function at an input value using an iterative refinement procedure requiring at least two multiplications for each iteration of claim 1 , in which producing the initial approximation and performing the first multiplication collectively require a first number of clock cycles, and each multiplication in the full-precision multiplier requires at least the first number of clock cycles.

Assignees

• Imagination Tech Ltd

Inventors

• Rarick Leonard

Classifications

• G06F7/552 Primary

  Powers or roots {, e.g. Pythagorean sums} · CPC title

• G06F7/523

  Multiplying only · CPC title

• G06F7/537 Primary

  Reduction of the number of iteration steps or stages, e.g. using the Sweeny-Robertson-Tocher [SRT] algorithm · CPC title

• G06F7/5525

  Roots or inverse roots of single operands · CPC title

• G06F2207/5351

  Multiplicative non-restoring division, e.g. SRT, using multiplication in quotient selection · CPC title