Abstract:
Multiple matches of words in a content addressable memory are detected by identifying each match of the input word to a word in the memory, and generating a representation of a relationship OR (x i  AND x j ), where x i =x 1 , x 2 , . . . x N−1 , x j εx i+1 , x i+2 , . . . x N , and x 1 , x 2 , . . . , x N  are the compare results of the individual words in the memory to the input word. A representation of at least one match is identified by generating a representation of a relationship x 1  OR x 2  OR x 3  OR . . . OR x N . The apparatus comprises a hierarchy of logic that carries a general match representation indicating at least one match between the input word and all of the memory words, and a multiple-match representation indicating multiple matches between the input word and the words in the memory.

Description:
FIELD OF THE INVENTION 
   This invention pertains to multiple match detection circuits for use with content addressable memories. 
   BACKGROUND OF THE INVENTION 
   Content addressable memories (CAM) are used to compare input words to all words stored in the memory. If the input word matches one or more words stored in the memory, the CAM will output the address of one of the matched words. In some CAM applications, it is important to know if a “match” result is a single-hit or multiple-hit. For this, a multiple match detect circuit must be used with such CAMs. 
   Prior multiple match detect circuits included dynamic analog comparator circuits that measured a signal value that was based on the number of hits. The worst-case condition of such circuits was to distinguish between one and two hits, since the difference between those two cases was the smallest. 
   As semiconductor technology advances toward smaller transistors, process variations of manufacturing semiconductor chips affects transistor performance in relatively greater proportion. In 0.13μ and newer integrated circuit technologies, the effects of process variation is relatively large compared to older, larger technologies. Therefore, it is more difficult to distinguish between one and two hits with an analog comparator with newer, smaller technologies. One problem of analog comparator circuits is that they do not consistently operate across all PVT corners (i.e. different combinations of process, voltage and temperatures). For example, inconsistency is known to exist in chips constructed using 0.18μ technology. The ability to form reliable analog comparators in 0.13μ and newer technology is even more problematic due to the sensitivity of the chip to process variations. 
     FIG. 1  illustrates a prior multiple match detect circuit for a CAM containing N words and constructed in 0.18μ or larger technology. Individual hitlines HL 0 -HL[N-1] carry the compare results of individual words in the CAM to the input word; the hitline carrying a signal representing that the corresponding word in the CAM matches the input word. Hitlines HL 0 -HL[N-1] are connected to two dedicated bitlines, X 1 N and X 1  through respective pull-down transistors  10  and respective pull-up transistors  12 . When a hit signal appears on any of the hitlines HL 0 -HL[N-1], the respective pull-down and pull-up transistors will be turned on. Thus if one hit occurs, one pull-down and one pull-up transistors are turned on; if there are two hits, two pull-down and two pull-up transistors will be turned on, and so on. Bitlines X 1 N and X 1  are connected to analog comparator  14 , which distinguishes between one and two hits according to different pull-up and pull-down strengths. 
   One problem with prior analog multiple match detect circuits is that as the technology moves to smaller transistors, such as 0.18μ and smaller, it becomes difficult to find a working point for the comparator to distinguish one and two hits across all PVT corners. The circuit would be too sensitive to process variations that the confidence is not great that multiple hits in a CAM would be detected using 0.13μ technology. 
   Another disadvantage with some multiple hit detection circuits is that they are not designed to identify multiple hits simultaneously with the identification of general hits, an identification of a general hit being that there is at least one hit in alliwords of the memory. More particularly, all CAMs are designed to identify general hits, but separate circuitry is required to identify multiple hits. 
   Yet another disadvantage with analog comparator circuits used for multiple match detection is that the comparator circuit must operate on a clock signal, which causes timing or race condition issues that must be addressed with timing margins. The addition of timing margins usually slows circuit performance, thereby contributing to delay. 
   SUMMARY OF THE INVENTION 
   The present invention is directed to a logical multiple match detection circuit that identifies single and multiple matches of an input word to words in a content addressable memory. 
   In one embodiment, multiple matches of words in a content addressable memory are detected by identifying each match of the input word to a word in the memory, and generating a representation of a relationship OR(x i  AND x j ), where x i =x 1 , x 2 , . . . x N−1 , x j εx i+1 , x i+2 , . . . x N , and x 1 , x 2 , . . . , x N  are the compare results of individual words in the memory to the input word. 
   In some versions, a representation of at least one match is identified by generating a representation of a relationship x 1  OR x 2  OR x 3  OR . . . OR x N . 
   In another embodiment, a circuit detects multiple matches of words in a content addressable memory to an input word. The content addressable memory has a hitline for each word in the memory, each hitline carrying a binary signal representative of a match or not-match condition of the respective word to the input word. A first logic element is responsive to binary signals representative of a match condition on respective pairs of hitlines to propagate a multiple-match signal. A second logic element is responsive to binary signals representative of a match condition on each hitline to propagate respective hit signals. A third logic element is responsive to a plurality of hit signals propagated by the second logic element to propagate the multiple-match signal. 
   In some versions the logic elements are arranged in a hierarchical arrangement such that the first logic element comprises a plurality of first logic gates coupled to respective pairs of hitlines. The second logic element comprises a plurality of second logic gates coupled to the respective pairs of hitlines. The third logic element comprises a plurality of third logic gates responsive to hit signals propagated by respective pairs of second logic gates to propagate respective match signals. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a circuit diagram of a prior multiple match detection circuit. 
       FIGS. 2-7  are circuit diagrams of various embodiments of multiple match detection circuits according to the present invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The present invention is directed to a multiple match detection circuit for a CAM that uses static logic, rather than dynamic analog comparators. Consequently, the multiple match detection circuit of the present invention is physically more reliable and less sensitive to process variations than other dynamic versions of multiple match detection circuit. 
   The multiple match detection is realized in a hierarchical manner. At a first logic level, herein referred to as the X 2  level, “hit” and “multiple hit” signals, H 2  and M 2 , respectively, are generated for each pair of words (W 0  and W 1 , W 2  and W 3 , . . . ). A hit signal indicates whether or not there is at least one match between the two words and a multiple hit signal indicates whether or not both words matched. Thus, H 2 =HL 0  OR HL 1  and M 2 =HL 0  AND HL 1 , where HL 0  and HL 1  are the hitline signals from words  0  and  1 . 
   Signals H 2  and M 2  can be generated using one NAND and one NOR gate, as shown in  FIG. 2 , where HLN 0  and HLN 1  are the inversions of HL 0  and HL 1 , respectively. If at least one of HLN 0  and HNL 1  is low (meaning that one or both of HL 0  and HL 1  is high), the NAND gate propagates a high H 2  signal indicating a “hit” amongst HL 0  and HL 1 . If both of HLN 0  and HNL 1  are low (meaning that both HL 0  and HL 1  are high), the NOR gate propagates a high M 2  signal indicating a “multiple hit” with HL 0  and HL 1 . 
   At a second logic level for each four words, herein referred to as the X 4  level, hit and multiple hit signals (H 4  and M 4 ) are generated using the hit and multiple hit signals from the X 2  level (H 2 T/M 2 T for the top pair and H 2 B/M 2 B for the bottom pair), H 4 =H 2 T OR H 2 B, M 4 =(H 2 T AND H 2 B) OR (M 2 T OR M 2 B).  FIG. 3  shows the circuit for realizing H 4  and M 4 . 
   As shown in  FIG. 3 , the MMDETX 4  circuit  40  includes NAND gate  20  and NOR gate  22  connected to receive the HLN 0  and HLN 1  and configured as shown in  FIG. 2  to propagate H 2  and M 2  signals, designated H 2 B and M 2 B. Similarly, NAND gate  24  and NOR gate  26  receive the HLN 3  and HLN 4  and are configured to propagate H 2 T and M 2 T signals. NOR gate  28  receives the H 2 B and H 2 T signals and propagates an inversion of the H 4  signal. Thus, if either H 2 B or H 2 T is high, indicating a “hit” amongst the inputs, NOR gate  28  propagates a low signal, which is inverted by inverter  30  to provide a high H 4  signal, indicating at least one hit. 
   NOR gate  32  receives the M 2 B and M 2 T signals. If either M 2 B or M 2 T is high (meaning a multiple hit amongst HL 0  and HL 1  or HL 2  and HL 3 ), gate  32  propagates a low signal to NAND gate  36 . NAND gate  34  receives the H 2 B and H 2 T signals and will propagate a logical low if both of H 2 B and H 2 T are high (meaning at least one of HL 0  and HL 1  is a match and at least one of HL 2  and HL 3  is a match, so there are at least two matches in HL 0 -HL 03 ). NAND gate  36  receives the outputs of gates  32  and  34  and propagates a high to the M 4  output if either (or both) inputs is low (indicating a multiple hit amongst HL 0 -HL 3 ). 
     FIG. 4  is a circuit diagram of a multiple hit detection circuit for the X 8  level. Circuit MMDETX 8  includes two MMDETX 4  circuits  40   a  and  40   b,  illustrated in  FIG. 3 , receiving HNL 0 -HNL 3  and HNL 4 -HNL 7  signals, respectively. An HMGEN circuit  44  is connected to the outputs of circuits  40   a  and  40   b  and includes a NOR gate  46  and inverter  48  that propagate the H 8  hit signal, and NOR gate  50  and NAND gates  52  and  54  that propagate the M 8  multiple hit signal. It will be appreciated that NOR gate  46  and inverter  48  operate in a manner similar to gate  28  and inverter  30  in  FIG. 3  and that NOR gate  50  and NAND gates  52  and  54  operate in a manner similar to gates  32 - 36  in  FIG. 3 . 
   Similarly, the hit and multiple hit signals can be generated at X 16 , X 32 , . . . , X 256  levels, etc. by simple expansion of the circuit. As shown in  FIGS. 5-7  each level of circuit employs two instances of the next smaller circuit plus an additional HMGEN circuit  44  shown in  FIG. 4 . 
     FIGS. 5-7  illustrate layouts for the MMDETX 8  circuit shown in  FIG. 4 , an MMDETX 16  and an MMDETX 32  circuit. As shown in  FIG. 5 , the MMDETX 8  circuit is composed of one HMGEN circuit  44  in a second column connected to two MMDETX 4  circuits  40   a  and  40   b  in a first column. For the MMDETX 16  circuit shown in  FIG. 6 , the layout consists of four MMDETX 4  circuits  40   a - 40   d  and two HMGEN circuits  44   a  and  44   b  configured as two MMDET8 circuits, plus one additional HMGEN circuit  46 , as shown in  FIG. 6 . Circuit  46  is identical to HMGEN circuit  44 . For an MMDETX 32  circuit, the layout consists of eight MMDETX 4  circuits  40   a - 40   h  and six HMGEN circuits  44   a - 44   b  and  46   a  and  46   b  configured as two MMDET16 circuits, plus one additional HMGEN circuit  48 , as shown in  FIG. 7 . It is evident that the circuit can be expanded to accommodate content addressable memories capable of storing N words, where N=2 x  and x is a whole natural number. 
   From the above, it is evident that for a CAM containing N words, the hit signal
 
 H ( x   1   , . . . , x   N )= x   1  OR  x   2  OR  x   3  OR . . . OR  x   N ,   (1)
 
and the multiple-match signal
 
 M ( x   1   , . . . , x   N )=OR( x   i  AND  x   j ),   (2)
 
where x 1 , x 2 , . . . , x N  are the individual words in the CAM, x i =x 1 , x 2 , . . . x N−1  and x j εx i+1 , x i+2 , . . . x N . Thus, if any x i  and any x j  are both true, a multiple match is detected by relationship (2). A general match is identified if at least one input is true in expression (1) even though no multiple-match is found by expression (2).
 
   The physical layouts shown in  FIGS. 5-7  illustrate that all MMDETX 4  circuits  40  are placed in a first column of the chip and all HMGEN circuits  44 ,  46 ,  48  are placed in a second column of the chip, regardless of the size of the CAM or the multiple match detection circuit. As shown in  FIG. 4 , routing wires  42  will be necessary for each HMGEN circuit  44  and  46  to couple the outputs of circuits  40  to circuits  44 , from circuits  44  to circuits  46 , and so on. Vertical routing wires are also necessary in at least some circuits  44 ,  46 , etc. to serve as routes for connecting circuits  46  to circuits  48 , etc. In X 2 , X 4  and X 8  levels, the routings are preferably done locally, since the transistors are close to each other. Vertical long distance routing wires are necessary at the X 16  level and above to connect the output of one level to the inputs of the next higher level. For a memory containing 256 words, about ten such vertical routing wires are necessary. Consequently, it is more convenient to standardize the HMGEN circuit as a single standard cell with adequate routing wires for any necessary purpose. 
   In some embodiments, the gate sizes are smaller in the MMDETX 4  circuits than in the HMGEN circuits at the MMDETX 8  level and above. More particularly, the signal nets of the MMDETX 4  level are physically close to each other and the parasitic metal capacitance/resistance is relatively small. Consequently, a small driver is adequate to propagate the hit and multiple hit signals through the MMDETX 4  level. Theoretically, the higher the level, the larger the driver size that is required to propagate the signals. But from layout consideration, it is better to make all HNGEN circuits the same size. In preferred embodiments the circuit is constructed as part of an integrated circuit chip in a technology not greater than 0.18μ, and preferably using 0.13μ technology. 
   With reference to  FIG. 3 , NAND gates  20 ,  24  and  34  of the MMDETX 4  circuits  40  have PMOS/NMOS widths of 1.0μ/1.0μ, NAND gate  36  has a PMOS/NMOS width of 2.0μ/2.0μ, NOR gates  22 ,  26 ,  28  and  32  have PMOS/NMOS widths of 2.0μ/0.5μ, and inverter  30  has a PMOS/NMOS width of 2.0μ/1.0μ. For the HMGEN cell ( FIG. 4 ) each NOR gate has a PMOS/NMOS width of 8.0μ/2.0μ, NAND gate  52  has a PMOS/NMOS width of 4.0μ/4.0μ, NAND gate  54  has a PMOS/NMOS width of 8.0μ/8.0μ, and inverter  48  has a PMOS/NMOS width of 8.0μ/4.0μ. 
   From the circuits of  FIGS. 2-4 , it is evident that each logic level generates an M output signal as well as an H signal. Consequently, the hit signal H and the multiple-hit signal M are generated simultaneously at each level. 
   The layout of the multiple match detection circuit starts with a plurality of MMDETX 4  cells, each having a height of four rows, each of the four inputs to each MMDETX 4  cell being connected to a respective hitline of the CAM. Thus, there are at least N/4 MDMETX 4  cells. If N is not a number which is evenly divisible by 4, then the number of MMDETX 4  cells considered is equal to the next number that is greater than N and evenly divisible by 4. HMGEN cells (shown in  FIG. 4 ) are built to a height of 4 rows and placed in the second column (as shown in  FIGS. 5-7 ). Respective HMGEN cells are connected to two respective MMDETX 4  cells (in the first column) or to two respective HMGEN cells (in the second column). Only two columns of circuit are necessary. 
   One feature of the invention is that only two basic circuits are necessary to form a multiple hit detection circuit, namely the MMDETX 4  cell  40  and the HMGEN cell  44 . Expansion of the circuit to accommodate the capacity of the CAM is accomplished by coupling plural copies of cells  40  and  44 , with local and/or vertical routing wires, as herein described. 
   If the number of words N is not equal to some whole number power of 2, the circuit is designed using a number of words equal to N+M, where M is the lowest number of words beyond the capacity (N) of the CAM such that N+M=2 x  and x is a whole natural number. The cells dedicated exclusively to the M words may be eliminated, and the inputs of cells dedicated exclusively to the M words may be defaulted to a not hit value. 
   A multiple match detection circuit according to the present invention for a CAM containing 256 words in 0.13μ technology will not create significant RC delays. The critical path of the 256-word MMDET circuit is 15 NAND, NOR and/or inverter gates (three gates for the MMDETX 4  gate and two gates for each of the six logic levels of HMGEN gates). The delay is actually smaller than some dynamic analog multiple match detection circuits. 
   The present multiple match detection circuit is physically robust and less sensitive to process variations due to the static logic employed. There are no timing issues because the circuit uses no clock signals. Analog detection circuits required all input signals to be present before the comparator can be enabled by the clock signal, thereby adding to the delay of analog circuits; the present multiple match detection circuit does not employ a clock so logical functions are generated as soon as the inputs permit. Nor are there charge-sharing problems as in some analog circuits. 
   The present invention is particularly useful for content addressable memories requiring multiple match detection. 
   Although the present invention has been described with reference to preferred embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.