Associative processor addition and subtraction

[0002] The present invention relates to associative processors and, more particularly, to a method of adding and subtracting numbers stored in the associative array of an associative processor.

[0003] An associative processor is a device for parallel processing of a large volume of data. FIG. 1 is a schematic illustration of an associative processor 10. The heart of associative processor 10 is an array 12 of content addressable memory (CAM) cells 14 arranged in rows 16 and columns 18. Associative processor 10 also includes four registers for controlling CAM cells 14: two tags registers 20aand 20bthat include many tag register cells 22, a mask register 24 that includes many mask register cells 26, and a pattern register 28 that includes many pattern register cells 30. Each cell 14, 22, 26 or 30 is capable of storing one bit (0 or 1). Each tags register 20 is a part of a tags logic block 36 that communicates with each row 16 via a dedicated word enable line 32 and a dedicated match result line 34, with each tag register cell 22 being associated with a respective row 16 via word enable line 32, match result line 34 and a dedicated logic unit 38. Each mask register cell 26 and each pattern register cell 30 is associated with a respective column 18. For illustrational simplicity, only three rows 16, only one word enable line 32, only one match result line 34 and only two logic units 38 are shown in FIG. 1. Note that the two tag register cells 22 that are associated with the same row 16 share the same word enable line 32 and the same match result line 34. Typical arrays 12 include 8192 (2¹³) rows 16. The array 12 illustrated in FIG. 1 includes 32 columns 18. More typically, array 12 includes 96 or more columns 18.

[0004] Each machine cycle of associative processor 10 is either a compare cycle or a write cycle. Correspondingly, in a single machine cycle of associative processor 10, each CAM cell 14 performs one and only one of two kinds of elementary operations, as directed by the contents of the corresponding cells 22, 26 or 30 of registers 20a, 20b, 24 and 28: either a compare operation or a write operation. For both kinds of elementary operations, columns 18 that are to be active are designated by the presence of “1” bits in the associated mask register cells 26. The contents of tag register cells 22 of one of tags logic blocks 36 are broadcast to the associated rows 16 as “write enable” signals by that tags logic block 36 via word enable lines 32, with rows 16 that receive a “1” bit being activated. In a compare cycle, each activated row 16 generates a “1” bit match signal on match result line 34 of that row 16. Each activated CAM cell 14 of that row 16 compares its contents with the contents of the cell 30 of pattern register 28 that is associated with the column 18 of that CAM cell 14. If the two contents are identical (both “0” bits or both “1” bits), that CAM cell 14 allows the match signal to pass. Otherwise, that CAM cell 14 blocks the match signal. As a result, if the contents of all the activated CAM cells 14 of a row 16 match the contents of corresponding cells 30 of pattern register 28, the match signal reaches tags logic blocks 36. In a write cycle, the contents of pattern register cells 30 associated with activated columns 18 are written to the activated CAM cells 14 of those columns 18.

[0005] In the example illustrated in FIG. 1, the fifth through eighth columns 18 from the right are activated by the presence of “1” s in the corresponding mask register cells 26. A binary “4” (0100) is stored in the corresponding pattern register cells 30. A compare cycle performed by associative processor 10 in this configuration tests activated rows 16 to see if a binary “4” is stored in their fifth through eighth CAM cells 14 from the right. A write cycle performed by associative processor 10 in this configuration writes binary “4” to the fifth through eighth CAM cells 14 from the right of activated rows 16.

[0006] Each logic unit 38 can be configured to perform, in a single machine cycle, one or more of several logical operations (AND, OR, NOT, XOR, identity) whose inputs are one or more of: the bit stored in the associated tag register cell 22, the bit stored in the corresponding tag register cell 22 in the other tags logic block 36, and, if the cycle is a compare cycle, the presence or absence of a match signal on match result line 34. The AND, OR and XOR operations are binary operations (two inputs). The NOT and identity operations are unary operations (one input). The presence of a match signal on match result line 34 is treated as a binary “1”. The absence of a match signal on match result line 34 is treated as a binary “0”. The result of the logical operation is a single bit that is stored in the associated tag register cell 22. In the simplest set of logical operations, in a compare cycle, the only input is the presence or absence of a match signal on match result line 34 and the sole logical operation is an identity operation. The result of this operation is the writing to the associated tag register cell 22 of the bit corresponding to the presence or absence of a match signal on match result line 34.

[0007] In summary, in both kinds of elementary operations, tags register 20aor 20band mask register 24 provide activation signals and pattern register 28 provides reference bits. Then, in a compare cycle, array 12 provides input to compare with the reference bits and tags registers 20aand 20breceive output; and in a write cycle, array 12 receives output that is identical to one or more reference bits.

[0008] Tags logic blocks 36aand 36balso can broadcast “1” s to all rows 16, to activate all rows 16 regardless of the contents of tags registers 20.

[0009] An additional function of tags registers 20 is to provide communication between rows 16. For example, suppose that the results of a compare operation executed on rows 16 have been stored in tags register 20a, wherein every bit corresponds to a particular row 16. By shifting tags register 20a, the results of this compare operation are communicated from their source rows 16 to other, target rows 16. In a single tags shift operation the compare result of every source row 16 is communicated to a corresponding target row 16, the distance between any source row 16 and the corresponding target row 16 being the distance of the shift.

[0010] More information about associative processors may be found in U.S. Pat. No. 5,974,521, to Akerib, which is incorporated by reference for all purposes as if fully set forth herein.

[0011] A prior art method of adding a first set of N binary numbers {a_n, n=1 . . . N}, stored in a first set of columns 18, to another set of N binary numbers {b_n, n=1 . . . N}, stored in a second set of columns 18, and storing the resulting N binary numbers {s_n, n=1 . . . N} in a third set of columns 18, is taught by Daniel P. Sieworek et al. in Computer Structures: Principles and Examples, Chapter 21: “A productive implementation of an associative array processor: STARAN 319”, McGraw-Hill, New York (1982), also available at the URL

[0012] http://www.ulib.org/webRoot/Books/Saving_Bell_Books/SBN%20Computer%20Strucutres/csp0336.htm.

[0013] Without loss of generality, all the input numbers {a_n} and {b_n} can be assumed to have the same number of bits, because any number that is shorter than the longest input number can be left-padded with “0” bits. For any particular index n, a_nand b_nare initially stored in the same row 16, in different sets of respective columns, and s_nis to be stored in the same row 16, typically in its own set of columns, although either a_nor b_ncan be partly or completely overwritten with s_nbecause once a bit of s_nis computed, the bits of a_nand b_nthat contributed to that bit of s_nare no longer needed.

[0014] FIG. 2 is a flow chart of the algorithm of Sieworek et al. The input numbers are assumed to be M bits long. The m-th bit of a number a, b or s is designated by a[m], b[m] or s[m]. “x” refers to a bit stored in the tag register cell 22 of tags register 20athat is associated with the row 16 that stores the numbers a, b and s. “y” refers to a bit stored in the tag register cell 22 of tags register 20bthat is associated with the row 16 that stores the numbers a, b and s. The symbol “:=” means “replacement”, as in ALGOL. At each stage of the loop over the bit index m, the carry bits are stored in tags register 20b.

[0015] The activities of array processor 10 in each of the blocks of FIG. 2 now will be described in detail.

[0016] In the initialization step (block 40), all tag register cells 22 are set to zero, for example by all logic units 38 performing the logical operation XOR with both inputs being whatever bits are initially in tag register cells 22. In addition, all pattern register cells 30 are set to “1”.

[0017] The first machine cycle in the loop over m (block 42) is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits a[m]. One of tags logic blocks 36 broadcasts “1” s to all rows 16. The resulting match signals indicate whether the respective bits a[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an AND operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20b. Each logic unit 38 of tags logic block 36athen performs an XOR operation whose two inputs are the result of the AND operation and the bit previously stored in the associated tag register cell 22 of tags register 20a. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20b.

[0018] The second machine cycle in the loop over m (block 44) is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits b[m]. One of tags logic blocks 36 broadcasts “1” s to all rows 16. The resulting match signals indicate whether the respective bits b[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an AND operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20b. Each logic unit 38 of tags logic block 36athen performs an XOR operation whose two inputs are the result of the AND operation and the bit previously stored in the associated tag register cell 22 of tags register 20a. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20b.

[0019] The third machine cycle in the loop over m (block 46) is a write cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that is to store bits s[m]. Tags logic block 36bbroadcasts the contents of tag register cells 22 of tags register 20ato all rows 16, as write enable signals. This results in the contents of tag register cells 22 of tags register 20abeing written to the column 18 that is to store bits s[m]. Meanwhile, each logic unit 38 of tags logic block 36aperforms an XOR operation whose two inputs are the bit previously stored in the associated tag register cell 22 of tags register 20aand the bit previously stored in the corresponding tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a.

[0020] The fourth machine cycle in the loop over m (block 48) may be either a compare cycle or a write cycle, because no data are exchanged between array 12 and tags registers 20 in this machine cycle. Each logic unit 38 of tags logic block 36aperforms an XOR operation whose two inputs both are the bit previously stored in the associated tag register cell 22 of tags register 20a. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an XOR operation whose two inputs are the bit previously stored in the corresponding tag register cell 22 of tags register 20aand the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20b.

[0021] In block 50, the bit index m is incremented. In block 52, m is tested to see if all input bits have been processed. If there are more input bits to process, the algorithm returns to block 42. Otherwise, in block 54, all mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that is to store the final carry bits, bits s[M+1]. Tags logic block 36bbroadcasts the contents of tag register cells 22 of tags register 20ato all rows 16, as write enable signals. This results in the contents of tag register cells 22 of tags register 20abeing written to the column 18 that is to store bits s[M+1].

[0022] Alternatively, if it is known a priori that all numbers b_nare shorter than the longest number of {a_n}, a simplified version of the algorithm of FIG. 2 can be applied to bits of numbers a for which the bit index m exceeds the number of bits in the longest member of the set of numbers {b_n}. Specifically, if b[m]=0, then the output of block 44 is identical to the input of block 44, and block 44 can be skipped. In general, the full algorithm of FIG. 2 must be applied only to bits a[m] of the number a that have corresponding bits b[m] in the number b.

[0023] According to the present invention there is provided a method of adding each binary number of a plurality of first binary numbers to a corresponding binary number of a like plurality of second binary numbers, including the steps of: (a) providing an array processor that includes: (i) an array of content addressable memory (CAM) cells, and (ii) a first and second tags register, each tags register including, for each row of the array, a respective tag register cell, each tags register also including, for each row of the array, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of: (A) a bit stored in the respective tag register cell of the first tags register immediately prior to the single machine cycle, (B) a bit stored in the respective tag register cell of the second tags register immediately prior to the single machine cycle, and (C) if the single machine cycle is a compare cycle: an output of a compare operation on the each row; (b) storing the plurality of first binary numbers in a respective first at least one column of the array, each first binary number being stored in a respective row of the array; (c) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, thereby producing a respective sum bit, all within at most three machine cycles; the combining being effected for all the binary numbers substantially simultaneously.

[0024] According to the present invention there is provided a method of adding each binary number of a plurality of first binary numbers to a corresponding binary number of a like plurality of second binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, wherein, in a first machine cycle of the combining, the inputs of the logical operations include only the each bit of the first binary number stored in the each row and the respective carry bit.

[0025] According to the present invention there is provided a method of adding each binary number of a plurality of first binary numbers to a corresponding binary number of a like plurality of second binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the respective logic units performing at most five logical operations, thereby producing a respective sum bit, and (ii) storing the respective sum bit in one of the CAM cells of the each row.

[0026] According to the present invention there is provided a method of adding each binary number of a plurality of first binary numbers to a corresponding binary number of a like plurality of second binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, at most three of the logical operations performed by the logic units including the corresponding bit of the second binary number stored in the each row as an input thereof, thereby producing a respective sum bit, and (ii) storing the respective sum bit in one of the CAM cells of the each row.

[0027] According to the present invention there is provided a method of adding each binary number of a plurality of first binary numbers to a corresponding binary number of a like plurality of second binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the logical operations performed by the logic units including at least one OR operation, thereby producing a respective sum bit, and (ii) storing the respective sum bit in one of the CAM cells of the each row.

[0028] According to the present invention there is provided a method of adding each binary number of a plurality of first binary numbers to a corresponding binary number of a like plurality of second binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the logical operations performed by the logic units including at most two XOR operations, thereby producing a respective sum bit, and (ii) storing the respective sum bit in one of the CAM cells of the each row.

[0029] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) providing an array processor that includes: (i) an array of content addressable memory (CAM) cells, and (ii) a first and second tags register, each tags register including, for each row of the array, a respective tag register cell, each tags register also including, for each row of the array, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of: (A) a bit stored in the respective tag register cell of the first tags register immediately prior to the single machine cycle, (B) a bit stored in the respective tag register cell of the second tags register immediately prior to the single machine cycle, and (C) if the single machine cycle is a compare cycle: an output of a compare operation on the each row; (b) storing the plurality of first binary numbers in a respective first at least one column of the array, each first binary number being stored in a respective row of the array; (c) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, thereby producing a respective difference bit, all within at most three machine cycles; the combining being effected for all the binary numbers substantially simultaneously.

[0030] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, wherein, in a first machine cycle of the combining, the inputs of the logical operations include only the each bit of the first binary number stored in the each row and the respective carry bit.

[0031] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number stored in the each row that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the respective logic units performing at most seven logical operations, thereby producing a respective difference bit, and (ii) storing the respective difference bit in one of the CAM cells of the each row.

[0032] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, at most four of the logical operations performed by the logic units including the corresponding bit of the second binary number stored in the each row as an input thereof, thereby producing a respective difference bit, and (ii) storing the respective difference bit in one of the CAM cells of the each row.

[0033] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the logical operations performed by the logic units including at least one OR operation, thereby producing a respective difference bit, and (ii) storing the respective difference bit in one of the CAM cells of the each row.

[0034] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the logical operations performed by the logic units including at most two XOR operations, thereby producing a respective difference bit, and (ii) storing the respective difference bit in one of the CAM cells of the each row.

[0035] According to the present invention there is provided a method of subtracting each binary number of a plurality of second binary numbers from a corresponding binary number of a like plurality of first binary numbers, including the steps of: (a) storing the plurality of first binary numbers in a respective first at least one column of an array of content addressable memory (CAM) cells, each first binary number being stored in a respective row of the array; (b) storing the plurality of second binary numbers in a respective second at least one column of the array, each second binary number being stored in the respective row of the corresponding first binary number, (c) providing, for each row: (i) a first tag register cell, (ii) a second tag register cell, and (iii) for each tag register cell, a respective logic unit operative to perform, within a single machine cycle, at least one logical operation on input including at least two operands selected from the group consisting of a bit from one of the binary numbers stored in the each row, a bit stored in the each tag register cell immediately prior to the single machine cycle and a bit stored in the other tag register cell immediately prior to the single machine cycle; and (d) for each row: for each bit of the first binary number, stored in the each row, that has a corresponding bit in the second binary number stored in the each row: (i) combining the each bit of the first binary number stored in the each row with the corresponding bit of the second binary number stored in the each row and with a respective carry bit, using the first and second registers and the respective logic units, the logical operations performed by the logic units including at most two XOR operations, thereby producing a respective difference bit, and (ii) storing the respective difference bit in one of the CAM cells of the each row.

[0036] FIG. 3 is a flow chart of a first algorithm of the present invention for adding the N binary numbers {a_n} to the N binary numbers {b_n}. FIG. 4 is a flow chart of a second algorithm of the present invention for adding the N binary numbers {a_n} to the N binary numbers {b_n}. FIG. 5 is a flow chart of an algorithm of the present invention for subtracting the N binary numbers {b_n} from the N binary numbers {a_n}. Initialization blocks 56, 70 and 84 correspond to prior art initialization block 40, except that x is not initialized. Index increment blocks 64, 78 and 92 correspond to prior art increment block 50. Index test blocks 66, 80 and 94 correspond to prior art index test block 52. The storage of the final set of carry bits in blocks 68, 82 and 96 corresponds to prior art block 54. The algorithms of the present invention differ from the prior art algorithm principally in the machine cycle blocks within the loop over the bit index m. These differences are described in detail below. For now, it suffices to make the following observations about the present invention:

[0037] 1. The algorithms of the present invention include only three machine cycles per pair of input bits: two compare cycles and one write cycle.

[0038] 2. In the algorithms of the present invention, x is neither initialized before the loop over m nor shared between successive iterations of the loop over m. Only the carry bits (y) are initialized (to “0”) before the loop over m and shared between successive iterations of the loop over m.

[0039] 3. The second addition algorithm of the present invention includes only five logical operations (two ANDs, two XORs, one OR) per pair of input bits, vs. nine logical operations per pair of input bits in the prior art algorithm. Similarly, the subtraction algorithm of the present invention includes only seven logical operations (two ANDs, two XORs, two NOTs, one OR) per pair of input bits, of which only five are binary logical operations.

[0040] 4. In the second addition algorithm of the present invention, only three of the logical operations per pair of input bits include b[m] as a direct or indirect argument, vs. six logical operations per pair of input bits in the prior art algorithm. Similarly, in the subtraction algorithm of the present invention, only four of the logical operations per pair of input bits include b[m] as a direct or indirect argument.

[0041] 5. Both the second addition algorithm of the present invention and the subtraction algorithm of the present invention include OR operations. The prior art algorithm lacks OR operations.

[0042] 6. In both the second addition algorithm of the present invention and the subtraction algorithm of the present invention, there are only two XOR operations per pair of input bits, vs. seven XOR operations in the prior art algorithm.

[0043] 7. In both the second addition algorithm of the present invention and the subtraction algorithm of the present invention, only one of the logic units performs XOR operations. It follows that, for example, in associative processor 10, logic units 38 of only one of tags logic blocks 36 need to be configured to do XOR operations. This leads to a simplification of associative processor 10, because the hardware needed to perform an XOR operation is more complicated than the hardware needed to perform the other logical operations.

[0044] The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein:

[0045] FIG. 1 is a schematic illustration of an associative processor;

[0046] FIG. 2 is a flow chart of a prior art addition algorithm;

[0047] FIG. 3 is a flow chart of a first addition algorithm of the present invention;

[0048] FIG. 4 is a flow chart of a second addition algorithm of the present invention;

[0049] FIG. 5 is a flow chart of a subtraction algorithm of the present invention.

[0050] The present invention is of algorithms for addition and subtraction using an associative processor.

[0051] The principles and operation of associative processor arithmetic according to the present invention may be better understood with reference to the drawings and the accompanying description.

[0052] The algorithm of FIG. 3 is a simplification of the prior art algorithm of FIG. 2, based on the observation that the “x:=x XOR x” step in block 48 always sets x equal to “0”. Therefore, there is no need to initialize x or to carry x between successive iterations of the loop over m.

[0053] Referring again to the drawings, the activities of array processor 10 in blocks 58, 60 and 62 of FIG. 3 now will be described in detail.

[0054] Block 58 is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits a[m]. One of tags logic blocks 36 broadcasts “1”s to all rows 16. The resulting match signals indicate whether the respective bits a[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an AND operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20b. Each logic unit 38 of tags logic block 36athen performs a NOT operation whose input is the result of the AND operation. The result of this NOT operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20b.

[0055] Block 60 also is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits b[m]. One of tags logic blocks 36 broadcasts “1” s to all rows 16. The resulting match signals indicate whether the respective bits b[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an AND operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20b. Each logic unit 38 of tags logic block 36athen performs an XOR operation whose two inputs are the result of the AND operation and the bit previously stored in the associated tag register cell 22 of tags register 20a. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20b.

[0056] Block 62 is a write cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that is to store bits s[m]. Tags logic block 36bbroadcasts the contents of tag register cells 22 of tags register 20bto all rows 16, as write enable signals. This results in the contents of tag register cells 22 of tags register 20bbeing written to the column 18 that is to store bits s[m]. Meanwhile, each logic unit 38 of tags logic block 36bperforms an XOR operation whose two inputs are the bit previously stored in the associated tag register cell 22 of tags register 20band the bit previously stored in the corresponding tag register cell 22 of tags register 20a. Each logic unit 38 of tags logic block 36bthen performs another XOR operation whose inputs are the result of the first XOR operation and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of the second XOR operation is stored in the associated tag register cell 22 of tags register 20b.

[0057] As in the case of the prior art algorithm of FIG. 2, block 60 can be skipped for the bits of numbers a for which the bit index m exceeds the number of bits in the longest member of the set of numbers {b_n}. In general, the full algorithm of FIG. 3 must be applied only to bits a[m] of the number a that have corresponding bits b[m] in the number b.

[0058] Referring now to FIG. 4, the activities of array processor 10 in blocks 72, 74 and 76 now will be described in detail.

[0059] Block 72 is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits a[m]. One of tags logic blocks 36 broadcasts “1” s to all rows 16. The resulting match signals indicate whether the respective bits a[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an AND operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this AND operation is stored in the associated tag register cell 22 of tags register 20b.

[0060] Block 74 also is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits b[m]. One of tags logic blocks 36 broadcasts “1”s to all rows 16. The resulting match signals indicate whether the respective bits b[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20a. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms an AND operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20a. Each logic unit 38 of tags logic block 36bthen performs an OR operation whose two inputs are the output of the AND operation and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this OR operation is stored in the associated tag register cell 22 of tags register 20b.

[0061] Block 76 is a write cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that is to store bits s[m]. Tags logic block 36abroadcasts the contents of tag register cells 22 of tags register 20ato all rows 16, as write enable signals. This results in the contents of tag register cells 22 of tags register 20abeing written to the column 18 that is to store bits s[m].

[0062] As in the case of the algorithm of FIG. 3, block 74 can be skipped for the bits of numbers a for which the bit index m exceeds the number of bits in the longest member of the set of numbers {b_n}. In general, the full algorithm of FIG. 4 must be applied only to bits a[m] of the number a that have corresponding bits b[m] in the number b.

[0063] The following is a proof of the correctness of the algorithm of FIG. 4. In this proof, the bit index m is suppressed and “c” denotes the carry bit initially stored in y.

[0064] At the end of the second machine cycle, x is to be the sum of a, b and c, which is a XOR b XOR c.

[0065] x=(c XOR a)XOR b=c XOR a XOR b=a XOR b XOR c

[0066] At the end of the second machine cycle, y is to be the carry bit of a+b+c. This is (a AND c) OR (b AND c) OR (a AND b). $\begin{array}{c}y=\left(a\mathrm{AND}c\right)\mathrm{OR}\left[\left(a\mathrm{XOR}c\right)\mathrm{AND}b\right]\\ =\left(a\mathrm{AND}c\right)\mathrm{OR}\left[\left(\left(\mathrm{NOT}a\right)\mathrm{AND}c\right)\mathrm{OR}\left(a\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\mathrm{AND}b\right]\\ =\left(a\mathrm{AND}c\right)\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\mathrm{AND}c\right)\mathrm{OR}\left(a\mathrm{AND}b\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\\ =[a\mathrm{AND}\left(c\mathrm{OR}\left(b\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\right]\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\mathrm{AND}c\right)\\ =\left[a\mathrm{AND}\left(c\mathrm{OR}b\right)\right]\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\mathrm{AND}c\right)\\ =\left(a\mathrm{AND}c\right)\mathrm{OR}\left(a\mathrm{AND}b\right)\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\mathrm{AND}c\right)\\ =\left[c\mathrm{AND}\left(a\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\right)\right)\right]\mathrm{OR}\left(a\mathrm{AND}b\right)\\ =\left[c\mathrm{AND}\left(a\mathrm{OR}b\right)\right]\mathrm{OR}\left(a\mathrm{AND}b\right)\\ =\left(a\mathrm{AND}c\right)\mathrm{OR}\left(b\mathrm{AND}c\right)\mathrm{OR}\left(a\mathrm{AND}b\right)\\ Q.E.D.\end{array}$

[0067] Referring now to FIG. 5, the activities of array processor 10 in blocks 86, 88 and 90 now will be described in detail.

[0068] Block 86 is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits a[m]. One of tags logic blocks 36 broadcasts “1” s to all rows 16. The resulting match signals indicate whether the respective bits a[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the corresponding tag register cell 22 of tags register 20b. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms a NOT operation whose input is the bit corresponding to the match signal received via match result line 34. Each logic unit 38 of tags logic block 36bthen performs an AND operation whose two inputs are the output of the NOT operation and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this AND operation is stored in the associated tag register cell 22 of tags register 20b.

[0069] Block 88 also is a compare cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that stores bits b[m]. One of tags logic blocks 36 broadcasts “1” s to all rows 16. The resulting match signals indicate whether the respective bits b[m] are “0” or “1”. Each logic unit 38 of tags logic block 36aperforms an XOR operation whose two inputs are the bit corresponding to the match signal received via match result line 34 and the bit previously stored in the associated tag register cell 22 of tags register 20a. The result of this XOR operation is stored in the associated tag register cell 22 of tags register 20a. Meanwhile, each logic unit 38 of tags logic block 36bperforms a NOT operation whose input is the bit corresponding to the match signal received via match result line 34. Each logic unit 38 of tags logic block 36bthen performs an AND operation whose two inputs are the result of the NOT operation and the bit previously stored in the corresponding tag register cell 22 of tags register 20a. Each logic unit 38 of tags logic block 36bthen performs an OR operation whose two inputs are the output of the AND operation and the bit previously stored in the associated tag register cell 22 of tags register 20b. The result of this OR operation is stored in the associated tag register cell 22 of tags register 20b.

[0070] Block 90 is a write cycle. All mask register cells 26 are set to “0” except for the mask register cell 26 corresponding to the column 18 that is to store bits s[m]. Tags logic block 36abroadcasts the contents of tag register cells 22 of tags register 20ato all rows 16, as write enable signals. This results in the contents of tag register cells 22 of tags register 20abeing written to the column 18 that is to store bits s[m].

[0071] For the bits of numbers a for which the bit index m exceeds the number of bits in the longest member of the set of numbers {b_n}, the algorithm of FIG. 5 can be shortened from three machine cycles to two machine cycles, but not by merely skipping block 88. Even though the first step of block 88 reproduces x exactly when b[m]=0, the second step of block 88 does not reproduce y exactly. The output of the second step of block 88 is: $\begin{array}{c}\left(\left(\mathrm{NOT}0\right)\mathrm{AND}x\right)\mathrm{OR}y=\left(1\mathrm{AND}x\right)\mathrm{OR}y\\ =x\mathrm{OR}y\end{array}$

[0072] Instead of skipping block 88, block 90 is skipped; and block 88 is changed from a compare cycle to a write cycle, in which tags register 20aperforms the write operations that write the contents of tag register cells 22 of tags register 20ato the column 18 that is to store bits s[m], and tags register 20bperforms the second step of block 88.

[0073] The following is a proof of the correctness of the algorithm of FIG. 5. As in the proof of the correctness of the algorithm of FIG. 4, the bit index m is suppressed and “c” denotes the carry bit initially stored in y.

[0074] At the end of the second machine cycle, x is to be the difference of sum of a and b with a carry bit c, which is a XOR b XOR c.

[0075] x=(c XOR a)XOR b=c XOR a XOR b=a XOR b XOR c

[0076] At the end of the second machine cycle, y is to be the carry bit of a-b. This is ( (NOT a) AND c) OR (b AND c) OR ( (NOT a) AND b). $\begin{array}{c}y=\left(c\mathrm{AND}\left(\mathrm{NOT}a\right)\right)\mathrm{OR}\left[\left(\mathrm{NOT}\left(a\mathrm{XOR}c\right)\right)\mathrm{AND}b\right]\\ =\left(c\mathrm{AND}\left(\mathrm{NOT}a\right)\right)\mathrm{OR}\\ \left[\left[\mathrm{NOT}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}c\right)\mathrm{OR}\left(a\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\right]\mathrm{AND}b\right]\\ =\left(c\mathrm{AND}\left(\mathrm{NOT}a\right)\right)\mathrm{OR}\\ \left[\left[\mathrm{NOT}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}c\right)\mathrm{AND}\left(\mathrm{NOT}\left(a\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\right)\right]\mathrm{AND}b\right]\\ =\left(c\mathrm{AND}\left(\mathrm{NOT}a\right)\right)\mathrm{OR}\\ \left[\left[\left(a\mathrm{OR}\left(\mathrm{NOT}c\right)\right)\mathrm{AND}\left(\mathrm{NOT}a\right)\mathrm{OR}c\right)\right]\mathrm{AND}b]\\ =\left(c\mathrm{AND}\left(\mathrm{NOT}a\right)\right)\mathrm{OR}\\ \left[\left[\left(\left(\mathrm{NOT}a\right)\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\mathrm{OR}\left(a\mathrm{AND}c\right)\right]\mathrm{AND}b\right]\\ =\left(c\mathrm{AND}\left(\mathrm{NOT}a\right)\right)\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\\ \mathrm{OR}\left(a\mathrm{AND}b\mathrm{AND}c\right)\\ =[\left(\mathrm{NOT}a\right)\mathrm{AND}\left(c\mathrm{OR}\left(b\mathrm{AND}\left(\mathrm{NOT}c\right)\right)\right]\mathrm{OR}\left(a\mathrm{AND}b\mathrm{AND}c\right)\\ =\left[\left(\mathrm{NOT}a\right)\mathrm{AND}\left(c\mathrm{OR}b\right)\right]\mathrm{OR}\left(a\mathrm{AND}b\mathrm{AND}c\right)\\ =\left(\left(\mathrm{NOT}a\right)\mathrm{AND}c\right)\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\right)\mathrm{OR}\left(a\mathrm{AND}b\mathrm{AND}c\right)\\ =\left[c\mathrm{AND}\left(\left(\mathrm{NOT}a\right)\mathrm{OR}\left(a\mathrm{AND}b\right)\right)\right]\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\right)\\ =\left[c\mathrm{AND}\left(\left(\mathrm{NOT}a\right)\mathrm{OR}b\right)\right]\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\right)\\ =\left(\left(\mathrm{NOT}a\right)\mathrm{AND}c\right)\mathrm{OR}\left(b\mathrm{AND}c\right)\mathrm{OR}\left(\left(\mathrm{NOT}a\right)\mathrm{AND}b\right)\\ Q.E.D.\end{array}$

[0077] In addition to adding and subtracting binary numbers stored in different sets of columns 18, the present invention also can be used to add and subtract binary numbers stored in the same set of columns 18. For example, suppose that binary numbers {a_n, n=1 . . . N} are stored in a set of columns 18 and it is desired to add the first N−d numbers to the numbers d rows 16 below them, i.e., to compute {a_n+a_n+d} for n=1 through N−d. Either the algorithm of FIG. 3 or the algorithm of FIG. 4 can be used for this purpose, with tags registers 20 shifted down by d bits at the end of the first machine cycle so that, for any first input bit a_n[m], the second input bit is a_n+d[m]; and with tags register 20bshifted up by as many bits at the end of the second machine cycle as are needed to put the sum bits in the desired rows 16.

[0078] While the invention has been described with respect to a limited number of embodiments, it will be appreciated that many variations, modifications and other applications of the invention may be made.