Generating partial sums

A method for generating partial sums from at least four multiple-digit sequences in a computing device includes partitioning the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences. The method also includes generating at least one auxiliary set of multiple-digit sequences. The auxiliary set includes digits copied from respective digit positions of multiple-digit sequences in the first and second sets. The method further includes replacing the copied digits in the first and second sets by zeros to obtain a first altered set and a second altered set, respectively, of multiple-digit sequences each comprising multiple segments separated by the replaced zeros. The method also includes generating at least a first partial sum by adding the multiple-digit sequences in at least one auxiliary set and generating at least a second and third partial sums by adding the multiple-digit sequences in the first altered set and second altered set, respectively.

TECHNICAL FIELD

This description relates to generating partial sums, e.g., in adders used in computer hardware.

BACKGROUND

The carry operation in different fast adders are handled in a number of ways. In general, when numbers of a given length are added together, the sum may be of length greater than the individual length of each number. Consider adding two binary numbers 11+11. Addition of the right most bits (the lowest order bit position), i.e. 1+1 results in 10. While the 0 is stored in the corresponding bit position of the result, the 1 is referred to as a ‘carry’ which must be added to the sum of the bits in the next higher bit position. In this example, the 1 is added to 1+1, i.e., the sum of the digits in the next bit position, giving the final result of 110. In computer arithmetic, accounting for the carry in the next higher position is known as propagation of carry.

Various designs of fast adders could be differentiated based on their handling of the carry propagation. For example, some adders divide the bits of numbers to be added into multiple segments that are added in parallel, and then combine the sums of the segments to generate a final result. Each segment can consist of a single bit or multiple bits. The carry-select adder is an example of such an adder. In this adder, the carry from the most significant bit of one segment is propagated to the least significant bit of the next most significant segment. For example, the circuitry for adding a given segment in the carry select adder generally consists of two adders and one multiplexer. Adding two n-bit numbers with a carry select adder is done with two adders for each segment in order to perform the calculation twice, one time with the assumption of the carry being 0 and the other assuming 1. After the two results are calculated the correct sum, as well as the correct carry, are then selected with the multiplexer once the correct carry is known. This is repeated for every segment, with the correct carry result being propagated from one segment to the next. While performance can be increased by performing the two sums for each segment in parallel (e.g., dividing the time approximately by the number of segments), there may also be a cost since the addition for each segment is performed twice (e.g., a cost in area on a chip for the extra adder for each segment). Also, additional time is needed to propagate the carry result among the segments.

When adding two or more numbers of n-bits, the carry save adder outputs two n-bit numbers, one which is a sequence of partial sum bits and another which is a sequence of carry bits. For example, consider the binary sum 1101+1111. Carry-save arithmetic works by abandoning the binary notation while still working to base 2. It computes the sum digit by digit, as:

As seen above, the carry save adder produces a result that has to be converted back into binary and this means that carries have to propagate from right to left. The carry-save adder is typically used in adding more than two numbers, i.e. as a multi-operand adder, to justify the cost of converting the saved non-binary carries to binary, and finally adding them to the computed sum to get the final result.

In some cases a carry look ahead adder may be used to reduce the delay associated with a carry save adder. In principle the delay can be reduced so that it is proportional to log(b) where b is the number of bits in each summand, but for large numbers this is no longer the case, because even when carry look-ahead is implemented, the distances that signals have to travel on the chip increases proportionally with b, and propagation delays increase at the same rate.

SUMMARY

In one aspect, a method for generating partial sums from at least four multiple-digit sequences in a computing device includes partitioning the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences. The method also includes generating at least one auxiliary set of multiple-digit sequences. The auxiliary set includes digits copied from respective digit positions of multiple-digit sequences in the first and second sets. The method further includes replacing the copied digits in the first and second sets by zeros to obtain a first altered set and a second altered set, respectively, of multiple-digit sequences each comprising multiple segments separated by the replaced zeros. The method also includes generating at least a first partial sum by adding the multiple-digit sequences in at least one auxiliary set and generating at least a second and third partial sums by adding the multiple-digit sequences in the first altered set and second altered set, respectively.

In another aspect, a method of generating partial sums from at least four multiple-digit sequences in a computing device includes partitioning the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences and generating at least a first partial sum and a second partial sum. The first and second partial sums are generated by adding respective segments of the multiple-digit sequences in the first set and second set, respectively, with two or more sets of segments of multiple-digit sequences being added in parallel. The method may also include generating at least one auxiliary set of multiple-digit sequences that include digits derived from respective carry results from additions of respective segments of the multiple-digit sequences in the first set and second sets.

In another aspect, a system for generating partial sums from at least four multiple-digit sequences in a computing device includes a first circuitry and a second circuitry. The first circuitry is configured to partition the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences and generate at least one auxiliary set of multiple-digit sequences that include digits copied from respective digit positions in the first and second sets. The first circuitry is further configured to replace the copied digits in the first and second sets by zeros to obtain a first altered set and a second altered set, respectively, of multiple-digit sequences each comprising multiple segments separated by the replaced zeros. The second circuitry is configured to generate at least a first partial sum by adding the multiple-digit sequences in the at least one auxiliary set. The second circuitry is also configured to generate at least a second partial sum and a third partial sum by adding the multiple-digit sequences in the first altered set and second altered set, respectively.

In another aspect, a system of generating partial sums from at least four multiple-digit sequences includes a first circuitry and a second circuitry. The first circuitry is configured to partition the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences. The second circuitry is configured to generate at least a first partial sum and a second partial sum by adding respective segments of the multiple-digit sequences in the first set and second set, respectively, with two or more sets of segments of the multiple-digit sequences being added in parallel.

In another aspect, a computer readable medium for storing a computer program for generating partial sums from at least four multiple-digit sequences is described. The computer program includes instructions for causing a computer system to partition the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences and generate at least one auxiliary set of multiple-digit sequences that include digits copied from respective digit positions in the first and second sets. The computer program also includes instructions for causing a computer system to replace the copied digits in the first and second sets by zeros to obtain a first altered set and a second altered set, respectively, of multiple-digit sequences each comprising multiple segments separated by the replaced zeros. The computer program also includes instructions for causing a computer system to generate at least a first partial sum by adding the multiple-digit sequences in at least one auxiliary set and generate at least a second and third partial sums by adding the multiple-digit sequences in the first altered set and the second altered set, respectively.

In another aspect, a computer readable medium for storing a computer program for generating partial sums from at least four multiple-digit sequences is described. The computer program includes instructions for causing a computer system to partition the multiple-digit sequences into at least a first set of multiple-digit sequences and a second set of multiple-digit sequences and generate at least first and second partial sums by adding respective segments of the multiple-digit sequences in the first and second sets, respectively, with two or more sets of segments of multiple-digit sequences being added in parallel. The computer program also includes instructions for causing a computer system to generate at least one auxiliary set of multiple-digit sequences that include digits derived from respective carry results from additions of respective segments of the multiple-digit sequences in the first and second sets.

Implementations may include one or more of the following. Generating the at least one auxiliary set may include copying digits from a first group of digit positions of each multiple-digit sequence in the first set and a second group of digit positions of each multiple-digit sequence in the second set to corresponding digit positions in a first auxiliary set where each of the digit positions in the first group is different from the digit positions in the second group. Generating the auxiliary set may further include setting a third group of digit positions in the first auxiliary set to zero, the third group corresponding to digit positions not included in either of the first and second groups. Generating the auxiliary sets may include copying digits from a first group of digit positions in the first set to corresponding digit positions in a first auxiliary set, and copying digits from a second group of digit positions in the second set to corresponding digit positions in a second auxiliary set. Adding the multiple-digit sequences in each of the first and second altered sets and the auxiliary set may include adding different segments of the multiple-digit sequences in parallel. The first set may have substantially the same number of multiple-digit sequences as the second set. The method may further include summing the partial sums. The multiple-digit sequences may be binary numbers. One or more zeros may be appended at the beginning or end of one or more of the multiple-digit sequences in the first and second sets. The digit positions in the first group may be periodic with a first period, the digit positions in the second group may be periodic with a second period and in some cases, the first period may be equal to the second period. Generating the first auxiliary set may further include setting a third group of digit positions in the first auxiliary set to zero, the third group corresponding to the digit positions not included in either of the first and second groups. In some cases, the digit positions in the third group are periodic with a third period. The third period equal to at least one of the first period and the second period. Each of the first and second groups of digit positions may include at least two digit positions that are consecutive. The third group of digit positions may also include at least two digit positions that are consecutive. Each of the sets of multiple-digit sequences may include at least two multiple-digit sequences and in some cases three or more multiple-digit sequences. The multiple-digit sequences may be obtained via a multiplication of two numbers or two matrices. The multiplication may be a floating point multiplication or a fixed point multiplication. the multiple-digit sequences may be obtained via a computation of an inner product or an outer product of two vectors. The digits derived from the respective carry results from additions of the respective segments in the first and second sets occupy bit positions in the auxiliary set corresponding to bit positions of the respective carry results. The bit positions of the respective carry results from additions of the respective segments in the first set may be different from the bit positions of the respective carry results from additions of the respective segments in the second set. The method may further include adding the auxiliary set and the first and second partial sums. At least one of the first circuitry and the second circuitry may comprise a processor. The second circuitry may further comprise an adder. A storage may store the first, second and third partial sums. The storage may be further configured to store the multiple-digit sequences. The first circuitry may be further configured to copy digits from a first group of digit positions of each multiple-digit sequence in the first set and a second group of digit positions of each multiple-digit sequence in the second set to corresponding digit positions in a first auxiliary set. Each of the digit positions in the first group is different from the digit positions in the second group. The first circuitry may be further configured to copy digits from a first group of digit positions of each multiple-digit sequence in the first set and a second group of digit positions of each multiple-digit sequence in the second set to corresponding digit positions in a first auxiliary set and a second auxiliary set, respectively. The second circuitry may be further configured to add the partial sums. Digits derived from the respective carry results from additions of the respective segments in the first and second sets may occupy bit positions in the auxiliary set corresponding to the bit positions of the respective carry results. The bit positions of the respective carry results from additions of the respective segments in the first set may be different from the bit positions of the respective carry results from additions of the respective segments in the second set. The second circuitry may be further configured to add the auxiliary set and the first and second partial sums.

Among the many advantages of the invention (some of which may be achieved only in some of its various aspects and implementations) are the following.

The need to propagate the carry between segments of a sum performed in parallel can be avoided. Patterns of gaps of zeros are created between segments in each of the summands by moving certain bits into auxiliary sets of summands (called “auxiliary arrays”). In some implementations, these bits can be moved into the auxiliary array directly as soon as the bits become available. In some implementations, the pattern of the moved bits is such that the auxiliary array is filled without overlaps and in some cases, with gaps of zeros. The gaps of zeros convert a sum of numbers with an arbitrarily large number of bits to independent parallel additions of pairs of shorter segments. Any carry bits resulting from the addition of pairs of segments, are trapped in the gaps. This allows for fast parallel addition that is independent of the number of bits of the summands, and instead depend only on the number of bits in the segments added in parallel. For example, the time needed to propagate the carry from one segment to the next can be avoided. For example, the time needed to propagate the carry from one segment to the next can be avoided. In other words, the adders described herein are based on restructuring the summands such that gaps of zeros are created. These gaps arrest the propagation of the carries that result from adding the segments between the gaps. The restructuring does not require any knowledge of the bits to be moved or any checks or evaluations of the given summands. The pattern of the moved bits may be decided in advance as part of the algorithm and built into the structure of the adder. As soon as a summand is available, the restructuring can be done essentially instantaneously with the need to necessarily perform checks, valuations or tests. Therefore, no additional time is needed. The addition of the short segments can be computed in parallel.

Compared to the carry-select adder, an area savings of approximately 25% and time savings of approximately 50% can be achieved in some implementations.

In the carry-save adder the carry bits are accumulated separately, allowing fast parallel addition, while adding the sum of the carries at the end. Adders described in this application are able to avoid carry propagation beyond a few bits (for example, within the short segments). In some implementations, the time needed to add N numbers of b bits each satisfies:
TN(b)=alog2N+f(b)
where the dependence on the number of bits is additive and is affected only by a small number of residual additions at the end. For large N even this dependence can be ignored and the time to add N numbers of b bits is proportional to the logarithm of N. Since the number of residual additions at the end is small, a very fast parallel adder can be used to compute those additions.

DETAILED DESCRIPTION

There are a great many possible implementations of the invention, too many to describe herein. Some possible implementations that are presently preferred are described below. It cannot be emphasized too strongly, however, that these are descriptions of implementations of the invention, and not descriptions of the invention, which is not limited to the detailed implementations described in this section but is described in broader terms in the claims.

FIG. 1is a schematic diagram of a computer system100. The system100can be used for the operations described in association with any of the computer-implemented methods described herein, according to one implementation. The system100includes a processor110, a memory120, a storage device130, and an input/output device140. Each of the components110,120,130, and140are interconnected using a system bus150. The processor110is capable of processing instructions for execution within the system100. In one implementation, the processor110is a single-threaded processor. In another implementation, the processor110is a multi-threaded processor. The processor110is capable of processing instructions stored in the memory120or on the storage device130to display graphical information for a user interface on the input/output device140.

The memory120stores information within the system100. In some implementations, the memory120is a computer-readable medium. The memory120can include volatile memory and/or non-volatile memory.

The storage device130is capable of providing mass storage for the system100. In one implementation, the storage device130is a computer-readable medium. In various different implementations, the storage device130may be a floppy disk device, a hard disk device, an optical disk device, or a tape device.

The input/output device140provides input/output operations for the system100. In some implementations, the input/output device140includes a keyboard and/or pointing device. In some implementations, the input/output device140includes a display unit for displaying graphical user interfaces.

The processor110carries out instructions related to a computer program. The processor110may include hardware such as logic gates, adders, multipliers and counters. The processor110may further include a separate arithmetic logic unit (ALU) that performs arithmetic and logical operations. The adders may include any number and type of half adders, full adders and multiple bit adders. The adder circuits may be arranged to realize more complex adders such as ripple carry adders, carry look-ahead adders, carry skip adders, conditional sum adders, carry complete adders or adders such as described in this application.

In general, hardware in a processor110is configured to add numbers of a given maximum length. This maximum length may be expressed in digits, such as binary digits called bits, for example, 4 bit adder, 16 bit adder, 32 bit adder etc. These adders may be used to add numbers that are greater than the maximum length of the adder. For example, a processor that has only 16 bit adders may need to add two or more 128 bit numbers. In such cases, the long additions are partitioned into several shorter additions involving smaller groups of bits, called segments, and the final answer is obtained by the summing the intermediate segments. A number of sums of the segments may be computed in parallel or sequentially in accordance with the hardware capabilities of the processor.

Referring now toFIG. 2, a flowchart depicts example operations followed in adding longer numbers than allowed by the hardware. Operations include partitioning210the long addition into multiple short additions. The partitioning is done in accordance with the available hardware. For example, if two 32 bit numbers are to be added using 4 bit adders, the long addition is partitioned into 8 separate 4 bit additions. In another example, the 32 bit addition may be partitioned into 4 separate 4 bit additions and 2 separate 8 bit additions if the available hardware allows the computation of such additions. Operations further include computing220the short additions of the segments separately. The shorter additions may be computed in parallel, in sequence or as a combination of parallel and in sequence depending on the hardware available to compute the shorter additions. The results of the short additions are combined appropriately to obtain partial sums. Operations also include adding230the partial sums together. In some cases, the operations210and220may be repeated one or more times to add the results of the shorter additions together.

Referring now toFIG. 3A, a schematic diagram describes adding multiple numbers called summands. In this example, each summand is a long sequences of digits. In the following part of the document, we refer to the digits as binary digits or bits.

However, the digits may be of any base such as decimal, octal, hexadecimal etc. The summands to be added together are represented as the set301. In this example, the set301includes 6 numbers each of which is 32 bits in length. The numbers are denoted as310a-310f. The least significant bit of each number is denoted as b1while the most significant bit is denoted as bn. In this example, since the numbers are 32 bit long, n=32.

In this example, the 6 numbers to be added together are divided into 3 different pairs302a,302band302c(302in general). The pair302aincludes the numbers310aand310b, the pair302bincludes the numbers310cand310dand so on. In this example, the ordering is chosen only for illustrative purposes. In general, any two numbers from the set301may be chosen to form a pair302. In this example, it is assumed that the available hardware allows for adding two 3 bit numbers at a time to produce up to a 4 bit result. The extra bit in the result allows for the carry that may need to be added to the least significant bit of the next most significant bits. For example, consider the addition of the numbers310aand310bin the set301. If the segments including bits b2, b3and b4were added using a 3 bit adder, the sum may include a carry that would have to be added to the least significant bit of the sum of the segments including bits b5, b6and b7. The next sum of segments would produce another carry that would have to be added to the least significant bit of the following sum of segments. In this way, the carry of each segment would have to be propagated to the next all the way up to the most significant bit bnof the numbers being added.

To avoid the need to propagate the carry from one segment to another, all the way to the most significant bits, in some implementations, certain bit positions in each of the numbers being added are replaced by zeros and the replaced bits are moved to a corresponding bit position in an auxiliary array303. In this example, bits corresponding to bit positions b1, b5, b9etc, from the pair302a, are replaced by gaps325of zeros and the replaced bits are moved to corresponding bit positions in a pair of numbers represented by the auxiliary array303. Similarly, bits corresponding to bit positions b6, b10, b13etc, from the pair302b, are replaced by gaps325of zeros and the replaced bits are moved to corresponding bit positions in the auxiliary array303. Bits from the pair302care also moved to the auxiliary array in a similar fashion. The pattern of the bits in the different pairs is staggered, such that the auxiliary arrays are filled without overlaps. In other words, the bit positions moved from the pair302aare different from the bit positions moved from each of the pairs302band302c. When the pairs302are altered in the above fashion, the sum for each segment can be calculated without propagating the carry to the next segment. For example, when the bits b2, b3and b4are added using a 3 bit adder, the carry that might result is at bit position b5. Since the numbers310aand310bhave been altered to have zeros at that location, the bit position b5of the resulting partial sum will be zero if there is no carry from the addition of bits in bit position b4and will be one if there is a carry from the addition of bits in bit position b4. In either case, the carry is not propagated to bit position b6. The bits that were replaced at these bit locations corresponding to bit position b5are not ignored in the final sum since they are added together in the auxiliary array. For example, bits corresponding to b5from the pair302a, b6from the pair302bandb7from the pair302care added together at the corresponding locations in the auxiliary array. Since the result of summing the numbers in the auxiliary array are later added to the results of summing the numbers in the pairs302a-302c, manipulating the bit positions, as described in the above example, does not affect the final sum. In some implementations, the auxiliary array may also have one or more gaps325of zeros to arrest one or more carries resulting from sums of different segments. In this example, gaps325are introduced at b4, b8, b12etc. in the auxiliary array, to arrest the carry resulting from summing the bits at b1-b3, b5-b7and b9-b11, respectively. Adders using these techniques may therefore be referred to as carry-arrest adders.

The result of summing the pair of numbers302ais denoted as a partial sum320a. Similarly, the result corresponding to summing the pairs302b,302cand the auxiliary array pair303are denoted as partial sums320b,320cand320d, respectively. In some implementations, the results320a-320dare one bit longer in order to accommodate a carry from the addition of the most significant bits. For example, when the bit positions bn, bn−1and bn−2in the pairs302aare added, the result may have a carry that needs to be accommodated. In some implementations, when the bit positions corresponding to the most significant bit in the pair has gaps325of zeros (e.g., as in the auxiliary array pair303in the above example), the result will not have an extra carry.

The numbers or bit sequences320a-320dare partial sums resulting from adding the numbers310a-310fthat can be added together to obtain the final sum. The operations described in the above example reduce the number of long sequences to be added from 6 to 4 by performing the short additions as described above. In some implementations, two or more of the additions of the segments of a given pair of bit sequences may be done in parallel thereby reducing the time required for the additions.

The above example shows that the gaps325are introduced in each pair of summands302a-302cand303with a periodicity of 4. It should be noted that in some implementations the gaps325may also be aperiodic. In the above example, the gaps may be distributed in any way as long as the corresponding bit positions in one pair do not overlap with bit positions of gaps introduced in any of the other pairs. For example, in some implementations, the periodicity of gaps in one pair of summands302amay be different from the periodicity of a different pair of summands302bor auxiliary array303. The gaps may be periodic in one pair of summands302bwhile aperiodic in one or more different pairs of summands302cor auxiliary array303.

In some implementations, the above scheme may be used to add at least 4 long sequences of bits. If four n bit sequences301are used in the above scheme, the number of n+1 (or n) bit sequences or partial sums obtained will be 3. In general, the above scheme can be used repetitively until 3 partial sums are obtained. The last 3 partial sums may then be added together using any fast adder.

The above scheme may also be illustrated as follows. Consider adding together N summands of b bits each. In some implementations, the set of N summands is divided into N/(2r) sets of 2r summands each and each set is grouped into pairs denoted by (xi, yi), where i=0, 1, . . . r−1.

For every pair (xi, yi) a set of bit positions is replaced by gaps325of zeros. In some implementations, every (r+1)th bit in each pair may be replaced by the gaps325of zeros. The resultant altered pair302of numbers may be denoted by (xi′, yi′), where i=0, 1, . . . , r−1. The bits replaced by gaps325of zeros are placed in corresponding bit positions in an auxiliary array, which in this example corresponds to the auxiliary array pair303of numbers (xr, yr). In some implementations, the bit positions replaced in one pair do not overlap with bit positions replaced in any other pair. For example, the starting points of the gaps325for each pair may be shifted by one more bit for every pair such that the replaced bits are interlaced in the auxiliary array pair303without overlapping and placed one next to the other. The gaps325may also be introduced in the auxiliary array pair303. In the example shown inFIG. 3A, the periodicity of the gaps325in the auxiliary array pair is same as the periodicity of the gaps325in each of the pairs302a,302band302c. In such a case, every (r+1)th bit in the auxiliary array pair303is left unoccupied by the transfer. By leaving selected bit positions unoccupied, it is implied that gaps325of zeros exist at those bit positions. The resulting altered pairs302along with the auxiliary array pair303may be represented in matrix form as:

Only 9 of the least significant bits have been shown in the above equation, where x0(j) represents the jth bit position of the number x0. In some implementations, the above matrix will have only one pair of gaps325of zeros in each column. The r+1 bit segments of the pairs302and the auxiliary array pair303may be added using any parallel adders. For example, each pair302could be added by a parallel adder that adds each segment of r bit numbers (each having a zero in the gap corresponding to the (r+1)th bit position, yielding an r+1 bit sum), with the carry (if any) arrested in the gap created between each two adjacent segments. In this example, the total time to add two b bit numbers is substantially same as the time τrof adding two r bit numbers. In some implementations, this may be solely dependent on the method used to add the two r bit numbers. The auxiliary array pair303of numbers may also be added r bits at a time. In such a case, the 2r numbers in a given set are replaced by r+1 numbers of b+1 bits each. In other words, in this example, the original N=N0summands of b bits each are replaced by N1summands of b+1 bits each in τrtime, where:

N1=N0·r+12⁢r
In some implementations, the above steps are repeated for the N1summands. For each step Nithat the process is repeated, the number of summands in the next step becomes:

Proceeding for l steps in the above example, the number of summands becomes:

Nl=N0·(r+12⁢r)l
each of which are of length b+1 bits. In some implementations, the repetitions are stopped when the condition

Nl=N0·(r+12⁢r)l=r+1
is fulfilled. In such cases, the remaining summands representing partial sums from the previous step are added using any available algorithm and/or adder. The number of times that the above described steps may be repeated in the above example is given by:

Assuming that the remaining r+1 numbers in the above case are added together using for example, an adder tree, the total time τNneeded to add the N numbers is given by:

τN=l⁢⁢τr+τb+l⁢log⁡(r+1)=(1+log⁢Nr-1log⁢2⁢rr+1)⁢τr+τb+l⁢log⁡(r+1)
where τb+1is the time needed to add numbers of b+1 bits each. In some implementations, the time is increased by a small amount to accommodate the extra bit per level in the final adder tree, to an average of:

The scheme of addition described above with respect toFIG. 3Ais further illustrated by way of an example. The following example is shown using decimal digits. The concepts described can be extended to any other base.

Consider adding the following numbers:

1234+5678+9123+4567+8912+3456. The result of the addition is 32970. The scheme of adding numbers described above can be used to perform this addition as follows:

The partial sum in the above examples can be added together as:

6900+13610+11068+1392=32970, which is the expected result. As mentioned above, in some implementations, another round of addition using another auxiliary pair may be used to add the partial sums together.

Consider the addition of the following decimal numbers:564378392275491778564352987111785487352454676978758663439872326636478977677755354769867243523221

In this example, r=3 is used along with periodic gaps in the pairs. Therefore every fourth bit, with staggered beginnings in the six decimal numbers, is moved to the auxiliary pair. The six decimal numbers are therefore partitioned into three pairs of additions with an extra addition due to an auxiliary pair. The four pair of numbers can be added using parallel addition of three bit numbers, without the need for any carry propagation. The resultant partial sums may again be grouped into sets of six numbers and the process repeated until two numbers are left. The addition of the last two partial sums may then be computed using non-redundant binary parallel adders. The process is partially depicted using the following notations:

In some implementations, the auxiliary array may not have gaps of zeros. Referring now toFIG. 3B, such a scheme for adding multiple long sequences of bits is shown. The auxiliary array pair303in such cases does not have the gaps of zeros. In some implementations, the numbers in the auxiliary array are then added using any available adder and/or algorithms. Adders such as the one shown inFIG. 3Bare also referred to as a carry arrest adder with full auxiliary array. In some implementations, such adders are used for adding at least 6 numbers that are reduced to 4 after a first pass.

Referring now toFIG. 3C, another example of adding multiple long sequences of bits is shown. In this example, 14 summands, each 32 bit long, are added to each other using a substantially similar scheme described with respect toFIG. 3A. The number of summands is reduced to 8 from the original 14 after a first pass. In some implementations, the carry arrest adding method may be applied again until only a few partial sums, say 4, are left. These may then be added using any adder. In the example ofFIG. 3C, the reduction from 14, 32-bit numbers to 8, 33-bit numbers requires approximately the time to add 2, 7-bit numbers. Moreover, this is independent of the original number of bits (32 in this case), and depends only on the size of the segments of bits separated with gaps (7 in this case). Therefore, the speed is essentially decided by the addition time of the short adders, 7 bits in this case, and not the length of the original summands (32 bits in this case).

In the above example, the number of 32 bit summands is N=14. Since 7 bits are added at a time, r=7. If the reduction from 14 to 8 is applied until 8 numbers remain, then l steps are needed, where:

l=log2⁢N-3log2⁡(7/4)≅1.2386⁢log2⁢N-3.7157
For N=14, this gives l=1, which is what is expected since the reduction from 14 summands to 8 is achieved in a single pass or step. In general, in the above example, each of the l steps requires the time to add two 7 bit numbers only. The remaining number of summands, 8 in this case, can be further reduced using another carry arrest adder. However, if the remaining 8 summands are added via an adder tree, the total time needed is:
τN=T(7)(1.2386 log2N−3.7157)+3T(b+logN−3)
In comparison, the time required to add the N original summands using an adder tree is given by:

The time savings by using a carry arrest adder may be represented as a function of N and b as:

η⁡(N,b)≡1-τNTN⁡(b)
where η=0 would signify no savings and η=1 would signify that the carry arrest adder takes zero time to add the N, b bit summands. Using this in the above example, η(N,b) can be approximated as:

In some cases, it is possible to model different adder types by the equation:
T(b)=ζbα, 0<α<1
where α=1 indicates a class of parallel adders, while α<1 indicates an adder with increased area to achieve higher speed (such as the carry-select adder). Using this in the above example:

η⁡(N,b)≅1-1.2386⁢(7)α(b+log⁢⁢N2)α=1-1.2386⁢(7b+log⁢⁢N2)α
which for relatively large values of N, may be approximated as:

η⁡(N)≅1-1.2386⁢(14log⁢⁢N)α
which in turn signifies that the savings due to using a carry arrest adder is independent of the number of bits b.

In some implementations, more than a pair of numbers may be added in a given partial sum. Referring now toFIG. 4A, an exemplary scheme for adding multiple long bit sequences shows generating altered sets402a-402d(402in general) from initial summands401, and adding 4 summands in each of the altered sets402and the auxiliary set403to compute the partial sums404a-404e(404in general). In this example, since 4 numbers are added at a time, the gaps425of zeros introduced in the sets402are configured to accommodate 2 bit carries. In general, the number of bits in the carry depends on how many numbers are added together in each partial sum. The adders implemented as per the scheme shown inFIG. 4Amay be referred to as block carry arrest adders. As described above with respect toFIGS. 3A-3C, the block gaps425may be distributed over non-overlapping bit positions in different sets such that the corresponding bits positions of the auxiliary set are filled without overlaps. In some implementations, the bit positions corresponding to the block gaps425from one set (for example402a) are different from the bit positions corresponding to the block gaps from another set (for example402b). The block carry arrest adder is a generalization of the carry-arrest adder discussed above. In some implementations, the block carry arrest adder allows more than two numbers to be added and uses wider gaps425.

Referring now toFIG. 4B, another example of a block carry arrest adder is shown. In this example, the summands401are divided into two sets401aand401b. A first altered set402ais formed from the set401aby replacing some bit positions in the summands of401aby gaps of zeros. For example, the bits at bit positions b3and b4, among others, in set402aare replaced by zeros. This is done to accommodate the possible 2 bit carry that may result from adding the four 2 bit numbers at bit positions b1and b2of set402a. The replaced bits are moved to a first auxiliary set402b. Zeros are filled in at the bit positions in402bthat correspond to the bit positions in402anot replaced by zeros. Continuing with the above example, the bit positions b1and b2in the set402bwill be filled by zeros. This can be viewed as partitioning a set of N summands of b bits each into two sets of N summands of b bits each (an altered set and an auxiliary set) with zeros introduced in the summands. The bit positions where the zeros are introduced in the first altered set402aare different from the bit positions where the zeros are introduced in the first auxiliary set402b. As described above, the gaps of zeros are able to arrest the carries of several shorter additions that result from such partitioning of the summands. In the above example, the zeros are introduced in set402asuch that the possible carry of one or two bits from the sum of the four 2 bit summands in bit positions b1and b2are arrested in the gaps of zeros created at bit positions b3and b4. The result of the sum is then stored at bit positions b4, b3, b2and b1of the partial sum404a.

The summands in the set401bare also divided into two sets, a second altered set402cand a second auxiliary set402d, following essentially the same methodology as described with respect to set401a. In the example shown inFIG. 4B, the bit positions where zeros are introduced in set402care the same as the bit positions where zeros are introduced in set402a. Correspondingly, the bit positions of zeros in set402dmatch those of set402b. In this example, since there are two separate auxiliary sets, one for each altered set, there is no requirement that the bits positions of the auxiliary sets are filled without overlaps. In some implementations, the bit positions where zeros are introduced in sets402cand402dmay be chosen independently of the distribution of zeros in the sets402aand402b.

As seen from the example inFIG. 4B, the shorter addition of four 2 bit segments can be carried out in parallel. The bits resulting from the short additions in set402aare stored in the partial sum404a. The bits resulting from the short additions in sets402b,402cand402dare stored in the partial sums404b,404cand404d, respectively. The partial sums404a-404dmay then be added together using a carry arrest adder or any other multi-operand adder.

Even though the above example is shown for four sets402each having multiple segments of four 2 bit numbers, this example should not be considered as limiting in any sense. The summands401may be partitioned into sets402of any number of summands. The sets402may be further partitioned into shorter additions of any number of bits.

The example shown inFIG. 4Bmay be represented using equations as follows. Consider the addition of N positive integers of b bits each. These numbers are partitioned into s sets, each containing 2rnumbers of r bits each such that:

s=N⁢br⁢⁢2r
In the above example, N=8 summands are partitioned into s sets each containing numbers of 4 bits each. Therefore, in this case, r=2 and

s=8·322×4=32
Indeed, the number of 2 bit short additions involving 4 numbers each that need to be performed in the above example is 32. The numbers in each set are added. When 2rnumbers of r bits each are added, we get one number of 2r bits. Each (N/2r) numbers of b bits could be reduced into just two numbers of b+r bits each after adding each 2rnumbers of r bits, and merging the resulting 2r bit numbers into the partial sums404a-404d. This results in a total of N1numbers of b+r bits each, where

N1=2·N02r=N02r=N02r-1,N0=N
This is achieved in the time needed to add 2rnumbers of r bits each. The above steps are then repeated l times until two numbers of b+rl bits each remain, where

Nl=N2l⁡(r-1)=2
Therefore, in this example

l=log⁢⁢N-1r-1
Also, the total time to add all N numbers of b bits is therefore given by:
TN(b)=lτr+T2(b+rl)
where τris the time needed to add 2rnumbers of r bits each and T2(b+rl) is the time needed to add the last two numbers of b+rl bits each. In some implementations, for each N, there is an optimal value for r, which depends on N, b, the type of adder used to add 2rnumbers of r bits each and the adder used to add the last two numbers.

In some implementations, each number is divided into r bit numbers and grouped, in general, into sets of L numbers. Each set, when added together, results in a number of r+log L bits. Each L numbers of the given N are therefore merged after these additions into numbers of r+log L bits each and results in N1numbers, where

The above additions are computed in the time needed to add L numbers of r bits each. This time is defined as TL(r) which may depend on the form of adder used. In some implementations, the process may be repeated l times until only two numbers have to be added. Therefore:

Nl=N((1+log⁢⁢LL)L)l=2
The number of steps l is therefore given by:

l=log⁢⁢N-1log⁢⁢L-log⁡(1+log⁢⁢Lr)
The total time of computation is given by:
τN=lτL(r)+T2(b+logN−1)
Where T2(b) is the time needed to add two numbers of b bits each, and in some implementations depends on the type of adder used.

In some implementations, the block carry arrest adder has the advantage of processing blocks independently. In some implementations, the adders described herein may be used for parallel and multi-core processing. In some implementations, each block of r bit numbers could be computed using any multi-operand adder, including the block-carry-arrest adder again, or any regular non-redundant adder. In some implementations, the carry arrest adders and the block carry arrest adders may be used in combination. In such implementations, a switch between a carry arrest adder and a block carry arrest adder may be made at any stage of computation.

In some implementations, the carry arrest adder (or the block carry arrest adder) as described above may be used in a multiplication.FIG. 5shows an example of how multiple bit numbers obtained in an intermediate step of a multi-bit multiplication may be added together. Particularly, in parallel multipliers, the partial products501to be added for the final result are shifted or staggered with respect to each other. In some implementations, the VLSI of a parallel multiplier could be generalized to implement a wide class of functions by programming its partial product array (PPA) to accept arbitrarily defined numbers. Such partial products may be added with each other using the carry arrest adder (or block carry arrest adders) by introducing gaps of zeros in the set502and moving the replaced bits to auxiliary sets503. In the example shown inFIG. 5, 4 auxiliary sets are created for adding 16 partial products501resulting from a 16×16 bit multiplier. In this example, simultaneous additions of 4 bit numbers are needed with no carry propagation across the gaps replace the addition of 16 numbers501by 10 numbers504. The resulting 10 numbers504may be added using the carry arrest adder (or the block carry arrest adder) a second time or may be added using any other adder. In this example, the resulting 10 numbers are obtained in a time needed to add two 4-bit numbers. Therefore, the time taken depends only on the length of the short segments (4 in this case), and not on the original number of bits (16 in this case). Therefore, the larger the number of bits in the partial products501, the higher the relative increase in speed.

In some implementations, the multiplication may be a part of one of the following algorithms and/or functions: a divide and conquer algorithm, a vector multiplication, a matrix multiplication, a calculation of inner or outer product of vectors and any other operation that requires fast multi-operand adders. In some implementations, the multiplications are in fixed point arithmetic. In some implementations, the multiplications may be in floating point arithmetic. In such cases, the multiplication is computed using carry arrest (or block carry arrest) adder by computing the multiplication of the mantissas of the two multiplicands in fixed-point form, then adding the exponents, and finally performing final adjustment to put the mantissa in the proper form with possible minor adjustment of the exponent.

Referring now toFIG. 6, another exemplary scheme for performing multi-operand additions is shown. In this example, the summands601are 8 numbers of 32 bits each. The summands are paired up to form the set602of summands and each pair of summands is partitioned into shorter additions of 4 bit numbers and the partition is created without any gaps of zeros. For example, in the top pair of summands602aof set602, bit positions b2, b3, b4and b5is an example of a partitioned short addition of 4 bits. The partition into 4 bits is for illustrative purposes only and should not be considered limiting. The carry resulting from the short addition of four bits is placed in a corresponding bit position in the auxiliary array603. For example, the carry that may result from adding the bit positions b2, b3, b4and b5of the pair602ais placed at the bit position b6of the auxiliary array603. The partitions from the other pairs602b,602cand602dare done in such a way that they are staggered with respect to one another. The staggering is done in a way such that the carries from the short additions across all pairs602are placed in the auxiliary array603without overlap. For example, the carry that may result from adding the bit positions b3, b4, b5and b6of the pair602bis placed at the bit position b7of the auxiliary array603and the carry that may result from adding the bit positions b4, b5, b6and b7of the pair602cis placed at the bit position b8of the auxiliary array603. For binary additions, the auxiliary array will have the carries from the different short additions in a binary form.

In this example, the number of 32 bit summands are reduced to 5, 33 bits summands, including the summands of the set604of partial sums resulting from the additions of the pairs602and the auxiliary array603representing including the carries. The reduction from 8 to 5 numbers is achieved in the time needed to add two 4 bit numbers and transfer the resulting carry (if any) to the auxiliary array603. The time required is independent of the length of the original summands601(32 bits in this case). This adder is suitable for at least 4 summands, which are reduced to 3. In some implementations, the partitioning of the pairs602may be done in any manner as long as the resultant carries from the short additions occupy a unique bit position in the auxiliary array603. In some implementations, the sets602a-602dmay be staggered with respect to one another by more than one bit position. In some implementations, more than one auxiliary array may be required to accommodate the resultant carries.

Even though the above adders have been described primarily with respect to binary numbers, the adders may be used with decimal, octal, hexadecimal and numbers of any other radix. Since the value of the carry when adding two numbers in any radix system is in {0,1}, more than two numbers sharing the same gap locations could be added without requiring more than one digit location to arrest the carry. For example, for radix R, up to R numbers sharing the same gap locations could be added with the maximum possible carry being R−1.

Applications of the adders described herein include, without limitation, the following. The carry arrest multi-operand adders could be implemented in hardware form as part of an advanced VLSI arithmetic unit, or in software form stored in a medium or executed by a computer system. In some implementations, the carry arrest adders could be implemented for multi-core systems. The high degree of parallelism renders the carry arrest adders suitable for multi-core implementation. The carry arrest adders could be used for fast computation of sums, multiplications, matrix multiplication, including inner and outer products. In some implementations, the carry arrest adders could be used for high dimensional with applications to image, digital and array processing and tensor based computations. The carry arrest adders may be used in computer graphics engines, video processing hardware, optical ray tracing apparatus and other systems requiring fast real time processing including fast additions. In some implementations, the carry arrest adders may be used for cryptography applications. Most cryptography applications use modular arithmetic with very large number of bits. While modular arithmetic allows for parallel computation for each modulus independently, the moduli are typically very large, and carries need to be handled efficiently for fast additions.

Referring now toFIG. 7, a system700for performing additions is shown and described. In some implementations, the system700includes a first circuitry705, a second circuitry710and storage720. The first circuitry705may include circuit elements for partitioning the multiple-digit sequences or summands into two or more sets of multiple-digit sequences. The sets of multiple-digit sequences may have two or more summands in each one of them. In some implementations, the partitioned sets are saved or stored in the storage720. The first circuitry705may also include circuit elements for generating one or more auxiliary sets that include digits copied from respective digit positions of the sets of multiple-digit sequences. The first circuitry705may also include circuit elements for replacing one or more digits in the sets of multiple-digit sequences by zeros. In some implementations, the first circuitry further identifies short segments of numbers from the sets of multiple-digit sequences and provides the shorts segments to the second circuitry710.

The second circuitry710may include one or more adders715that are capable of adding the short segments of numbers from the sets of multiple-digit sequences. For example, if the summands are 32 bit long, the first circuitry may identify 4-bit long segments from each pair of summands and provide them to the second circuitry710for implementing the addition of such segments. In some implementations, the short segments may include zeros at certain bit positions introduced by replacing an original bit in the corresponding position. The original bits, as mentioned above, are placed in one or more auxiliary sets. In some implementations, the adders715may all be of the same length. In other implementations, some of the adders715may be of a first length while other adders715may be of a different length. In some implementations, the addition of the short segments may be done in parallel. For example, if each of four 32-bit numbers to be added are broken down into 8 segments of 4-bits each, then 16 additions, each 4-bit long, will be required. If the hardware has 16, 4-bit adders available, the additions may be done in parallel in a time required to do one 4-bit addition. In other implementations, the addition of the short segments may be done in real time as the bits become available. For example, an algorithm may pre-define which bits of a given set are to be copied to an auxiliary set and replaced by zero. In such a case, the bits from the multiple-digit sequences may be allocated to the adders715as they become available and the addition performed as soon as an adder fills up to capacity. This allows for very fast real time addition, especially for large multiple-digit sequences, because partial sums are generated on the run even when the entire multiple-digit sequence is not completely available. In some cases, such real time computation is referred to as asynchronous computation.

In some implementations, the results from the adders715are stored in the storage720. The results may be combined in the storage720to produce partial sums. In some implementations, the first circuitry705communicates with the storage720to store the partitioned and altered sets of multiple-digit sequences. The second circuitry710may further communicate with the storage720to retrieve multiple-digit sequences to process, possibly with the adders715. In some implementations, the first circuitry stores all summands in the storage720before the second circuitry710accesses the summands to compute the additions of the short segments in parallel. In some implementations, the storage720stores the one or more auxiliary sets.

The first circuitry705may include circuit elements to perform, for example, arithmetic and logical operations. For example, the first circuitry705may include, without limitation, one or more of a microprocessor, a microcontroller, a clock circuit, a logic gate, an arithmetic logic unit, a random access memory, an accumulator, a counter, a digital signal processor or other analog and digital circuitry that may be configured to perform the operations described herein.

The second circuitry710may include any circuit element described with respect to the first circuitry705. The second circuitry710may also include adders715. The adders715may be of different forms and types. For example, an adders715may be a carry save adder, a carry select adder, a carry look ahead adder, an adder tree or any other multi-digit adder that may be configured to add two or more multi-digit segments.

The storage720includes memory to store digital data. The storage720may include, without limitation, an accumulator, a random access memory (RAM), a read only memory (ROM), a hard drive, a removable storage media or other forms of hardware that may be configured to store and provide access to digital data.

Many other implementations of the invention other than those described above are within the invention, which is defined by the following claims.