Abstract:
A method and apparatus for reducing memory required to store reciprocal approximations as specified in Institute of Electrical and Electronic Engineers (IEEE) standards such as IEEE 754 is presented. Monotonic properties of the reciprocal function are used to bound groups of values. Efficient bit-vectors are used to represent information in groups resulting in a very compact table representation about four times smaller than storing all of the reciprocal approximations in a table.

Description:
FIELD 
       [0001]    This disclosure relates to methods and apparatus for performing arithmetic operations in a computer system and in particular to binary floating point arithmetic. 
       BACKGROUND 
       [0002]    A floating-point number is represented as a concatenation of a sign bit, an M-bit exponent field and an N-bit significand field. The IEEE standard for Binary Floating-Point Arithmetic (IEEE-754) defines formats for representing floating point numbers including single precision (M=8; N=24); double precision (M=11; N=53) and double-extended precision (M=15; N=64) formats. 
         [0003]    Division of floating point numbers (a/b) is performed using reciprocal approximation by first obtaining a reciprocal approximation of 1/b and refining the reciprocal approximation by a series of subsequent multiplication and subtraction operations. In many processor architectures, ten bit reciprocal approximations of 1/b are pre-computed and stored in a lookup table having 265 entries that is indexed by the eight Most Significant Bits (MSBs) of the operand ‘b’ treated as a normalized real number in binary of the form 1.xx. . . x that is defined by IEEE-754 standard. The lookup table storing the 256 reciprocal approximations may be implemented in specialized logic as a Programmable Logic Array (PLA). 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0004]    Features of embodiments of the claimed subject matter will become apparent as the following detailed description proceeds, and upon reference to the drawings, in which like numerals depict like parts, and in which: 
           [0005]      FIG. 1  illustrates reciprocal approximations stored in a 256 entry lookup table that may be used to perform division of binary floating point numbers; 
           [0006]      FIG. 2  illustrates a plurality of representations of groups of reciprocal approximations from which the reciprocal approximations shown in  FIG. 1  may be computed; 
           [0007]      FIG. 3  is a flowgraph illustrating an embodiment of a method for storing reciprocal approximations shown in  FIG. 1  as the plurality of representations of groups of reciprocal approximations shown in  FIG. 2 . 
           [0008]      FIG. 4  is a block diagram illustrating computation of a reciprocal approximation for an index using the representation of reciprocal approximations associated with the index; 
           [0009]      FIG. 5  is a flowgraph illustrating an embodiment of a method for computing a reciprocal approximation from a representation of a group of reciprocal approximations; and 
           [0010]      FIG. 6  is a block diagram of a system that includes an embodiment of an Arithmetic Logic Unit (ALU) in a processor to compute a reciprocal approximation corresponding to a selected one of the representations of a group of reciprocal approximations. 
       
    
    
       [0011]    Although the following Detailed Description will proceed with reference being made to illustrative embodiments of the claimed subject matter, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art. Accordingly, it is intended that the claimed subject matter be viewed broadly, and be defined only as set forth in the accompanying claims. 
       DETAILED DESCRIPTION 
       [0012]    A lookup in the PLA based lookup table for a reciprocal approximation is typically performed in about one cycle. However, the PLA based lookup table requires 256×10 bits (2560 bits) of memory to store all of the reciprocal approximations which consumes power in addition to the amount of memory needed. 
         [0013]    An embodiment of the present invention reduces the amount of memory needed to store the reciprocal approximations without changing the performance. In an embodiment the memory is about four times smaller than typically used by prior art lookup tables. 
         [0014]      FIG. 1  illustrates reciprocal approximations stored in a 256 entry lookup table  100  that may be used to perform division of binary floating point numbers. For example, the 256 fixed 10-bit values (in hexadecimal) that are stored in a PLA based lookup table used in Intel IA-64 Architecture processors are shown in the lookup table  100  in  FIG. 1  and also in the “Intel IA-64 Architecture Software Developer&#39;s Manual, Volume 3: Instruction Set Reference, January 2000”. 
         [0015]    The entries in the lookup table  100  are arranged in row-major form with eight entries per row and a total of 32 rows  102 _ 1 , . . . ,  102 _ 32 . The values (in hexadecimal format) stored in the 256 entries  104 _ 1 , . . . ,  104 _ 256  are reciprocal approximations for 1/b where b is in the range of 1.00000000 to 1.11111111. The reciprocal approximation of 1.00000000 (0×3FC) is stored in entry  104 _ 1  and the reciprocal approximation of 1.11111111 (0×001) is stored in entry  104 _ 256 . With 10-bits per entry and 256 entries in the lookup table, a PLA with an area proportional to 2560 units (256*10 bits) is required to store all of the reciprocal approximations. 
         [0016]    Looking at the values of the reciprocal approximations stored in the  256  entries  104 _ 1  . . .  104 _ 256  in the table  100  in  FIG. 1 , the values are monotonic in nature and the difference between any two successive values is small. The difference between any two successive values is not greater than eight and not less than two. Also, when moving from the value stored in entry  104 _ 1  to the value stored in entry  104 _ 256 , the differences between the values stored in any two successive entries  104 _ 1 , . . . ,  104 _ 256  decreases. 
         [0017]    For example, looking at the values stored in entries in the first row  102 _ 1 : entry  104 _ 8  stores a value of 0×3c6, moving across the entries in the row from left to right, the value stored in entry  104 _ 7  is 0×3cd, which is 0×3c6−7 (a difference of 7), the value stored in entry  104 _ 6  is 0×3d5 which is 0×3cd−8 (a difference of 8). Similarly, continuing across the first row  102 _ 1 , the difference been any two values stored in successive entries in the first row  102 _ 1  is either 7 or 8. 
         [0018]    A pattern may also be observed between values stored in successive entries in other rows in the lookup table  100 . For example, looking at the values stored in row  102 _ 3 , that is, 0×384, 0×37d, 0×376, 0×36f, 0×368, 0×361, 0×35b, 0×354, the difference between values stored in two successive entries in the third row  102 _ 3  is either 6 or 7. 
         [0019]    Looking at the values stored in row  102 _ 6 , that is, 0×2e8, 0&gt;2e2, 0×2dc, 0×2d7, 0×2d1, 0×2cb, 0×2c5, 0×2bf, the difference between values stored in successive entries in the sixth row is either 5 or 6. Looking at the values stored in row  102 _ 31 , that is, 0×020, 0×01e, 0×01c, 0×01a, 0×018, 0×015, 0×013, 0×011, the difference between values stored in two successive entries in the thirty first row is either 2 or 3. 
         [0020]    Thus, the difference between values stored in two successive entries in any one of the rows  102 - 1 , . . .  102 - 32  in the lookup table  100  is always n or n+1 where n is in the range of 2-7. Thus, instead of storing all 256 reciprocal approximations in lookup table  100 , the amount of memory may be reduced by encoding the reciprocal approximations for a row (that is, a group of reciprocal approximations) as a representation of a group of reciprocal approximations (an encoded group of reciprocal approximations) from which any of the reciprocal approximations in the group may be computed. 
         [0021]      FIG. 2  illustrates a plurality of representations of groups of reciprocal approximations from which the reciprocal approximations shown in  FIG. 1  may be computed. The plurality of representations of groups of reciprocal approximations may be stored in a lookup table  200 . Each representation of a group of reciprocal approximations  202 - 1 , . . . ,  202 - 32  includes a base reciprocal approximation  204 - 3  for the group  202 - 1 , . . . ,  202 - 32 . In an embodiment, the base reciprocal approximation  204 - 3  is the reciprocal approximation for the reciprocal approximation having the smallest value that is stored in the group (row). In an embodiment in which the group corresponds to a row  102 - 1 , . . .  102 - 32  in the lookup table  100  shown in  FIG. 1 , the base reciprocal approximation for row  102 - 1  is the reciprocal approximation stored in entry  104 - 8 , that is, 0×3c6, which is stored in group of reciprocal approximations  202 - 1 . 
         [0022]    In order to generate any of the eight reciprocal approximations for any of the rows  102 - 1 , . . . , 102 - 32  in the table  100  shown in  FIG. 1 , each representation of a group of reciprocal approximations  202 - 1 , . . . ,  202 - 32  includes a minimum-value of the difference between reciprocal approximations stored in successive entries in the group (row) (n)  204 - 1 . The representation of a group of reciprocal approximations  202 - 1 , . . . ,  202 - 32  also includes a bit mask vector  204 - 2  having single bit per reciprocal approximation for all reciprocal approximations other than the base reciprocal approximation in the group. The state of a bit in the bit mask vector  204 - 2  that corresponds to the reciprocal approximation in the group indicates whether to add the minimum difference  204 - 1  or the minimum difference plus one to the base reciprocal approximation  204 - 3  to compute the reciprocal approximation for the entry in the group. 
         [0023]    In an embodiment, the representation of a group of reciprocal approximations requires memory storage that is about four times smaller than the lookup table  100  discussed in conjunction with  FIG. 1  that stores all possible 256 reciprocal approximations. In the embodiment shown, instead of storing all 256 reciprocal approximations in 2560 bits, the 256 reciprocal approximations are encoded in 32 representations of groups of reciprocal approximations  202 - 1 , . . . ,  202 - 31  with each representation of a group of reciprocal approximations having 20 bits for a total of 640 bits. In an embodiment, additional logic to compute the reciprocal approximation corresponding to an index uses about 15 gates which occupy an insignificant area in comparison to the additional amount of memory required to store all of the reciprocal approximations as discussed in conjunction with  FIG. 1 . 
         [0024]      FIG. 3  is a flowgraph illustrating an embodiment of a method for storing the reciprocal approximations shown in  FIG. 1  as the plurality of representations of groups of reciprocal approximations shown in  FIG. 2 . 
         [0025]    At block  300 , the differences between successive reciprocal approximations in a group of reciprocal approximations is computed. In one embodiment the number of reciprocal approximations in a group is eight, which is the same number of reciprocal approximations that are stored per row  102 - 1 , . . . , 102 - 32  in the lookup table  100  shown in  FIG. 1 . Processing continues with block  302 . 
         [0026]    At block  302 , the minimum difference between successive reciprocal approximations in the group (row) is stored in a minimum difference field  204 - 1  in table  200 . For example, as the difference between successive reciprocal approximations in row  102 - 1  of table  100  is either 7 or 8, the minimum difference, that is, 7 is stored in the minimum difference field  204 - 1  in representation of reciprocal approximations  202 - 1 . Processing continues with block  304 . 
         [0027]    At block  304 , an indication of whether the difference between successive reciprocal approximations in the group of reciprocal approximations is even or odd is stored in a bit mask  204 - 2 . For example, referring to  FIG. 1 , looking from left to right at the reciprocal approximations in row  102 - 1 , the differences are 8, 8, 8, 7, 8, 8, 7 which corresponds to even, even, even, odd, even, even, even, odd. Substituting ‘1’ for odd and ‘0’ for even, the bit mask is 0001001 (0×9) which is stored in the bit mask field  204 - 1  in the representation of reciprocal approximations  202 - 1 . Processing continues with block  306 . 
         [0028]    At block  306 , the reciprocal approximation that is stored in entry  104 - 8  that is, the entry for which the Least Significant Bits of an index are ‘111” is selected as the base reciprocal approximation and stored in the base reciprocal approximation field  204 - 3  in the representation of reciprocal approximations  202 - 1 . In other embodiments, other reciprocal approximations in the group may be selected as the base reciprocal approximation with appropriate selection of the bit mask vector so that any of the reciprocal approximations in the group may be computed using the base reciprocal approximation. For example, in an embodiment, the reciprocal approximation that is stored in entry  104 - 1 , that is, the entry for which the Least Significant Bits of an index are ‘000” may be selected as the base reciprocal approximation. Processing continues with block  308 . 
         [0029]    At block  308 , if there is another group of reciprocal approximations in table  100  to be encoded into a representation of reciprocal approximations, processing continues with block  300 . If not, processing is complete. 
         [0030]      FIG. 4  is a block diagram illustrating computation of a reciprocal approximation for an index using the representation of a group of reciprocal approximations associated with the index. In an embodiment with 256 reciprocal approximations, an 8-bit index (index[7:0]) is used to select one of the reciprocal approximations. 
         [0031]    The five Most Significant Bits (MSB) of the index are used to select the representation of a group of reciprocal approximations, in this example, the 5 MSBs of the index set to ‘00000’ selects the representation of a group of reciprocal approximations  202 - 1 . The three Least Significant Bits (LSB) are used to select bits from the bit mask vector, in this case, the three LSBs set to ‘101’. 
         [0032]    Referring to  FIG. 1 , row  102 - 1  stores reciprocal approximations for 1.00000000 to 1.00000111. 1.0000000 and, 1.00000111 are significands or mantissas having a one leading digit of 1 and fractional digits 00000100, 00000111 The reciprocal approximation for 1.00000000, that is, 0×3df is stored in entry  104 - 1  and the reciprocal approximation for 1.00000111, that is, 0&#39;3c6 is stored in entry  104 - 8 . 
         [0033]    Returning to  FIG. 4 , the representation of reciprocal approximations  202 - 1  represents reciprocal approximations for 1.000000000 to 1.00000111, with the five MSBs of the fractional digits of the significand (00000) selecting representation of reciprocal approximations  202 - 1 . 
         [0034]      FIG. 5  is a flowgraph illustrating an embodiment of a method for computing a reciprocal approximation corresponding to an index from a representation of reciprocal approximations.  FIG. 5  will be described in conjunction with  FIGS. 1 ,  2  and  4 . 
         [0035]    At block  500 , in an embodiment in which there are 32 encoded representations of groups of reciprocal approximations stored in a table, the five Most Significant bits of the eight fractional digits of the significand are used as an index to the table to select one of the 32 representations of groups of reciprocal approximations. The representation of reciprocal approximations  202 - 1  is selected for index[7:3] of ‘00000”. Processing continues with block  502 . 
         [0036]    At block  502 , if the three Least Significant bits (LSB) of the 8 fractional digits of the significand index[2:0] are ‘111”, the base corresponds to the reciprocal approximation and processing continues with block  510 . If not, processing continues with block  504 , to determine the location of the requested reciprocal approximation. 
         [0037]    At block  504 , the representation of a group of reciprocal approximations includes a minimum difference  204 - 1 , a mask bit vector  204 - 2  and a base  204 - 3 . Referring to  FIG. 2 , in the representation of a group of reciprocal approximations  202 - 1  that corresponds to the index which is a mantissa or significand of a floating point number, for example, 1.000000101, the 3-bit minimum difference  204 - 1  is 0×7, the 7-bit mask bit vector is 0×9 (0001001) and the 10-bit base reciprocal approximation is 0×3c6. First, the number of bits of the mask to process (that is, the column location of the reciprocal approximation in the table shown in  FIG. 1 ) is determined by subtracting the three least significant fractional digits (index[2:0] of the significand from the minimum difference  204 - 1 , that is, in base  2 ,  111 - 101  (0×7−0×5). The result is 010 (0×2). Processing continues with block  506 . 
         [0038]    At block  506 , in this case, the minimum difference (n) is 7, an odd number and n+1 is 8, an even number. Thus, the odd difference value is 7 and the even difference value is 8. The mask bit vector  204 - 2  is 0×9 (1001 in base  2 ). Based on the result (0×2), the two least significant bits of the mask bit vector which store ‘01’ are used to compute the reciprocal approximation. The bits of the mask bit register indicate whether the even difference value (8) or the odd difference value (7) are added to the base reciprocal approximation to compute the reciprocal approximation with ‘1’ indicating odd and ‘0’ indicating even. The sum of the odd difference value (0×7) and the even difference value (0×8) is 15 (0×f). Processing continues with block  508 . 
         [0039]    At block  508 , the sum of the difference values (0×f) is added to the base reciprocal approximation 0×3c6. The result is 0×3d5 which corresponds to the reciprocal approximation stored in entry  104 - 6  in table  100  in  FIG. 1 . 
         [0040]    In an embodiment, the computation of the difference between the reciprocal approximation and the base may be performed by Carry Save Adders (CSAs). 
         [0041]    An embodiment has been described for a table with 32 20-bit entries storing the representation of the group of reciprocal approximations for a group of 8 reciprocal approximations, with the base approximation reciprocal having the smallest reciprocal approximation in the group. In another embodiment, the table may have 64 16-bit entries storing the representation of the group of reciprocal approximations for a group of 4 reciprocal approximations. In this embodiment, a 1024-bit table is required to store the 64 entries each having a 10-bit base reciprocal approximation has 10-bits, a 3-bit minimum difference has 3-bits and a 3-bit mask vector. In contrast to the embodiment for a 32 entry table, the critical path for the 64 entry table is a little faster and the 1024-bit table provides about a fifty pecent area reduction over the 2560 bit PLA based lookup table. 
         [0042]    In an embodiment, the table  200  is included in an Arithmetic Logical Unit in a processor for use by division algorithms. In other embodiments, the table  200  is included in a floating point unit in a processor for performing floating point division operations. 
         [0043]    An embodiment has been described for providing a respresentation of a group of reciprocal approximations by moving across entries in a row in a PLA based lookup table from left to right. In another embodiment, the representation of a group of reciprocal approximations may be provided by moving across entries in a row from right to left. 
         [0044]      FIG. 6  is a block diagram of a system  100  that includes an embodiment of an Arithmetic Logic Unit (ALU)  630  in a processor to compute a reciprocal approximation corresponding to a selected one of the representations of a group of reciprocal approximations. In an embodiment the ALU  630  includes a plurality of groups of representations of reciprocal approximations  200  as discussed in conjunction with  FIG. 2  and logic  400  for computing a reciprocal approximation as discussed in conjunction with  FIG. 4 . 
         [0045]    The system  100  includes a processor  301  that includes an ALU  630 , a Memory Controller Hub (MCH)  602  and an Input/Output (I/O) Controller Hub (ICH)  604 . The MCH  602  includes a memory controller  306  that controls communication between the processor  301  and memory  610 . The processor  601  and MCH  602  communicate over a system bus  616 . 
         [0046]    The processor  601  may be any one of a plurality of processors such as a single core Intel® Pentium IV ® processor, a single core Intel Celeron processor, an Intel® XScale processor or a multi-core processor such as Intel® Pentium D, Intel® Xeon® processor, or Intel® Core® Duo processor or any other type of processor. 
         [0047]    The memory  610  may be Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), Synchronized Dynamic Random Access Memory (SDRAM), Double Data Rate 2 (DDR2) RAM or Rambus Dynamic Random Access Memory (RDRAM) or any other type of memory. 
         [0048]    The ICH  604  may be coupled to the MCH  602  using a high speed chip-to-chip interconnect  614  such as Direct Media Interface (DMI). DMI supports 2 Gigabit/second concurrent transfer rates via two unidirectional lanes. 
         [0049]    The ICH  604  may include a storage I/O controller  620  for controlling communication with at least one storage device  612  coupled to the ICH  604 . The storage device  612  may be, for example, a disk drive, Digital Video Disk (DVD) drive, Compact Disk (CD) drive, Redundant Array of Independent Disks (RAID), tape drive or other storage device. The ICH  604  may communicate with the storage device  612  over a storage protocol interconnect  618  using a serial storage protocol such as, Serial Attached Small Computer System Interface (SAS) or Serial Advanced Technology Attachment (SATA). 
         [0050]    It will be apparent to those of ordinary skill in the art that methods involved in embodiments of the present invention may be embodied in a computer program product that includes a computer usable medium. For example, such a computer usable medium may consist of a read only memory device, such as a Compact Disk Read Only Memory (CD ROM) disk or conventional ROM devices, or a computer diskette, having a computer readable program code stored thereon. 
         [0051]    While embodiments of the invention have been particularly shown and described with references to embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of embodiments of the invention encompassed by the appended claims.