System and method for executing fixed point divide operations using a floating point multiply-add pipeline

Abstract

A system and method for executing fixed point divide operations using a floating point multiply-add pipeline are provided. With the system and method, the floating point execution unit in a processor is modified to include elements that may be used to perform fixed point divide operations. These additional elements include a leading zero counter, a leading one counter, an estimate table unit, and a state machine. The fixed point divide operands are converted to a floating point format and an estimate of the reciprocal of the divisor is generated using estimate tables. These values are used in multiple passes through the floating point unit for calculating estimates of the quotient and corresponding error values. The estimates of the quotient are based on previous estimates of the quotient in a prior pass through the floating point unit and a corresponding error value. The final quotient estimate is truncated.

1 . A method, in a data processing system, for executing a fixed point divide instruction using a floating point execution unit, comprising: 
 receiving, in the floating point execution unit, operands of the fixed point divide instruction, wherein the operands include a numerator and a divisor;    converting, in the floating point execution unit, the numerator and divisor to a floating point format;    generating, in the floating point execution unit, an estimate of a reciprocal of the divisor; and    determining a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor.    
   
   
       2 . The method of  claim 1 , wherein generating an estimate of the reciprocal of the divisor includes using an estimate table unit in the floating point execution unit to lookup an estimate of the reciprocal of the divisor.  
   
   
       3 . The method of  claim 2 , wherein the lookup of the estimate of the reciprocal of the divisor in the estimate table unit is based on a shifted mantissa of the divisor.  
   
   
       4 . The method of  claim 1 , wherein determining a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor includes using a quadratically converging division algorithm for fixed point division.  
   
   
       5 . The method of  claim 4 , wherein the quadratically converging division algorithm is implemented using a state machine having states corresponding to fused-multiply-add/subtract operations that are to be performed by the floating point execution unit.  
   
   
       6 . The method of  claim 5 , wherein the state machine implementing the quadratically converging division algorithm avoids a remainder comparison operation by providing a perturbation value to a multiplier of the floating point execution unit to perturb an intermediate result.  
   
   
       7 . The method of  claim 1 , wherein determining a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor includes using a hardware state machine having states corresponding to fused-multiply add/subtract operations to be performed by the floating point execution unit to execute the fixed point divide instruction.  
   
   
       8 . The method of  claim 1 , wherein converting, in the floating point execution unit, the divisor to a floating point format includes using one of a leading zero counter value and a leading one counter value to shift a mantissa of the divisor.  
   
   
       9 . The method of  claim 8 , wherein generating, in the floating point execution unit, an estimate of a reciprocal of the divisor includes performing a lookup of the shifted mantissa of the divisor in a lookup table unit of the floating point execution unit to identify an estimate of the reciprocal of the divisor.  
   
   
       10 . The method of  claim 1 , wherein determining a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor includes: 
 making multiple passes through a pipeline of the floating point execution unit using results from a previous pass through the pipeline of the floating point execution unit, to generate estimates of the quotient for the fixed point divide instruction, wherein a final pass through the pipeline of the floating point execution unit involves truncating an estimate of the quotient to generate the quotient for the fixed point divide instruction.    
   
   
       11 . The method of  claim 1 , wherein determining a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor includes: 
 determining if the divisor is associated with a special case for fixed point divide instructions; and    ending the determination of the quotient for the fixed point divide instruction early if the divisor is associated with a special case for fixed point divide instructions.    
   
   
       12 . The method of  claim 11 , wherein determining if the divisor is associated with a special case for fixed point divide instructions includes determining if the divisor is associated with one of when the divisor is a power of 2, when the divisor is 1 or −1, and when one or more of the operands is zero.  
   
   
       13 . A system for executing a fixed point divide instruction using a floating point execution unit, comprising: 
 one or more floating point registers; and    a floating point execution unit coupled to the floating point registers, wherein the floating point execution unit receives operands of the fixed point divide instruction from one or more registers, wherein the operands include a numerator and a divisor, converts the numerator and divisor to a floating point format, generates an estimate of a reciprocal of the divisor, and determines a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor.    
   
   
       14 . The system of  claim 13 , wherein the floating point unit includes an estimate table unit, and wherein the floating point execution unit generates an estimate of the reciprocal of the divisor using the estimate table unit to lookup an estimate of the reciprocal of the divisor.  
   
   
       15 . The system of  claim 13 , wherein the floating point execution unit implements a quadratically converging division algorithm to determine a quotient for the fixed point divide instruction using the floating point formatted numerator, divisor and the estimate of the reciprocal of the divisor.  
   
   
       16 . The system of  claim 15 , further comprising: 
 a state machine coupled to the floating point execution unit, wherein the quadratically converging division algorithm is implemented using the state machine, and wherein the state machine has states corresponding to fused-multiply-add/subtract operations that are to be performed by the floating point execution unit.    
   
   
       17 . The system of  claim 16 , wherein the state machine implementing the quadratically converging division algorithm avoids a remainder comparison operation by providing a perturbation value to a multiplier of the floating point execution unit to perturb an intermediate result.  
   
   
       18 . The system of  claim 13 , further comprising: 
 A hardware state machine, coupled to the floating point execution unit, having states corresponding to fused-multiply-add/subtract operations to be performed by the floating point execution unit to execute the fixed point divide instruction.    
   
   
       19 . The system of  claim 13 , wherein the floating point execution unit includes a leading zero counter and a leading one counter, and wherein the floating point execution unit converts the divisor to a floating point format using one of a value from the leading zero counter and a value from the leading one counter to shift a mantissa of the divisor.  
   
   
       20 . The system of  claim 13 , wherein the floating point execution unit determines a quotient for the fixed point divide instruction includes: 
 making multiple passes through a pipeline of the floating point execution unit using results from a previous pass through the pipeline of the floating point execution unit, to generate estimates of the quotient for the fixed point divide instruction, wherein a final pass through the pipeline of the floating point execution unit involves truncating an estimate of the quotient to generate a final estimate of the quotient for the fixed point divide instruction.