Data processing apparatus having combined divide-square root circuitry

Patent metadata

Field	Value
Publication number	US-9785407-B2
Application number	US-201414549639-A
Country	US
Kind code	B2
Filing date	Nov 21, 2014
Priority date	Nov 21, 2014
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

A processing apparatus has combined divide-square root circuitry for performing a radix-N SRT divide algorithm and a radix-N SRT square root algorithm, where N is an integer power-of-2. The combined circuitry has shared remainder updating circuitry which performs remainder updates for a greater number of iterations per cycle for the SRT divide algorithm than for the SRT square root algorithm. This allows reduced circuit area while avoiding the SRT square root algorithm compromising the performance of the SRT divide algorithm.

First claim

We claim:

1. A data processing apparatus comprising:
combined divide-square root circuitry to perform, in response to a divide instruction identifying a first operand A and a divisor D, a radix-N SRT division algorithm to generate a result value Q=A/D, and to perform, in response to a square root instruction identifying a second operand B, a radix-N SRT square root algorithm to obtain a result value Q=√{square root over (B)}, where N is an integer power of 2;
wherein the SRT division algorithm and the SRT square root algorithm each comprise a plurality of iterations, each iteration for determining an updated remainder value R i based on a quotient value q i selected for that iteration in dependence on a previous remainder value R i−1 , the updated remainder value from one iteration becoming the previous remainder value for a following iteration, and the result value Q being derivable from the quotient values selected for the plurality of iterations; and
the combined divide-square root circuitry comprises shared remainder updating circuitry to generate the updated remainder value for a greater number of iterations per processing cycle for the SRT division algorithm than for the SRT square root algorithm;
wherein in the SRT square root algorithm, the i th iteration is for determining the updated remainder value R i based on the previous remainder value R i−1 , the quotient value q i and a partial result value Q i−1 corresponding to a combination of the quotient values selected in the preceding iterations;
the partial result value Q i−1 is represented in signed-digit format; and
the shared remainder updating circuitry comprises circuitry to perform a calculation for determining the updated remainder value R i with the partial result value Q i−1 remaining in the signed-digit format, when performing the SRT square root algorithm.

2. The data processing apparatus according to claim 1 , wherein the shared remainder updating circuitry is to generate the updated remainder value for twice as many iterations per processing cycle for the SRT division algorithm than for the SRT square root algorithm.

3. The data processing apparatus according to claim 1 , wherein the combined divide-square root circuitry comprises shared quotient selecting circuitry to select the quotient value based on the previous remainder value, for both the SRT divide algorithm and the SRT square root algorithm.

4. The data processing apparatus according to claim 1 , wherein in the SRT division algorithm, the i th iteration is for determining the updated remainder value R i equivalent to R i =N×(R i−1 −q i ×D) or R i =N×R i−1 −q i ×D.

5. The data processing apparatus according to claim 1 , wherein in the SRT square root algorithm, the i th iteration is for determining the updated remainder value R i equivalent to R i =N×(R i−1 −q i (2Q i−1 +q i /2 i )) or R i =N×R i−1 −q i (2Q i−1 +q i /2 i ).

6. The data processing apparatus according to claim 1 , wherein the partial result value Q i−1 is represented by a first value representing positively-weighted digits of the partial result value and a second value representing negatively-weighted digits of the partial result value; and
the shared remainder updating circuitry comprises a first adding stage to perform an addition or subtraction using the previous remainder value R i−1 and one of the first value and the second value, and a second adding stage to perform an addition or subtraction using a result of the first adding stage and the other of the first value and the second value, to generate the updated remainder value R i at the output of the second adding stage when performing the SRT square root algorithm.

7. The data processing apparatus according to claim 6 , wherein when performing the SRT divide algorithm, the first adding stage is to generate the updated remainder value R i for one iteration, and the second adding stage is to generate the updated remainder value R i+1 for a subsequent iteration.

8. The data processing apparatus according to claim 1 , wherein the shared remainder updating circuitry comprises at least one remainder updating stage;
each remainder updating stage comprising shared circuitry to output, in response to the previous remainder value R i−1 for one iteration:
(i) the updated remainder value R i+1 for a subsequent iteration when performing the SRT divide algorithm; and
(ii) the updated remainder value R i for said one iteration when performing the SRT square root algorithm.

9. The data processing apparatus according to claim 1 , wherein the shared remainder updating circuitry comprises at least one remainder updating stage, each remainder updating stage comprising a first adding stage and a second adding stage;
when performing the SRT divide algorithm, the first adding stage is to generate the updated remainder value R i for one iteration, and the second adding stage is to generate the updated remainder value R i+1 for a subsequent iteration; and
when performing the SRT square root algorithm, the first adding stage and the second adding stage are together to generate the updated remainder value R i for a single iteration.

10. The data processing apparatus according to claim 9 , wherein the first adding stage is to perform an addition or subtraction using the previous remainder value R i−1 and a second value; and
each remainder updating stage comprises second value selecting circuitry to select as the second value:
(i) a value dependent on the divisor D and the quotient value for said one iteration, when performing the SRT divide algorithm; and
(ii) a value dependent on the quotient values selected for preceding iterations and the quotient value for said single iteration, when performing the SRT square root algorithm.

11. The data processing apparatus according to claim 9 , wherein the second adding stage is to perform an addition or subtraction using a result of the first adding stage and a further value; and
each remainder updating stage comprises further value selecting circuitry to select as the further value:
(i) a value dependent on the divisor D and the quotient value for said subsequent iteration, when performing the SRT divide algorithm; and
(ii) a value dependent on the quotient values selected for preceding iterations and the quotient value for said single iteration, when performing the SRT square root algorithm.

12. The data processing apparatus according to claim 9 , wherein each remainder updating stage comprises shift circuitry to shift the output of the first adding stage and supply the shifted output to the second adding stage when performing the SRT divide algorithm, and to supply an unshifted output of the first adding stage to the second adding stage when performing the SRT square root algorithm.

13. The data processing apparatus according to claim 9 , wherein each remainder updating stage comprises shift circuitry to shift an input of the first adding stage or an output of the second adding stage when performing both the SRT divide algorithm and the SRT square root algorithm.

14. The data processing apparatus according to claim 9 , wherein the shared result generating circuitry comprises a plurality of said remainder updating stages.

15. The data processing apparatus according to claim 1 , comprising result generating circuitry to generate the result value Q based on the quotient values selected in said plurality of iterations.

16. The data processing apparatus according to claim 1 , wherein N=2.

17. A data processing apparatus comprising:
combined divide-square root means for performi

Assignees

• Advanced Risc Mach Ltd

Inventors

• Burgess Neil
• Lutz David Raymond

Classifications

• G06F9/3001

  Arithmetic instructions · CPC title

• G06F7/5525

  Roots or inverse roots of single operands · CPC title

• G06F7/535 Primary

  Dividing only · CPC title

• G06F2207/5528

  Non-restoring calculation, where each result digit is either negative, zero or positive, e.g. SRT · CPC title

• G06F2207/5351

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