Iterative estimation hardware

Patent metadata

Field	Value
Publication number	US-11422802-B2
Application number	US-201916725378-A
Country	US
Kind code	B2
Filing date	Dec 23, 2019
Priority date	Dec 21, 2018
Publication date	Aug 23, 2022
Grant date	Aug 23, 2022

Abstract

A function estimation hardware logic unit may be implemented as part of an execution pipeline in a processor. The function estimation hardware logic unit is arranged to calculate, in hardware logic, an improved estimate of a function of an input value, d, where the function is given by1⁢/⁢di.The hardware logic comprises a plurality of multipliers and adders arranged to implement a mth-order polynomial with coefficients that are rational numbers, where m is not equal to two and in various examples m is not equal to a power of two. In various examples i=1, i=2 or i=3. In various examples m=3.

First claim

What is claimed is:

1. A fixed function estimation hardware logic unit for use in an arithmetic logic unit of a processor, the fixed function estimation hardware logic unit arranged to calculate, in fixed function hardware logic, an improved estimate, x n+1 , for a function of an input value, d, wherein the function is

1
/

d
i

,

and the fixed function estimation hardware logic unit comprising:
a first input arranged to receive the input value, d;
a second input arranged to receive an estimate, x n , for the function of the input value; and
an output arranged to output the improved estimate, x n+1 , for the function of the input value; and
a combination of multiplier and addition hardware blocks configured in hardware circuitry to implement an m th -order polynomial to determine the improved estimate, x n+1 , with m th order convergence, wherein the m th -order polynomial can be expressed as:
x n+1 =x n /8(15− dx n 2 (10−3 dx n 2 ))

wherein m=3 and i=2 and wherein the combination of multiplier and addition hardware blocks configured in hardware circuitry to implement the m th -order polynomial comprises:
a first hardware logic stage comprising a right shifter, the right shifter comprising an input arranged to receive an estimate x n for the function of the input value and an output;
a second hardware logic stage comprising a square function logic block, the square function logic block comprising an input arranged to receive an estimate x n for the function of the input value and an output;
a third hardware logic stage comprising a multiplier, the multiplier comprising an input arranged to receive the input value, d, an input connected to the output of the second hardware logic stage and an output;
a fourth hardware logic stage comprising a multiplier, the multiplier comprising an input connected to the output of the third hardware logic stage and an output;
a fifth hardware logic stage comprising a square function logic block, the square function logic block comprising an input connected to the output of the third hardware logic stage and an output;
a sixth hardware logic stage comprising a multiplier, the multiplier comprising an input connected to the output of the fifth hardware logic stage and an output; and
a seventh hardware logic stage comprising two subtraction logic blocks and a multiplier, the first of the two subtraction logic blocks comprising an input connected to the output of the fourth hardware logic stage and an output, the second of the two subtraction logic blocks comprising an input connected to the output of the first of the two subtraction logic blocks, an input connected to the output of the sixth hardware logic stage and an output and the multiplier comprising an input connected to the output of the first hardware logic stage, an input connected to the output of the second of the two subtraction logic blocks and an output.

2. An arithmetic logic unit comprising the fixed function estimation hardware logic unit according to claim 1 .

3. An arithmetic logic unit comprising plurality of instances of the fixed function estimation hardware logic unit according to claim 1 arranged in a sequence, wherein an output from one fixed function estimation hardware logic unit is taken as an input to a next fixed function estimation hardware logic unit in the sequence.

4. A computer implemented method for calculating, in fixed function hardware logic, an improved estimate, x n+1 , for a function of an input value, d, wherein the function is

1
/

d
i

,

and the method comprising:
receiving the input value, d; receiving an estimate, x n , for the function of the input value; and calculating an improved estimate, x n+1 , for the function of the input value by inputting the input value and the received estimate to a combination of multiplier and addition hardware blocks configured in hardware circuitry to implement an m th -order polynomial to determine the improved estimate, x n+1 , with m th order convergence, wherein the m th -order polynomial can be expressed as:
x n+1 =x n /8(15− dx n 2 (10−3 dx n 2 ))

wherein m=3 and i=2 and wherein the combination of multiplier and addition hardware blocks configured in hardware circuitry to implement the m th -order polynomial comprises:
a first hardware logic stage comprising a right shifter, the right shifter comprising an input arranged to receive an estimate x n for the function of the input value and an output;
a second hardware logic stage comprising a square function logic block, the square function logic block comprising an input arranged to receive an estimate x n for the function of the input value and an output;
a third hardware logic stage comprising a multiplier, the multiplier comprising an input arranged to receive the input value, d, an input connected to the output of the second hardware logic stage and an output;
a fourth hardware logic stage comprising a multiplier, the multiplier comprising an input connected to the output of the third hardware logic stage and an output;
a fifth hardware logic stage comprising a subtraction logic block and a multiplier, the subtraction logic block comprising an input connected to the output of the fourth hardware logic stage and an output and the multiplier comprising an input connected to the output of the subtraction logic block, an input connected to the output of the third hardware logic stage and an output; and
a sixth hardware logic stage comprising a subtraction logic block and a multiplier, the subtraction logic block comprising an input connected to the output of the fifth hardware logic stage and an output and the multiplier comprising an input connected to the output of the subtraction logic block, an input connected to the output of the first hardware logic stage and an output.

5. A non-transitory computer readable storage medium having stored thereon an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a fixed function estimation hardware logic for use in an arithmetic logic unit of a processor, the fixed function estimation hardware logic arranged to calculate, in hardware logic, an improved estimate, x n+1 , for a function of an input value, d, wherein the function is

1
/

d
i

,

and the fixed function estimation hardware logic comprising:
a first input arranged to receive the input value, d; a second input arranged to receive an estimate, x n , for the function of the input value; and an output arranged to output the improved estimate, x n+1 , for the function of the input value; and a combination of multiplier and addition hardware blocks configured in hardware circuitry to implement an m th -order polynomial to determine the improved estimate, x n+1 , with m th order convergence, wherein the m th -order polynomial can be expressed as:
x n+1 =x n /8(15− dx n 2 (10−3 dx n 2 ))

wherein m=3 and i=2 and wherein the combination of

Assignees

• Imagination Tech Ltd

Inventors

• Rose Thomas
• Freiburghaus Max
• Mckemey Robert

Classifications

• G06F7/5525 Primary

  Roots or inverse roots of single operands · CPC title

• G06F7/575 Primary

  Basic arithmetic logic units, i.e. devices selectable to perform either addition, subtraction or one of several logical operations, using, at least partially, the same circuitry · CPC title

• G06F7/57

  Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations {(G06F7/49, G06F7/491 take precedence)} · CPC title

• G06F7/552

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

• G06F2207/5521

  Inverse root of a number or a function, e.g. the reciprocal of a Pythagorean sum · CPC title