Abstract:
A method includes receiving a dividend and a divisor for performing a division operation. Numbers p and n are found, for which the divisor equals 2 n (1+2 p ). An interim result, which is equal to a reciprocal of 1+2 p  multiplied by the dividend, is calculated. The interim result is divided by 2 n  to produce a result of the division operation.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to digital circuits, and particularly to methods and devices for performing integer division. 
       BACKGROUND OF THE INVENTION 
       [0002]    Digital systems often comprise different digital circuit blocks to realize different logical functions. For example, digital dividers are used to perform division computations on binary numbers. 
       SUMMARY OF THE INVENTION 
       [0003]    An embodiment of the present invention that is described herein provides a method including receiving a dividend and a divisor for performing a division operation. Numbers p and n are found, for which the divisor equals 2 n (1+2 p ). An interim result, which is equal to a reciprocal of 1+2 p  multiplied by the dividend, is calculated. The interim result is divided by 2 n  to produce a result of the division operation. 
         [0004]    In some embodiments, calculating the interim result includes evaluating a binary fraction having a pattern of alternating runs of p binary “1”s and p binary “0”s after the binary point. In an embodiment, calculating the interim result includes evaluating a finite number of terms in a power series of 1/2 2p . Evaluating the finite number of the terms may include evaluating a first number of the terms recursively from a second number of the terms that is smaller than the first number. In an example embodiment, receiving the dividend includes receiving a size of a memory, receiving the divisor includes receiving a length of a record in the memory, and the division operation finds a number of records in the memory. 
         [0005]    There is additionally provided, in accordance with an embodiment of the present invention, apparatus including an interface and a divider module. The interface is configured to receive a dividend and a divisor for performing a division operation. The divider module is configured to find numbers p and n for which the divisor equals 2 n (1+2 p ), to calculate an interim result that is equal to a reciprocal of 1+2 p  multiplied by the dividend, and to divide the interim result by 2 n  to produce a result of the division operation. 
         [0006]    The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]      FIG. 1  is a block diagram that schematically illustrates an integer divider module, in accordance with an embodiment of the present invention; and 
           [0008]      FIG. 2  is a flow chart that schematically illustrates a method for integer division, in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
       [0009]    Embodiments of the present invention that are described herein provide improved methods and systems for implementing integer divider modules. The divider modules described herein are applicable for any divisor that can be expressed as a sum of two exponential terms of base two, i.e., as DIVISOR=2 m +2 n  wherein exponents m and n are integers, or equivalently DIVISOR=2 n (1+2 p ) wherein p=m−n is also integer. 
         [0010]    For a divisor of this form, the term 1/DIVISOR can be expressed as a binary fraction comprising alternating runs of size p of binary “1”s and “0”s, which is simple to implement in digital hardware. Thus, in some embodiments the divider module identifies the values of n and p, calculates 1/(1+2 p ) using the above-described binary fraction, and then multiplies the result by the dividend and divides by 2 n  to produce the final result. These calculations can be implemented using simple hardware and with small computational complexity. In some embodiments the divider evaluates the binary fraction up to a desired accuracy using a recursive calculation. 
         [0011]    When using the disclosed configurations, the computation time has only a logarithmic dependence on the size of the dividend instead of a linear dependence as in conventional long binary division. Thus, the embodiments presented herein significantly improve the computational efficiency and power consumption of the division operation without adding a significant number of logic circuits. 
       System Description 
       [0012]      FIG. 1  is a block diagram that schematically illustrates a block diagram that schematically illustrates an integer divider module  20 , in accordance with an embodiment of the present invention. The integer divider module in the embodiment shown in  FIG. 1  is configured to divide a dividend denoted A by a DIVISOR denoted B. DIVISOR is an integer of the form 2 m +2 n , which can be further represented as 2 n (1+2 p ), where p=m−n when m&gt;n. 
         [0013]    Such integer divider modules may be used in a variety of applications. Divisors that are sums of powers of two are common in memory allocation tables or memory maps, used for example in data integrity fields (DIF) for protecting data in storage devices. In such an example, data items of size 2 m  may be written into memory, with each data item protected by a signature of size 2 n . The total record size is thus 2 m +2 n . For example, a memory may store 512-byte data words and an 8-byte signature, of which 2 bytes comprise a Cyclic Redundancy Check (CRC). In order to derive the number of rows from the total memory size, or to perform other memory-related calculations, it is necessary to perform division by 2 m +2 n . Thus, the disclosed divider configurations can be embedded in any system or device that accesses memory, e.g., in communication devices such as Network Interface Cards (NICs) or network elements. 
         [0014]    Divider  20  of  FIG. 1  comprises an input interface  24 , which receives dividend A and divisor B. DIVISOR B is the input to an identification (ID) block  28 , which is configured to identify the exponents p and n in the exponent term of the DIVISOR of the form 2 n (1+2 p ). A reciprocal calculation block  32  is configured to calculate the value of 1/(1+2 p ) which then multiplies the dividend A from input interface  24  in a multiplier block  36  to produce an interim result. 
         [0015]    The interim result is then the input to a shifter block  40 , which divides the interim result from multiplier  36  by 2 n  to compute the quotient A/B, where n was obtained from ID block  28 . (Division by 2 n  is typically implemented by applying n shift-right operations.) An output interface  44  outputs the result A/B of the division operation from the divider module. The configuration of integer divider module  20  shown in  FIG. 1  is by way of example, and not by way of limitation of the embodiments of the present invention. In alternative embodiments, any other suitable divider configuration can be used. For example, the integer divider described in the embodiments of the present invention comprises a divisor with sum of two exponentials of base 2. However, in a system or application that performs arithmetic operations in another, non-binary base, the disclosed division techniques can be implemented, mutatis mutandis, for divisors that comprise a sum of two exponentials of any base. 
         [0016]    In some embodiments, divider  20  is used as part of a general divider, which is not limited to divisors that are sums of powers of two. Such a general divider would typically comprise an additional integer divider (not shown in the figures) that performs conventional division. In these embodiments, if the divisor is found to be a sum of powers of two, then the division operation is carried out by divider  20 . Otherwise, the division operation is carried out by the additional divider. In some embodiments, divider  20  and the additional divider may share some common hardware (e.g., shifters, adders and/or registers) so as to reduce the overall hardware size and cost. 
         [0017]    Divider module  20  may be implemented in hardware using digital circuit blocks. Divider module  20  may be further implemented in one or more Application-Specific Integrated Circuits (ASICs) or Field-Programmable Gate Arrays (FPGAs). Additionally or alternatively, some elements of divider module  20  can be implemented using software, or using a combination of hardware and software elements. In some embodiments, divider  20  can be implemented using a programmable processor, which is programmed in software to carry out the functions described herein. The software may be downloaded to the processor in electronic form, over a network, for example, or it may, alternatively or additionally, be provided and/or stored on non-transitory tangible media, such as magnetic, optical, or electronic memory. Additionally or alternatively, the divider may be implemented in a separate packaged integrated circuit. The divider may be integrated in a semiconductor chip, system-on-chip (SoC), system-on-package (SoP), or implemented within any suitable digital system. 
         [0018]      FIG. 2  is a flow chart that schematically illustrates method for integer division using integer divider module  20 , in accordance with an embodiment of the present invention. In a receiving step  100 , divider module  20  receives dividend A and divisor B for performing a division operation. In a finding step  110 , ID block  28  finds the exponents n and p for which the divisor is of the form 2 n (1+2 p ). In a calculating step  120 , block  32  calculates the reciprocal of 1+2 p . In a multiplying step  130 , multiplier  36  multiplies the dividend A by the reciprocal from step  120  to produce an interim result. In a dividing step  140 , shifter block  40  divides the interim result by 2 n . In an outputting step  150 , output interface  44  of divider module  20  outputs the result of the division operation, i.e., the quotient A/B. 
       Mathematical Derivation of Integer Divider Module Configuration 
       [0019]    As explained above, DIVISOR can be written as 2 m +2 n =2 n (1+2 p ). Setting aside the division by 2 n , which is performed later by shifter module  40 , the division operation is equivalent to multiplication by 1/(1+2 p ). The evaluation of 1/(1+2 p ) is carried out by block  32 . 
         [0020]    As will be shown below, the term 1/(1+2 p ) can be written as a binary fraction comprising an infinite pattern of alternating runs of p-ones and p-zeros after the binary point. Table 1 shows this property for several values of p and n=0: 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Binary representation of 1/(1 + 2 p ) 
               
             
          
           
               
                   
                 DIVISOR (Decimal) 
                 p 
                 1/(1 + 2 p ) (Binary) 
               
               
                   
                   
               
               
                   
                 1 + 2 = 1 + 2 1  = 3 
                 1 
                 0.01010101010101010101 . . . 
               
               
                   
                 1 + 4 = 1 + 2 2  = 5 
                 2 
                 0.00110011001100110011 . . . 
               
               
                   
                 1 + 8 = 1 + 2 3  = 9 
                 3 
                 0.000111000111000111 . . . 
               
               
                   
                 1 + 16 = 1 + 2 4  = 17 
                 4 
                 0.0000111100001111 . . . 
               
               
                   
                 1 + 32 = 1 + 2 5  = 33 
                 5 
                 0.00000111110000011111 . . . 
               
               
                   
                   
               
             
          
         
       
     
         [0021]    Multiplication by a binary fraction of this form can be easily realized in hardware using full adders, shifters, and a decrementor, using the derivation below. The term 
         [0000]    
       
         
           
             
               2 
               p 
             
             × 
             
               ( 
               
                 1 
                 DIVISOR 
               
               ) 
             
           
         
       
     
         [0000]    can be expanded as a power series of 1/2 2p .as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       2 
                       p 
                     
                     × 
                     
                       ( 
                       
                         1 
                         DIVISOR 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       { 
                       
                         
                           1 
                           
                             2 
                             p 
                           
                         
                         × 
                         
                           ( 
                           
                             
                               2 
                               p 
                             
                             - 
                             1 
                           
                           ) 
                         
                       
                       } 
                     
                      
                     
                       { 
                       
                         1 
                         + 
                         
                           1 
                           
                             2 
                             
                               2 
                                
                               p 
                             
                           
                         
                         + 
                         
                           1 
                           
                             2 
                             
                               4 
                                
                               p 
                             
                           
                         
                         + 
                         
                           1 
                           
                             2 
                             
                               6 
                                
                               p 
                             
                           
                         
                         + 
                         
                           1 
                           
                             2 
                             
                               8 
                                
                               p 
                             
                           
                         
                         + 
                         
                           1 
                           
                             2 
                             
                               10 
                                
                               p 
                             
                           
                         
                         + 
                         … 
                       
                        
                       
                           
                       
                       } 
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0022]    Equation (1) represents 
         [0000]    
       
         
           
             
               2 
               p 
             
             × 
             
               ( 
               
                 1 
                 DIVISOR 
               
               ) 
             
           
         
       
     
         [0000]    as an alternating pattern of runs of p-ones and p-zeroes after the binary point similar to the series of 1/DIVISOR shown in Table 1. The term 
         [0000]    
       
         
           
             { 
             
               
                 1 
                 
                   2 
                   p 
                 
               
               × 
               
                 ( 
                 
                   
                     2 
                     p 
                   
                   - 
                   1 
                 
                 ) 
               
             
             } 
           
         
       
     
         [0000]    in Equation (1) generates a run of p-binary “1”s after the binary point. Each term in the power series of 
         [0000]    
       
         
           
             1 
             
               2 
               
                 2 
                  
                 p 
               
             
           
         
       
     
         [0000]    concatenates another run of p-“0”s and a run of p-“1”s as shown in Table 2 for several values of p: 
         [0000]    
       
         
               
             
               
               
               
               
             
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Example terms in the power series of Equation (1) 
               
             
          
           
               
                   p 
                 
                   
                     
                       
                         { 
                         
                           
                             1 
                             
                               2 
                               p 
                             
                           
                           × 
                           
                             ( 
                             
                               
                                 2 
                                 p 
                               
                               - 
                               1 
                             
                             ) 
                           
                         
                         } 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           { 
                           
                             
                               1 
                               
                                 2 
                                 p 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   2 
                                   p 
                                 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           } 
                         
                          
                         
                           { 
                           
                             1 
                             + 
                             
                               1 
                               
                                 2 
                                 
                                   2 
                                    
                                   p 
                                 
                               
                             
                           
                           } 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           { 
                           
                             
                               1 
                               
                                 2 
                                 p 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   2 
                                   p 
                                 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           } 
                         
                          
                         
                           { 
                           
                             1 
                             + 
                             
                               1 
                               
                                 2 
                                 
                                   2 
                                    
                                   p 
                                 
                               
                             
                             + 
                             
                               1 
                               
                                 2 
                                 
                                   4 
                                    
                                   p 
                                 
                               
                             
                           
                           } 
                         
                       
                     
                   
                 
               
               
                   
               
             
          
           
               
                 1 
                 0.1 
                 0.101 
                 0.10101 
               
               
                 2 
                 0.11 
                 0.110011 
                 0.1100110011 
               
               
                 3 
                 0.111 
                 0.111000111 
                 0.111000111000111 
               
               
                 4 
                 0.1111 
                 0.111100001111 
                 0.11110000111100001111 
               
               
                 5 
                 0.11111 
                 0.111110000011111 
                 0.1111100000111110000011111 
               
               
                   
               
             
          
         
       
     
         [0023]    In some embodiments, block  32  in divider  20  evaluates a certain number of terms in the power series of 1/2 2p , to match the desired calculation accuracy. As p increases, the number of digits after the binary point increases per term, as shown in Table 2, and the accuracy of representing 
         [0000]    
       
         
           
             
               2 
               p 
             
             × 
             
               ( 
               
                 1 
                 DIVISOR 
               
               ) 
             
           
         
       
     
         [0000]    increases accordingly. 
         [0024]    Stated differently, p increases the number of digits after the binary point for each additional term in the power series such that every term add 2 digits after the binary point for p=1, for example. Similarly, each additional term in the power series adds 8 digits after the binary point for p=4. 
         [0025]    From the hardware standpoint, fewer adders are needed as p increases. Accuracy requirements of the computation determine the number of digits after the binary point that are needed in the finite series, which is on the order of N, the size of the dividend (approximately round_up(log2(DIVIDEND))). 
         [0026]    In some embodiments, for further reduction of hardware cost, power consumption and hardware size, block  32  may compute the power series terms on the right side of equation (1) by performing one or more recursive iteration loops, where i is an integer denoting the iteration index as in the following Equations (2)-(4) for n=0: 
         [0000]    
       
         
           
             
               
                 
                   
                     F 
                     1 
                   
                   = 
                   
                     1 
                     + 
                     
                       1 
                       
                         2 
                         
                           2 
                            
                           p 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           F 
                           2 
                         
                         = 
                           
                          
                         
                           1 
                           + 
                           
                             1 
                             
                               2 
                               
                                 2 
                                  
                                 p 
                               
                             
                           
                           + 
                           
                             1 
                             
                               2 
                               
                                 4 
                                  
                                 p 
                               
                             
                           
                           + 
                           
                             1 
                             
                               2 
                               
                                 6 
                                  
                                 p 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             ( 
                             
                               1 
                               + 
                               
                                 1 
                                 
                                   2 
                                   
                                     2 
                                      
                                     p 
                                   
                                 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               1 
                               
                                 2 
                                 
                                   4 
                                    
                                   p 
                                 
                               
                             
                             × 
                             
                               ( 
                               
                                 1 
                                 + 
                                 
                                   1 
                                   
                                     2 
                                     
                                       2 
                                        
                                       p 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             F 
                             1 
                           
                           + 
                           
                             
                               1 
                               
                                 2 
                                 
                                   4 
                                    
                                   p 
                                 
                               
                             
                             × 
                             
                               F 
                               1 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                     F 
                     
                       i 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       F 
                       i 
                     
                     + 
                     
                       
                         1 
                         
                           2 
                           
                             
                               2 
                               
                                 ( 
                                 
                                   i 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                              
                             p 
                           
                         
                       
                       × 
                       
                         F 
                         i 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0027]    In Equations (2)-(4), F i  is the result of the i th  iteration loop. One iteration loop computation requires one adder circuit and one shifter circuit. Each iteration loop also doubles the number of bits after the binary point. Compared to a conventional long division, the disclosed divider has a significant reduction in the computation time. The computation time is reduced from N iterations for conventional long division to log 2 (N) for the disclosed divider module. The methods for optimizing the integer divider module described above are for conceptual clarity, and not by way of limitation of the embodiments of the present invention. 
         [0028]    In some cases, multiplying DIVIDEND by the reciprocal of 1+2 p  is still computationally complex. In an alternative embodiment, another algorithm can be used to further optimize the integer divider module by expressing the quotient A*(1/B) in a power series expansion and evaluating the quotient using one or more recursive iteration loops in contrast to the embodiment previously described where an additional computation step of the multiplying A with the reciprocal of 1+2 p  (e.g., 1/B) was required to produce the interim quotient result. 
         [0029]    In other words, steps  120  and  130  of the method of  FIG. 2  are not necessarily separate. In the alternative embodiment, block  32  may calculate DIVIDEND/(1+2 p ) instead of 1/(1+2 p ). The recursive calculation of equations (2)-(4) can be modified accordingly. 
         [0030]    In this embodiment, the quotient Q=DIVIDEND/DIVISOR=A*(1/B) may be computed in a recursive iteration loop denoted Q i  for the i th  iteration step given by equations (5) and (6). 
         [0000]    
       
         
           
             
               
                 
                   
                     Q 
                     0 
                   
                   = 
                   
                     
                       
                         1 
                         
                           2 
                           p 
                         
                       
                       × 
                       DIVIDEND 
                     
                     - 
                     
                       
                         1 
                         
                           2 
                           
                             2 
                              
                             p 
                           
                         
                       
                       × 
                       DIVIDEND 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                     Q 
                     
                       i 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       Q 
                       i 
                     
                     + 
                     
                       
                         1 
                         
                           2 
                           
                             
                               2 
                               
                                 ( 
                                 
                                   i 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                              
                             p 
                           
                         
                       
                       × 
                       
                         Q 
                         i 
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where M is an integer and provides the desired accuracy. Equations (5) and (6) are derived from Equations (1)-(4) for n=0 by evaluating a finite number of terms in a power series of 1/2 2p . However, the iteration loop computes the quotient Q by bundling DIVIDEND as in Equation (5) into the iteration loop. This eliminates the extra multiplication step of DIVIDEND with the reciprocal of 1+2 p  as described in the previous embodiment. 
         [0031]    After i=M iterations in the recursive quotient Q computation, M iterations are used to match the desired calculation accuracy. Each iteration step can be realized using a single shifter and a single adder/subtractor. Stated differently, in the embodiment presented here, quotient A*(1/B) is directly computed in an iteration loop to directly produce the interim result without an additional multiplication computation step of A by 1/B=(1/DIVISOR) as in the embodiment described in equations (1)-(4), which makes the computation of Q much simpler and more efficient. 
         [0032]    It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and sub-combinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art. Documents incorporated by reference in the present patent application are to be considered an integral part of the application except that to the extent any terms are defined in these incorporated documents in a manner that conflicts with the definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.