Patent Publication Number: US-9417839-B1

Title: Floating point multiply-add-substract implementation

Description:
STATEMENT OF GOVERNMENT INTEREST 
     The invention described herein may be manufactured and used by or for the Government of the United States of America for governmental purposes without the payment of any royalties thereon or therefor. 
    
    
     CROSS REFERENCE TO OTHER PATENT APPLICATIONS 
     None. 
     BACKGROUND OF THE INVENTION 
     (1) Field of the Invention 
     The present invention is directed to an implementation of a floating point multiply-add-subtract implementation for digital circuitry. 
     (2) Description of the Prior Art 
     In digital computer processing, signed floating point numbers can be utilized in a form having a mantissa multiplied by a base having an exponent. Mathematical functions are carried out on these numbers in semiconductor floating point units or processors in binary format. The floating point unit does addition, subtraction, multiplication, and division operations on floating point numbers. In many implementations the exponent is usually biased which means that a number called the bias is subtracted from the written exponent before computation. This allows implementations to use a positive representation of a negative exponent, since the written exponent minus the bias is negative. The examples assume a normalized format, which means that the first bit of the mantissa is ‘1’. 
     The Institute of Electrical and Electronics Engineers (IEEE) has standards for floating point representation of numbers. The current standard used by most commercial processors is IEEE-754-2008. The output of this format is a binary floating point number that contains a sign, biased exponent, and mantissa. A 16-bit IEEE-754 floating point number is given by the following format:
         seee eemm mmmm mmmm
 
where each letter represents a binary digit or bit; s is the sign bit; each e is an exponent bit; and each m is a mantissa bit. In this format the minimum exponent is −14, and the maximum exponent is 15. The exponent bias is 15. This means that 15 is subtracted from the exponent value to give the actual value. An exponent value having all is 1s used to represent infinity or “not a number” known as NaN. An exponent value having all zeroes is used to represent a denormalized number. IEEE-754 32 bit, 64 bit, and 128 bit floating point formats are similar.
       

     Important resources for floating point unit implementation are its size and its speed. The size of the implementation is the number of gates that are required. Typical commercial 32 bit multiply/accumulate floating point units without division take approximately 12,800 gates. This commercial implementation runs at 1 MFlop/Mhz or 55 Mhz. 
     When utilizing field programmable gate arrays and other special purpose semiconductors, it is often desirable to reduce the number of gates and chip resources required for processing floating point numbers. It is further desirable to process these numbers as quickly as possible. 
     SUMMARY OF THE INVENTION 
     The first object of the present invention is to provide an implementation of a floating point unit utilizing fewer gates. 
     Another object is to provide an implementation of a floating point unit capable of operating at faster speeds than existing units. 
     Accordingly, there is provided a floating point multiply and addition/subtraction implementation. Two operands are received in a standard floating point format with a code selecting a mathematic operation from addition, subtraction, and multiplication. Result mantissas and exponents are calculated simultaneously for all operations. The implementation simplifies computation of a result mantissa by dropping the least significant bits of the operands before computing the result. Underflow and overflow errors are shown by two extra bits in the exponent portion of the result. The mantissa result and the exponent result are selected by providing the operation code to a mantissa multiplexer and an exponent multiplexer. The selected mantissa and exponent are combined as output. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Reference is made to the accompanying drawings in which are shown an illustrative embodiment of the invention, wherein corresponding reference characters indicate corresponding parts, and wherein: 
         FIG. 1  is a diagram of an overview of the implementation; 
         FIG. 2  is a detailed diagram of the add/subtract section of the implementation; and 
         FIG. 3  is a detailed diagram of the multiply section of the implementation. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The benefits of the floating point unit implementation contained herein are accomplished via pipelining, simplification of exception handling and other hardware techniques. The current implementation calculates NaN, underflow, and overflow exception conditions by calculating the exponent with two additional bits of precision and using signed two&#39;s complement binary format. This eliminates complex error/exception detection circuitry because in this format, either of the two most significant bits of the exponent will only be 1 when an exception occurs. Underflow occurs when the most significant bit is 1 because the exponent is negative. Overflow occurs when the two most significant bits are 01 because the exponent portion has exceeded its range. NaN is indicated when the exponent bits following the two most significant bits are all 1&#39;s, and the mantissa is non-zero. In the current implementation, post calculation detection of this condition is unnecessary. 
     The floating point unit implementation receives two floating point numbers A in  and B in . The floating point number is separated into component parts for processing. For this purpose, in  FIG. 2  the mantissa of A in  is identified as A man , and the mantissa of B in  is identified as B man . The exponent of A in  is identified as A exp , and the exponent of B in  is identified as B exp . The sign of each number is identified as A sgn  and B sgn . This can be performed by segregating the appropriate bits. 
       FIG. 1  gives an overview of the floating point unit implementation  10 . The floating point unit implementation  10  receives A in  and B in  in a floating point format that can be broken up into signs, mantissas, and exponents. These numbers are provided to an initial error detection module  11 , an add/subtract section  12  and a multiply section  14 . The user also provides an opcode that selects the operation—multiplication, addition, or subtraction—of the floating point unit implementation  10 . 
     Prior to computation, error detection module  11  checks for NaNs at the inputs by checking if the exponent of either operand, A in  or B in , is all 1s, and its mantissa is non-zero. (This can be performed by conducting an AND operation among all of the exponent bits of the operand, conducting an OR operation among all of the mantissa bits of the operand, and executing an AND between the two results.) Error detection module  11  then asserts signal A NaN  if A in  is NaN, B NaN  if B in  is NaN, and a signal NaN if either A in , B in , or both is NaN. Next error detection module  11  checks for zeroes at the inputs, and then asserts A zero  if both A exp  is negated and A man  is zero. Likewise, B zero  is asserted if B exp  is negated and B man  is zero. Error detection module  11  then checks for infinities at the inputs and asserts A inf  if A exp  is all asserted while A man  is all negated. B inf  is asserted if B exp  is all asserted, and B man  is all negated. Next, error detection module  11  checks for signaling NaNs at the inputs, and A sNaN  is asserted when both A NaN  is asserted and the most significant bit of A man  is negated. Similarly, B sNaN  is asserted when B NaN  is asserted and the most significant bit of B man  is negated. 
     Next, error detection module  11  checks if invalid operation exceptions/signaling NaNs exist at the inputs based upon the opcode. If the opcode indicates addition an invalid operations flag, InvOp, is asserted when A sNaN  is asserted, or B sNaN  is asserted, or both A inf  and B inf  are asserted and A sgn  and B sgn  differ. If the opcode indicates subtraction then InvOp is asserted when A sNaN  is asserted, or B sNaN  is asserted, or both A inf  and B inf  are asserted and A sgn  and B sgn  match. If the opcode indicates multiplication then InvOp is asserted when A sNaN  is asserted, or B sNaN  is asserted, or both A inf  and B zero  are asserted and NaN is negated, or both A zero  and B inf  are asserted and NaN is negated. Next error correction module  11  modifies the diagnostic mantissa output, Y NaN , to indicate invalid operations and NaN error conditions. Y NaN  is set to A man  if A is a NaN, that is if either A NaN  or A sNaN  is asserted. Y NaN  is set to B man  if B is a NaN. If both A and B are NaNs, Y NaN  is set to A man . The first bit of Y NaN  can be use to indicate a signaling NaN versus a quiet NaN under the IEEE standard. 
     Further details of the add/subtract section  12  will be given in reference to  FIG. 2 , and further details of the multiply section  14  will be given in reference to  FIG. 3 . The mantissa outputs of the add/subtract section  12 , Y madd  and Y mmin , and the multiply section  14 , Y mmult , are provided to a mantissa multiplexer  16 . The opcode is further provided to the mantissa multiplexer  16  to select the correct mantissa function input as the mantissa output, Y man . The exponent outputs of the add/subtract section  12 , Y pexp , and the multiply section  14 , Y mexp , are provided to an exponent multiplexer  18 . The opcode is further provided to the exponent multiplexer  18  to select the correct exponent function input as the exponent result output, Y exp . An error check module  20  receives the exponent result output Y exp , and Y man , the input operands A in  and B in  and NaN output from error detection module  11 . Error check module  20  both computes the diagnostic error output and corrects the exponent and mantissa result outputs for the output format as described hereinafter. The mantissa output Y man  and the exponent output Y exp  are combined in at an output  22  to give the preferred output form. The diagnostic error output of error check module  20  can be a bus which contains the InvOp, overflow, underflow, and inexact error flag signals from error detection module  11  and error check module  20 . A divide by zero flag can be included for compatibility, but this flag will never be asserted. In an alternative embodiment, error check module  20  can give a diagnostic code that can be used to give these flags. 
       FIG. 2  provides a detailed view of add/subtract section  12 . Add/subtract section  12  includes an exponent comparator  24  and an exponent subtractor  26 . Exponent comparator  24  receives the exponent component of the inputs, A exp  and B exp , and provides the larger of the two exponents as the preliminary add/subtract result exponent, Y pexp . Exponent subtractor  26  receives the exponent inputs, A exp  and B exp , and provides the difference between them, C dexp , for use in scaling the values. Register  28  receives exponent difference, C dexp , and the mantissa inputs, A man  and B man , and scales these inputs relative to one another. An adder/subtractor  30  receives the scaled mantissa inputs and provides addition results Y madd  and subtraction results Y mmin  for these inputs. 
       FIG. 3  provides a detailed view of multiply section  14 . A mantissa multiplier  32  receives mantissa inputs A man  and B man  and provides a multiplied mantissa output M out . The multiplied mantissa output, M out , is provided to a priority encoder  34  which determines the maximum place value of the mantissa output M out . This maximum place value is provided to shift logic  36  which provides a number of shifts N shift , for the mantissa to fit into the places allocated for the format. A mantissa shift register  38  receives the mantissa output, M out , and the number of shifts, N shifts . Shift register  38  shifts the mantissa output by dropping the least significant bits of the mantissa output until the mantissa is the same length in bits as the mantissa portion of the format. Shift register  38  provides an unsigned multiplication result Y imult . Shift register  38  also provides an exponent correction that will be used as described below. 
     In order to calculate the sign of the output, an XOR gate receives the sign bits of the inputs, A sgn  and B sgn , and provides the sign of the result Y sgn  as the exclusive or of the sign inputs. The sign of the result Y sgn  is combined in a combiner  42  with the unsigned mantissa multiplication result Y imult  to give Y mmult . 
     A preliminary multiplication exponent result, Y pmexp , is calculated from the input exponents, A exp  and B exp , in a multiplication exponent adder  44 . Exponent calculation logic  46  receives the preliminary multiplication exponent result, Y pmexp , and combines this with the exponent correction from the mantissa shift register  38  to give a multiplication exponent result, Y mexp . 
     Overall operation of the floating point unit implementation is described in the following text. 
     Mantissa multiplier  32  calculates the mantissa of A man *B man  and provides the product, M out , with sufficient precision to store the entire result. This could be the place number precision of A man  added to the place number precision of B man , or double the precision of A man  or B man  if both have the same precision. Of course a lower precision result may be acceptable for some applications. This product, M out , will be shifted in operations in a later stage to drop the least significant digits. 
     A preliminary result exponent, Y pmexp , is determined by adding A exp  to B exp  in multiplication exponent adder  44 . Multiplication exponent adder  44  utilizes two extra bits in the most significant places in these exponent calculations. For example, in IEEE 764 16 bit, the exponents and results would each be five bit values; however, in this implementation, the result is a seven bit value. These extra, most significant bits will only be asserted in cases of underflow and overflow. This will be explained below. 
     The sign of the final output is determined by executing an “exclusive or” or XOR operation on A sgn  and B sgn  to give Y sgn . This allows use of a simple XOR  40  gate to give the sign for multiplication. 
     The priority encoder  34  is used to get the order of the multiplication result M out  from the mantissa multiplier  32 . The order is the position of the most significant bit of M out . (For example, if 0100 (4)*0011 (3)=1100 (12) the binary order would be 4 because the most significant digit 1xxx is in the fourth position.) This is used to determine the number of right shifts of M out  that will be required for the product to fit in the floating point format. (In 16 bit implementations, 10 bits are allowed. In 8 bit implementations, 4 bits are allowed.) In a preferred embodiment the priority encoder  34  with shift logic  36  determines the order of the bits beyond the number of bits allowed. This can be used directly as the number of shifts, N shifts . In an alternate embodiment the order is the absolute order of the product, and this order is converted into a number of shifts, N shifts . There are no shifts if the order is less than number of bits allowed. If the order is greater than the number of bits allowed, the number of shifts is an adjustment calculated as the order minus the number of bits allowed. 
     The product of A man  and B man , M out , is shifted by N shifts  in mantissa shift register  38  so that it fits into the number of bits allowed by dropping the least significant digits. This gives Y mmulti , the mantissa of the multiplication result. The multiplication exponent Y mexp  is calculated in an exponent calculation component  46  by adding the preliminary result exponent Y pmexp  to the number of shifts required for the mantissa N shifts . 
     The addition/subtraction process is more fully described below. A exp  and B exp  are compared using exponent comparator  24  to give the greater of the two exponents as a preliminary addition/subtraction result exponent, Y pexp . The difference between A exp  and B exp  is calculated by exponent subtractor  26 , by for example, subtracting B exp  from A exp  as C dexp  using two&#39;s complement addition. Two&#39;s complement addition uses less complicated logic to manage the signs and give a difference. A man  and B man  are scaled in register  28  by shifting the mantissa of the operand having the lower exponent. This shift uses the exponent difference C dexp  to shift the mantissa&#39;s bits to less significant places. The operand being shifted is governed by the sign of the difference, C dexp . (One of ordinary skill in the art would understand this as “right shifting” the mantissa.) For example if C dexp  is positive this means that A exp  is greater than B exp  and B man  is shifted by C dexp  positions. If C dexp  is negative B exp  is less than A exp , and A man  is shifted by C dexp  positions. This shift truncates the least significant digits of the smaller operand if one operand is significantly smaller than the other. The register  28  also aligns the mantissas prior to addition so that when the operand and the shifted operand are added the bits will be in the appropriate place value. 
     The register  28  adds an extra bit of precision to A man  and B man  which have been shifted as described above. A combined adder/subtractor receives the shifted mantissa A man  and B man  having the extra exponent bit. The adder/subtractor converts these numbers to signed two&#39;s complement format by taking the complement of each number and adding one to the complement of each number if the sign bit is 1. While two&#39;s complement addition requires the extra bit of precision, it greatly simplifies addition and subtraction because the sign can be ignored. The adder/subtractor  30  calculates an addition result A man +B man  to give the mantissa of the addition result, Y madd  and a subtraction result A man −B man  to give the mantissa of the subtraction result, Y mmin . Y madd  and Y mmin  are then converted by adder/subtractor  30  from two&#39;s complement form to signed magnitude form of the result mantissas. 
     Error check module  20  checks the two most significant bits of Y exp  to determine if an error condition such as an underflow/overflow, inexact or NaN condition exists. If the opcode indicates addition and A sgn  and B sgn  differ or the second-most most significant bit of Y exp  is asserted and the A inf  OR B inf  inputs from error detection module  11  are asserted then Y exp  is all asserted. Else, if the opcode indicates addition and the A zero  or B zero  inputs from error detection module  11  are asserted, or the most significant bit of Y exp  is asserted, then Y exp  changed to all negated. If the opcode indicates subtraction and A sgn  and B sgn  match and the A inf  OR B inf  inputs from error detection module  11  are asserted, or the NaN or InvOp inputs from error detection module  11  is asserted, or the second-most most significant bit of Y exp  is asserted then Y exp  is all asserted. Else, if the opcode indicates subtraction and the A zero  or B zero  inputs from error detection module  11  are asserted, or the most significant bit of Y exp  is asserted, or the NaN or InvOp inputs from error detection module  11  is asserted, then Y exp  changed to all negated. If the opcode indicates multiplication and the NaN or InvOp inputs from error detection module  11  are asserted, or the A inf  or B inf  inputs from error detection module  11  are asserted and the second most significant bit of Y exp  is negated, then Y exp  is changed to all asserted. Else, if the opcode indicates multiplication and the A zero  or B zero  inputs from error detection module  11  are asserted, or the most significant bit of Y exp  is asserted, then Y exp  changed to all negated the IEEE 754 convention for indicating these conditions. If the InvOp or NaN inputs from error detection module  11  are asserted, then Y man  is set to the Y NaN  input from error detection module  11 . Else, if either of the first two most significant bits of Y exp  are all asserted, or the remaining bits after the first two most significant bits of Y exp  are all asserted, or all bits of Y exp  are negated, then Y man  is set to all negated, the IEEE 754 convention for indicating these conditions. If all remaining bits after the most significant bit of Y exp  are asserted, and both NaN and InvOp inputs from error detection module  11  are negated then overflow is asserted. Otherwise, if all remaining bits after the most significant bit of Y exp  are negated, and both NaN and InvOp inputs from error detection module  11  are negated then underflow is asserted. If the A zero  input from error detection module  11  is asserted and A man  is not all negated, or the B zero  input from error detection module  11  is asserted and B man  is not all negated, then the inexact output is asserted, the IEEE 754 convention for indicating these conditions. The diagnostic error output of error check module  20  is a bus which contains the InvOp, overflow, underflow, and inexact output signals from error check module  20 . Bus can include a divide by zero line for compatibility, but this line will never be asserted because this implementation lacks a divide module. 
     A mantissa multiplexer selects among Y mmin , Y madd  and Y mmult  based on the opcode to provide the result mantissa Y man . Y mmin  is selected if the opcode indicates subtraction, Y madd  is selected if the opcode indicates addition, and Y mmult  is selected if the opcode indicates multiplication. In final processing, Y out  is composed from Y exp  and Y man . 
     This apparatus can be implemented utilizing many different technologies. These technologies include field programmable gate arrays, application specific integrated circuits, portions of integrated circuits, programmable read only memory, programmable logic arrays, hard-wired electrical circuits, or the like. 
     It will be understood that many additional changes in the details, materials, steps, and arrangement of parts, which have been herein described and illustrated in order to explain the nature of the invention, may be made by those skilled in the art within the principle and scope of the invention as expressed in the appended claims. 
     The foregoing description of the preferred embodiments of the invention has been presented for purposes of illustration and description only. It is not intended to be exhaustive, nor to limit the invention to the precise form disclosed, and obviously, many modification and variations are possible in light of the above teaching. Such modifications and variations that may be apparent to a person skilled in the art are intended to be included within the scope of this invention as defined by the accompanying claims.