Circuitry and method for performing division

Patent metadata

Field	Value
Publication number	US-10353671-B2
Application number	US-201614994601-A
Country	US
Kind code	B2
Filing date	Jan 13, 2016
Priority date	Jan 13, 2016
Publication date	Jul 16, 2019
Grant date	Jul 16, 2019

Abstract

A data processing apparatus comprises signal receiving circuitry to receive a signal corresponding to a divide instruction that identifies a dividend x and a divisor d. Processing circuitry performs, in response to said divide instruction, a radix-N division algorithm to generate a result value q=x/d, where N is an integer power of 2 and greater than 1. Said division algorithm comprises a plurality of iterations, each of said plurality of iterations being performed by quotient digit calculation circuitry to determine a quotient value of that iteration q[i+1] based on a remainder value of a previous iteration rem[i]; and remainder calculation circuitry to determine a remainder value of that iteration rem[i+1] based on said quotient value of that iteration q[i+1] and said remainder value of said previous iteration rem[i]. Result calculation circuitry derives said result value q based on each quotient value selected by said digit selection circuitry for each of said plurality of iterations. For at least some of said plurality of iterations, said quotient digit calculation circuitry speculatively determines a set of candidate values before a quotient value of said previous iteration is known and, in response to said quotient value of said previous iteration becoming known, determines said quotient value of that iteration q[i+1] based on one of said candidate values.

First claim

I claim:

1. A data processing apparatus comprising:
receiver circuitry to receive a signal corresponding to a divide instruction that identifies a dividend x and a divisor d;
processing circuitry to perform, in response to said divide instruction, a radix-N division algorithm for a plurality of radix-N iterations to generate a result value q=x/d, where N is an integer power of 2, said integer power being greater than 1, each of said plurality of radix-N iterations being performed by:
quotient digit calculation circuitry to determine a quotient value of that iteration q[i+1]based on a remainder value of a previous iteration rem[i], wherein the quotient value of that iteration q[i+1] comprises log 2 (N) bits and is within the range [−N/2,+N/2]; and
remainder calculation circuitry to determine a remainder value of that iteration rem[i+1]based on said quotient value of that iteration q[i+1] and said remainder value of said previous iteration rem[i]; and
result calculation circuitry to derive said result value q based on each quotient value determined by said quotient digit selection circuitry for each of said plurality of radix-N iterations, wherein
for at least some of said plurality of radix-N iterations, said quotient digit calculation circuitry is adapted to speculatively determine a set of candidate values before a quotient value of said previous iteration is known and, in response to said quotient value of said previous iteration becoming known, determines said quotient value of that iteration q[i+1] based on one of said candidate values.

2. A data processing apparatus according to claim 1 , wherein
for at least some of said plurality of radix-N iterations, said remainder calculation circuitry is adapted to speculatively determine a set of candidate remainder values before said quotient value of said previous iteration is known and, in response to said quotient value of said previous iteration becoming known, select one of said candidate remainder values as said remainder value of that iteration rem[i+1] in dependence on said quotient value of said previous iteration.

3. A data processing apparatus according to claim 2 , wherein
said set of candidate values comprises one candidate value corresponding to each of said candidate remainder values.

4. A data processing apparatus according to claim 2 , wherein
each of said candidate values is speculatively determined based on an approximation of a corresponding one of said candidate remainder values.

5. A data processing apparatus according to claim 2 , wherein
speculatively determination of each of said candidate values is based on most significant bits of a corresponding one of said candidate remainder values.

6. A data processing apparatus according to claim 2 , wherein
speculatively determination of each of said candidate values is based on M most significant bits of a corresponding one of said candidate remainder values, where M is based on N, and a digit set of said quotient value.

7. A data processing apparatus according to claim 1 , wherein said quotient digit calculation circuitry is adapted to determine said quotient value of that iteration q[i+1] as a largest single radix-N digit that, when multiplied by said divisor d, is less than said remainder value of said previous iteration rem[i].

8. A data processing apparatus according to claim 1 , wherein
said at least some of said plurality of radix-N iterations comprises second and subsequent iterations.

9. A data processing apparatus according to claim 1 , wherein
said divisor and said dividend share a bit position of a most significant bit.

10. A data processing apparatus according to claim 9 , further comprising
input scaling circuitry to perform an input scaling operation on at least one of said divisor and said dividend such that said divisor and said dividend share a bit position of a most significant bit; and
output scaling circuitry to cause said processing circuitry to derive said result value q by concatenating each quotient value determined by said digit selection circuitry for each of said plurality of radix-N iterations and performing an output scaling operation to produce said result value q, wherein said output scaling operation compensates for said input scaling operation.

11. A data processing apparatus according to claim 1 , wherein
said divisor is greater than 1−(1/64) and less than 1+(1/8).

12. A data processing apparatus according to claim 1 , wherein
said dividend x is a floating point number comprising a dividend significand and a dividend exponent, and said divisor d is a floating point number comprising a divisor significand and a divisor exponent; and
said data processing apparatus further comprises:
exponent calculation circuitry to subtract said dividend exponent from said divisor exponent to produce an output exponent;
unpack circuitry to provide said divisor significand and said dividend significand to said processing circuitry and to provide said dividend exponent and said divisor exponent to said exponent calculation circuitry; and
normalising and rounding circuitry to perform a normalising operation and a rounding operation based on said output exponent and each quotient value determined by said digit selection circuitry for each of said plurality of radix-N iterations to produce result value q.

13. A data processing apparatus according to claim 1 , wherein
at least some of said plurality of radix-N iterations are performed in a single clock cycle.

14. A data processing apparatus according to claim 13 , wherein
said at least some of said plurality of radix-N iterations comprises three iterations.

15. A data processing apparatus according to claim 1 , said quotient digit calculation circuitry further comprising:
second quotient circuitry to perform a second iteration in said plurality of radix-N iterations, wherein said second quotient circuitry determines said quotient value of that iteration q[i+1] as a largest single radix-N digit that, when multiplied by a selected one of said candidate values, is less than said remainder value of said previous iteration rem[i]; and
third quotient circuitry to perform a third iteration in said plurality of radix-N iterations, wherein said third quotient circuitry determines said quotient value of that iteration q[i+1] as one of said candidate values.

16. A data processing apparatus according to claim 1 , wherein N is 4.

17. A data processing apparatus according to claim 1 , wherein
said remainder calculation circuitry is adapted to determine a remainder value of that iteration rem[i+1] by multiplying said remainder value of said previous iteration rem[i] by N and subtracting said quotient value of that iteration q[i+1] multiplied by said divisor d.

18. A data processing apparatus according to claim 1 , wherein
at least one of said remainder value and said quotient digit are provided in redundant representation.

19. A method comprising steps:
receiving a signal corresponding to a divide instruction that identifies a dividend x and a divisor d;
performing, in response to said divide instruction, a radix-N division algorithm for a plurality of radix-N iterations to generate a result value q=x/d, where N is an integer power of 2, said integer power being greater than 1, each of said plurality of radix-N iterations being performed by:
determining, using quotient digit calculation circuitry, a quotient value of that iteration q[i+1] based on a remainder value of a previous iteration rem[i], wherein the quotient value of that it

Assignees

• Advanced Risc Mach Ltd

Inventors

• Bruguera Javier Diaz

Classifications

• G06F7/4873 Primary

  Dividing · CPC title

• G06F2207/5351

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

• G06F7/487 Primary

  Multiplying; Dividing {(G06F7/4833, G06F7/4836 take precedence)} · CPC title

• G06F7/537

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