Apparatus and method for performing operations implemented by iterative execution of a recurrence equation
AssigneeArm Limited
InventorsChristopher Neal Hinds, Neil Burgess
Life of this patent
Estimating the term…
Loading patent…
AssigneeArm Limited
InventorsChristopher Neal Hinds, Neil Burgess
Estimating the term…
The present invention provides an apparatus and method for performing an operation on an operand or operands in order to generate a result, in which the operation is implemented by iterative execution of a recurrence equation. In each iteration, execution of the recurrence equation causes a predetermined number of bits of the result and a residual to be generated, the residual generated in a previous iteration being used as an input for the current iteration, and in the first iteration the residual comprising the operand. The apparatus comprises result digit logic operable for a current iteration to determine, having regard to a most significant n bits of the input residual, a next result digit, and residual generation logic operable for a current iteration to generate, having regard to the input residual and the next result digit, a next residual, the most significant n bits of the next residual being generated in non-redundant form and the remaining bits of the next residual being generated in redundant form. Result update logic is also provided which is operable for a current iteration to modify the result, having regard to the next result digit, to produce an updated result. Control logic is then provided to cause the iterations to continue until a predetermined condition is met, whereafter the result is indicated by the updated result and any residual existing after the final iteration. In preferred embodiments, the apparatus is used to perform division operations and/or square root operations. The apparatus enables a significant reduction in the critical path of the primary iterative cycle used to execute the recurrence equation.
A method of operating a data processing apparatus to perform a division operation to divide a dividend by a divisor, the division operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of a quotient, and a partial remainder, to be generated, the partial remainder generated in a previous iteration being used as an input for the current iteration, and in the first iteration the dividend forming the input partial remainder, the method comprising the steps of:
A data processing apparatus operable to perform a division operation to divide a dividend by a divisor, the division operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of a quotient, and a partial remainder, to be generated, the partial remainder generated in a previous iteration being used as an input for the current iteration, and in the first iteration the dividend forming the input partial remainder, the data processing apparatus comprising:
A method of operating a data processing apparatus to perform a square root operation on a radicand, the square root operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of a root, and a residual, to be generated, the residual and the root generated in a previous iteration being used as an input for the current iteration, and in the first iteration the radicand forming the input residual, the method comprising the steps of:
A data processing apparatus operable to perform a square root operation on a radicand, the square root operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of a root, and a residual, to be generated, the residual and the root generated in a previous iteration being used as an input for the current iteration, and in the first iteration the radicand forming the input residual, the data processing apparatus comprising:
A method of operating a data processing apparatus to perform an operation on an operand in order to generate a result, the operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of the result and a residual to be generated, the residual generated in a previous iteration being used as an input for the current iteration, and in the first iteration the residual comprising the operand, the method comprising the steps of:
A data processing apparatus operable to perform an operation on an operand in order to generate a result, the operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of the result and a residual to be generated, the residual generated in a previous iteration being used as an input for the current iteration, and in the first iteration the residual comprising the operand, the data processing apparatus comprising:
Dependencies are inferred from the claim text.