Patent Abstract:
Circuitry (fixed or configured in a programmable device) for performing floating point addition and subtraction uses approximately the same resources as required for either operation separately. The circuitry is based on a recognition that when adding or subtracting two numbers, the two resulting mantissa values will be two out of three possibilities, and will involve either a one-bit shifting operation, or a shifting operation involving a large number of bits. Therefore, one mantissa path—a subtraction path—can be provided with full add/normalize/round circuitry, while a second mantissa path—an addition path—can be provided with a simple one-bit shifter and simplified rounding circuitry. Because the input numbers are signed, the “addition path,” which only adds the mantissas, may provide the mantissa for the subtraction result, depending on the signs of the input numbers. Similarly, the “subtraction path” may provide the mantissa for the addition result.

Full Description:
BACKGROUND OF THE INVENTION 
     This invention relates to performing floating point arithmetic operations in programmable integrated circuit devices such as programmable logic devices (PLDs). More particularly, this invention relates to circuitry for performing floating point addition and subtraction using approximately the same resources as required for either operation separately. 
     Certain mathematical operations may require both the sum and difference of two floating point numbers. For example, one technique for computing Fast Fourier Transforms uses a radix-2 butterfly that requires simultaneous addition and subtraction of two numbers. In fixed logic devices, where it is known that such operations will be performed, appropriate circuitry may be provided to efficiently carry out those addition and subtraction operations. However, in programmable devices, where only some particular user logic designs may need to perform such operations, it may be inefficient to provide all of the resources to separately perform such operations. Even in fixed logic, it may be desirable to reduce the required resources for such operations. 
     SUMMARY OF THE INVENTION 
     The present invention relates to circuitry for performing floating point addition and subtraction using approximately the same resources as required for either operation separately. The circuitry can be provided in a fixed logic device, or can be configured into a programmable integrated circuit device such as a programmable logic device (PLD). 
     The present invention is based on a recognition that when adding or subtracting two numbers, the two resulting mantissa values will be two out of three possibilities, and will involve either a one-bit shifting operation, or a shifting operation involving a large number of bits. 
     Therefore, in accordance with the present invention, there is provided combined floating-point addition and subtraction circuitry for both adding and subtracting a first signed floating-point input number and a second signed floating-point input number, where each of the first and second signed floating-point input numbers has a respective sign, a respective mantissa and a respective exponent, to provide a sum and a difference of said first and second signed floating-point numbers. The combined floating-point addition and subtraction circuitry includes a first mantissa computation path including a first adder for adding the mantissas of the first and second signed floating-point numbers, a one-bit right-shifting circuit for controllably shifting output of the first adder to normalize the output of the first adder, and rounding circuitry for (a) providing a first candidate mantissa and (b) providing a first exponent-adjustment bit. The combined circuitry also includes a second mantissa computation path including a first subtractor for subtracting the mantissa of the second signed floating-point number from the mantissa of the first signed floating-point number to provide a first mantissa difference, a second subtractor for subtracting the mantissa of the first signed floating-point number from the mantissa of the second signed floating-point number to provide a second mantissa difference, a selector for selecting as a mantissa difference output one of those first and second mantissa differences that is positive, and a normalize-and-round circuit for (a) providing a second candidate mantissa and (b) providing a second exponent-adjustment bit. The combined circuitry also includes a first exponent computation path for combining the input stage output exponent and the first exponent adjustment bit to provide a first candidate exponent. The combined circuitry also includes a second exponent computation path for combining the input stage output exponent and the second exponent adjustment bit to provide a second candidate exponent. Finally, the combined circuitry also includes a selection stage for selecting, based on the respective signs, one of the first and second candidate mantissas and one of the first and second candidate exponents for the sum of said first and second signed floating point numbers, and another of the first and second candidate mantissas and another of the first and second candidate exponents for the difference of the first and second signed floating point numbers. 
     A method of configuring such circuitry on a programmable device, a programmable device so configured, and a machine-readable data storage medium encoded with software for performing the method, are also provided. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above and other objects and advantages of the invention will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which: 
         FIG. 1  shows a known arrangement for reducing the resources needed to compute both the sum and the difference of the same two numbers; 
         FIG. 2  shows one potential embodiment of an add/normalize/round path in the arrangement of  FIG. 1 ; 
         FIG. 3  shows an arrangement in accordance with an embodiment of the invention for computing the sum and difference of two inputs; 
         FIG. 4  is a cross-sectional view of a magnetic data storage medium encoded with a set of machine-executable instructions for performing the method according to the present invention; 
         FIG. 5  is a cross-sectional view of an optically readable data storage medium encoded with a set of machine executable instructions for performing the method according to the present invention; and 
         FIG. 6  is a simplified block diagram of an illustrative system employing a programmable logic device incorporating the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Floating point numbers are commonplace for representing real numbers in scientific notation in computing systems. Examples of real numbers in scientific notation are:
         3.14159265 10 ×10 0  (π)   2.718281828 10 ×10 0  (e)   0.000000001 10  or 1.0 10 ×10 −9  (seconds in a nanosecond)   3155760000 10  or 3.15576 10 ×10 9  (seconds in a century)       

     The first two examples are real numbers in the range of the lower integers, the third example represents a very small fraction, and the fourth example represents a very large integer. Floating point numbers in computing systems are designed to cover the large numeric range and diverse precision requirements shown in these examples. Fixed point number systems have a very limited window of representation which prevents them from representing very large or very small numbers simultaneously. The position of the notional binary-point in fixed point numbers addresses this numeric range problem to a certain extent but does so at the expense of precision. With a floating point number the window of representation can move, which allows the appropriate amount of precision for the scale of the number. 
     Floating point representation is generally preferred over fixed point representation in computing systems because it permits an ideal balance of numeric range and precision. However, floating point representation requires more complex implementation compared to fixed point representation. 
     The IEEE754-1985 standard is commonly used for floating point numbers. A floating point number includes three different parts: the sign of the number, its mantissa and its exponent. Each of these parts may be represented by a binary number and, in the IEEE754-1985 format, have the following bit sizes: 
     
       
         
               
               
               
               
               
             
           
               
                   
               
               
                   
                 Sign 
                 Exponent 
                 Bias 
                 Mantissa 
               
               
                   
               
             
             
               
                 Single 
                 1 bit 
                 8 bits 
                 −127 
                 23 bits 
               
               
                 Precision 
                 [31] 
                 [30. . .23] 
                   
                 [22. . .00] 
               
               
                 32-Bit 
                   
                   
                   
                   
               
               
                 Double 
                 1 bit 
                 11 bits 
                 −1023  
                 52 bits 
               
               
                 Precision 
                 [63] 
                 [62. . .52] 
                   
                 [51. . .0] 
               
               
                 64-Bit 
               
               
                   
               
             
          
         
       
     
     The exponent preferably is an unsigned binary number which, for the single precision format, ranges from 0 to 255. In order to represent a very small number, it is necessary to use negative exponents. To achieve this the exponent preferably has a negative bias associated with it. For single-precision numbers, the bias preferably is −127. For example a value of 140 for the exponent actually represents (140−127)=13, and a value of 100 represents (100−127)=−27. For double precision numbers, the exponent bias preferably is −1023. 
     As discussed above, according to the standard, the mantissa is a normalized number—i.e., it has no leading zeroes and represents the precision component of a floating point number. Because the mantissa is stored in binary format, the leading bit can either be a 0 or a 1, but for a normalized number it will always be a 1. Therefore, in a system where numbers are always normalized, the leading bit need not be stored and can be implied, effectively giving the mantissa one extra bit of precision. Therefore, in single precision format, the mantissa typically includes 24 bits of precision. 
     In order to add two floating point numbers having different exponents, one of the numbers has to be denormalized so that the exponents are the same. This may be achieved by left-shifting the larger number by the difference in exponents, or by right-shifting the smaller number by that difference. After the numbers have been “aligned” by denormalization, they may added or subtracted (where subtraction may be addition with one negated input), then (re)normalized. As a further step, the normalized result may be rounded, and compliance with the IEEE754-1985 standard typically includes rounding. 
     The most straightforward technique to compute both the sum and the difference of the same two numbers is to use two complete separate circuit paths, where one path performs denormalization, addition, (re)normalization and rounding, while the other path performs denormalization, subtraction, (re)normalization and rounding. This technique consumes the maximum possible resources for computing the sum and difference of the same two numbers, namely about twice the resources needed for computing either alone. 
     A first, known, arrangement  100  for reducing the resources needed to compute both the sum and the difference of the same two numbers is shown in  FIG. 1 . Arrangement  100  uses a shared input path  101  for denormalization, followed by two separate, independent add(subtract)/(re)normalize/round paths  102 ,  103 . 
     Shared input path  101  is able to determine which of the two input numbers is larger and to denormalize the smaller number by right-shifting it, and also to select the exponent of the larger number as the resultant exponent. As can be seen, shared input path  101  includes respective register  104 ,  105  for the respective sign bit of each of the two input numbers, respective register  106 ,  107  for the respective mantissa of each of the two input numbers, and respective register  108 ,  109  for the respective exponent of each of the two input numbers. 
     The sign bits are passed straight through to add(subtract)/(re)normalize/round paths  102 ,  103 . Depending on the particular application, optional pipeline registers  114 ,  115 ,  124 ,  125  may be used for this purpose. 
     The mantissas and exponents are handled as follows: 
     Subtractor  110  subtracts the exponent in register  109  from the exponent in register  108 , while subtractor  111  subtracts the exponent in register  108  from the exponent in register  109 . The two differences are input to multiplexer  112 , while the two exponents themselves are input to multiplexer  113 . The most significant bit (MSB) of difference  110  is used as the control bit for multiplexers  112 ,  113 . Because difference  110  is a signed number, its MSB will be 0 for a positive difference (exponent  108  greater than exponent  109 ), thereby selecting difference  110  as the difference  118  and exponent  108  as the resultant exponent  119 , or 1 for a negative difference (exponent  109  greater than exponent  108 ), thereby selecting difference  111  as the difference  118  and exponent  109  as the resultant exponent  119 . Exponent  119  is propagated to the final stages, optionally through one or more pipeline registers  129 . 
     Mantissas  106 ,  107  are similarly input, in respective opposite order, to respective multiplexers  116 ,  117 , which also are controlled by the MSB of difference  110  to select mantissa  106  as part of the larger operand and mantissa  107  as part of the smaller operand when exponent  108  is larger, or mantissa  107  as part of the larger operand and mantissa  106  as part of the smaller operand when exponent  109  is larger. Larger mantissa  120  is input (after pipelining through registers  121 ,  122  if necessary) to add(subtract)/(re)normalize/round paths  102 ,  103 . Smaller mantissa  123  may be right-shifted at  126  by exponent difference  110 / 111  so that it may be added (after pipelining through registers  127 ,  128 , if necessary) to, or, after negation at  136 , subtracted from, larger mantissa  120  in add(subtract)/(re)normalize/round paths  102 ,  103  to compute the sum and difference. Add/(re)normalize/round path  103  and inverter  129  may be considered as, and may be replaced by, an integrated subtract/(re)normalize/round path  146 . 
     Each add(subtract)/(re)normalize/round path  102 ,  103  outputs a sum or difference mantissa  132 ,  133 , as well as an exponent adjustment value  130 ,  131  which is subtracted at  134 ,  135  from resultant exponent  119  to yield the final candidate exponents  139 ,  140 . Exponent adjustment values  130 ,  131  are determined during (re)normalization in paths  102 ,  103 , and their magnitudes depend on the relative magnitudes of the mantissas  120 ,  123  and whether they are being added or subtracted. 
     By sharing input stage  101 , arrangement  100  is about 50% larger than a single add or subtract path as compared to providing two completely separate add and subtract paths, which would be 100% larger than a single path. Conversely, arrangement  100  may be viewed as being about 30% smaller than two completely separate add and subtract paths. 
       FIG. 2  shows one potential embodiment  200  of the add/(re)normalize/round path  102 ,  103  of  FIG. 1 . If the operands are in signed-number format, in which the sign of the number is indicated by one of the bits of the number itself, then the operands are input at  201 ,  202  to adder/subtractor  203 . If the operands are in signed-magnitude format, in which the magnitude is always positive and the sign is indicated by a separate bit (or bits), then the operands are input at  211 ,  212  to respective signed-magnitude-to-signed-number converters  221 ,  222  for conversion to signed numbers which are then input at  201 ,  202 . The conversion from signed-magnitude format to signed-number format is well known. Either way, the exponent is input at  204 , with optional pipelining registers  214 ,  224 . Exclusive-OR gate  205  and adder  206  compute absolute value  213  of the sum or difference  203 . The resultant mantissa  213  is normalized by counting leading 0&#39;s at  207  (if signed numbers are used, leading 1&#39;s may be counted as well), and using the leading 0 count  217  to left-shift mantissa  213  at  227 , and to adjust exponent  204  at subtractor  234 . Normalized mantissa  223  is then rounded, in a manner which may be well-known, by examining one or more rounding bits (e.g., a “round” bit, a “guard” bit, and a “sticky” bit) at  208 , to provide rounded, final mantissa  233 . The amount of rounding may require one further adjustment of normalized exponent  244  at  254  to provide final exponent  264 . 
     In accordance with the invention, the resources needed for a simultaneous addition and subtraction of two numbers can be reduced further over the known embodiment of  FIGS. 1 and 2 . 
     It may be observed that if two numbers are close in magnitude to each other, then if they are added, their combined magnitude will almost double (a one-bit shift in a binary system), while if they are subtracted the result will be a very small number (a large bit shift from either number). Similarly, if two numbers are far apart in magnitude, then the magnitude of either their sum or their difference will be close to the magnitude of the larger number. Therefore, for addition, there is either no shift or a one-bit shift, while for subtraction, there could be a one-bit shift (if the minuend is negative and similar in magnitude to the subtrahend), or a very large shift (if the result is a very small number). 
     It also may be observed that if the two inputs have magnitudes A and B, then for computing the magnitude, the two operations will involve two out of the three possibilities A+B (for addition, or for subtraction if B is negative), A−B (for subtraction where B is smaller, or for addition where B is negative, and B−A (for subtraction where A is smaller, or for addition where A is negative). 
     In accordance with an embodiment of the invention, arrangement  300  of  FIG. 3  may be provided to compute the sum and difference of two inputs  301 ,  302 . Adder  303  may provide the sum of inputs  301  and  302 , subtractor  304  may provide the difference between input  301  and input  302 , and subtractor  305  may provide the difference between input  302  and input  301 . However if one or both of inputs  301 ,  302  is the mantissa of a negative number, adder  303  may compute a difference, while one of subtractors  304 ,  305  may compute a sum. For example, the magnitude of input  301  may denoted A and the magnitude of input  302  may be denoted B, with both A and B being positive values. If both input  301  and input  302  are mantissas of positive numbers, adder  303  and subtractors  304 ,  305  will compute A+B, A−B and B−A, respectively. If both input  301  and input  302  are mantissas of negative numbers, adder  303  and subtractors  304 ,  305  will compute A+B, B−A and A−B, respectively. If one of inputs  301 ,  302  is the mantissa of a positive number and the other of inputs  301 ,  302  is the mantissa of a negative number, then adder  303  will compute one of the differences, one of subtractors  304 ,  305  will compute the other difference, and the other of subtractors  304 ,  305  will compute the sum. 
     Although inputs A and B are always positive values, the outputs of adder  303  and subtractors  304 ,  305  are signed numbers. Which of these various sums and differences will be considered the mantissa of the final sum and which be considered the mantissa of the final difference will be determined by the signs of the input numbers as discussed below. 
     As stated above, the output path of adder  303  will require at most a one-bit right-shift  313  to provide normalized sum  323 , which is then rounded at  333 . The normalization and rounding may provide bits  306 , equalling 0, +1 or +2, by which input exponent  307  is adjusted at  317  to yield adjusted exponent  327 . Rounded sum  343  is provided as an input to each of multiplexers  308 ,  309  which select the correct mantissa results as discussed below. Similarly, adjusted exponent  327  is provided as an input to each of multiplexers  318 ,  319  which selects the correct exponent results as discussed below. 
     In the subtraction path, multiplexer  310  selects whichever difference  304  or  305  is positive. In a signed-number system where positive numbers begin with 0 and negative numbers begin with 1, the selection can be made by using the most-significant bit of difference  304  as the control bit for multiplexer  310  (assuming difference  304  is on the “0” input). The output of multiplexer  310  may be processed by a substantially standard (re)normalize/round path  311  (addition/subtraction having already occurred). As stated above, in the subtraction path, the degree of bit-shifting may be large or small depending on relative magnitudes. 
     (Re)normalize/round path  311  may output a mantissa value  321  which may be provided to multiplexers  308 ,  309  which select the correct mantissa results as discussed below. (Re)normalize/round path  311  also may output an adjustment value  331  for input exponent  307  to yield adjusted exponent  327 , which is provided as an input to each of multiplexers  318 ,  319  which selects the correct exponent results as discussed below. 
     After the two paths have been calculated, they have to be assigned to the correct outputs at multiplexers  308 ,  309 . The magnitudes or mantissas can be decoded from the input signs, as shown in the following table, in which input  301  is denoted as “X” and has magnitude or mantissa “A” and input  302  is denoted as “Y” and has magnitude or mantissa “B.” The signs of the results are assigned in sign assignment stage  320 , also as shown in the table. The correct exponents at multiplexers  318 ,  319  follow the magnitudes at multiplexers  308 ,  309 . 
     
       
         
               
               
               
               
               
               
             
           
               
                   
               
               
                 Sign X 
                 Sign Y 
                 |X + Y| 
                 Sign (X + Y) 
                 |X − Y| 
                 Sign (X − Y) 
               
               
                   
               
             
             
               
                 + 
                 + 
                 A + B 
                 + 
                 A − B 
                 Sign (A − B) 
               
               
                 + 
                 − 
                 A − B 
                 Sign (A − B) 
                 A + B 
                 + 
               
               
                 − 
                 + 
                 A − B 
                 Sign (B − A) 
                 A + B 
                 − 
               
               
                 − 
                 − 
                 A + B 
                 − 
                 A − B 
                 Sign (B − A) 
               
               
                   
               
             
          
         
       
     
     Thus it is seen that only one standard add(subtract)/(re)normalize/round path is required to perform two simultaneous floating point additions and subtractions on the same inputs. The second path can be replaced by a simple one-bit shift and rounding function, as shown. The logic resources need to simultaneously calculate the addition and subtraction of two floating point numbers therefore are barely more—i.e., about 10% more—than the logic resources needed for one addition or subtraction. 
     One potential use for the present invention may be in programmable integrated circuit devices such as programmable logic devices, where programming software can be provided to allow users to configure a programmable device to perform simultaneous floating point addition and subtraction. The result would be that fewer logic resources of the programmable device would be consumed. And where the programmable device is provided with a certain number of dedicated blocks for arithmetic functions (to spare the user from having to configure arithmetic functions from general-purpose logic), the number of dedicated blocks needed to be provided (which may be provided at the expense of additional general-purpose logic) can be reduced (or sufficient dedicated blocks for more operations, without further reducing the amount of general-purpose logic, can be provided). 
     Instructions for carrying out a method according to this invention for programming a programmable device to perform simultaneous floating point addition and subtraction may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming or configuring PLDs or other programmable devices to perform addition and subtraction operations as described above. For example, a personal computer may be equipped with an interface to which a PLD can be connected, and the personal computer can be used by a user to program the PLD using a suitable software tool, such as the QUARTUS® II software available from Altera Corporation, of San Jose, Calif. 
       FIG. 4  presents a cross section of a magnetic data storage medium  800  which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  800  can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate  801 , which may be conventional, and a suitable coating  802 , which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium  800  may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device. 
     The magnetic domains of coating  802  of medium  800  are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention. 
       FIG. 5  shows a cross section of an optically-readable data storage medium  810  which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  810  can be a conventional compact disk read-only memory (CD-ROM) or digital video disk read-only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium  810  preferably has a suitable substrate  811 , which may be conventional, and a suitable coating  812 , which may be conventional, usually on one or both sides of substrate  811 . 
     In the case of a CD-based or DVD-based medium, as is well known, coating  812  is reflective and is impressed with a plurality of pits  813 , arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating  812 . A protective coating  814 , which preferably is substantially transparent, is provided on top of coating  812 . 
     In the case of magneto-optical disk, as is well known, coating  812  has no pits  813 , but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating  812 . The arrangement of the domains encodes the program as described above. 
     A PLD  90  programmed according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system  900  shown in  FIG. 6 . Data processing system  900  may include one or more of the following components: a processor  901 ; memory  902 ; I/O circuitry  903 ; and peripheral devices  904 . These components are coupled together by a system bus  905  and are populated on a circuit board  906  which is contained in an end-user system  907 . 
     System  900  can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD  90  can be used to perform a variety of different logic functions. For example, PLD  90  can be configured as a processor or controller that works in cooperation with processor  901 . PLD  90  may also be used as an arbiter for arbitrating access to a shared resources in system  900 . In yet another example, PLD  90  can be configured as an interface between processor  901  and one of the other components in system  900 . It should be noted that system  900  is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims. 
     Various technologies can be used to implement PLDs  90  as described above and incorporating this invention. 
     It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.

Technology Classification (CPC): 6