Abstract:
In one embodiment, a CAM is provided that includes; a plurality of memory cells grouped to store a word, wherein the memory cells are organized into a plurality of ripple groups, each ripple group including a complex logic gate configured to determine whether a stored content for the ripple group&#39;s memory cells matches a corresponding portion of a comparand word if an enable input for the ripple group is asserted, each complex logic gate asserting an output if the determination indicates a match, the ripple groups being arranged from a first ripple group to a last ripple group such that the output from the first ripple group&#39;s complex logic gate functions as the enable input for a second ripple group&#39;s complex logic gate and so on such that an output from a next-to-last ripple group&#39;s complex logic gate functions as the enable input for the last ripple group&#39;s complex logic gate.

Description:
RELATED APPLICATION 
     This application claims the benefit of U.S. Provisional Application No. 60/760,255, filed Jan. 19, 2006. 
    
    
     TECHNICAL FIELD 
     This application relates to content address memory (CAM), and more particularly to a CAM adapted for low-power consumption. 
     BACKGROUND OF THE INVENTION 
     In conventional memories such as a random access memory (RAM) or a read only memory (ROM), data is stored at particular locations denoted as addresses. To retrieve data, a user specifies the associated address. For high-speed searches, such an approach creates a bottleneck in that the addresses are examined sequentially before the desired data can be retrieved. As a result, content addressable memory (CAM) was developed that operates in an opposite fashion to conventional memories. In other words, a user provides data to a CAM, which returns the associated address. Just like RAM/ROM, data storage in a CAM is organized into words. The word size is arbitrary. For example, a CAM may be organized to store 4-byte words (the length of each word typically denoted as the “width” of the corresponding CAM). Similarly, the number of words in any given CAM is also arbitrary (the number of words typically denoted as the “depth” of the corresponding CAM). A user thus presents a word to a CAM, which then compares the presented word simultaneously to all its stored words. 
     This simultaneous comparison across all stored words in CAM results in a search time that is much faster than comparable RAM/ROM operation. The results of the simultaneous comparison at each stored word in a CAM are typically expressed in the voltage of corresponding “match” lines. Each stored word may have its own corresponding match line. Prior to the comparison, each match line is typically charged to the CAM&#39;s internal supply voltage, VDD. If the presented word (typically denoted as the “comparand” word) does not match the stored word, the corresponding match line is discharged to ground. Thus, the vast majority of match lines are discharged in a typical CAM search. These match lines may be denoted as “unmatched” match lines. Although the parallel search across all stored words is thus speedy, a problem is presented because of the charge being wasted as each unmatched match line is discharged. Moreover, if the word size is increased, the capacitance (and hence stored charge) of each match line increases. Thus, a relatively large amount of power may be wasted in conventional CAM designs. 
     Power consumption is not the only problem with conventional CAM design. Because the capacitance of each match line can be relatively large, the amount of time it takes to pull each unmatched match line to ground can be relatively long. Thus, the speed advantage of CAM searches would be hampered if a “full-swing” (VDD or ground) decision as to the state (matched or unmatched) of each match line is made. Thus, conventional CAMs typically employ sophisticated sense amplifiers that do not need a full voltage swing to make a match decision. For example, such a sense amplifier may declare a match line to be unmatched if it senses that the voltage has dropped some fraction (e.g., 200 to 300 millivolts) below VDD. Such sensitive limited-swing (less than full swing) sense amplifiers are unreliable compared to a full-swing sense amplifiers because of their reduced margin for error. In addition, limited-swing sense amplifiers demand considerably more power. 
     Accordingly, there is a need in the art for improved CAM architectures that provide more power-efficient searches while demanding less die area. 
     SUMMARY 
     This section summarizes some features of the invention. Other features are described in the subsequent sections. 
     In accordance with an embodiment of the invention, a CAM is provided that includes a plurality of memory cells grouped to store a word, wherein the memory cells are organized into a plurality of ripple groups, each ripple group including a complex logic gate configured to determine whether a stored content for the ripple group&#39;s memory cells matches a corresponding portion of a comparand word if an enable input for the ripple group is asserted, each complex logic gate asserting an output if the determination indicates a match, the ripple groups being arranged from a first ripple group to a last ripple group such that the output from the first ripple group&#39;s complex logic gate functions as the enable input for a second ripple group&#39;s complex logic gate and so on such that an output from a next-to-last ripple group&#39;s complex logic gate functions as the enable input for the last ripple group&#39;s complex logic gate. 
     In accordance with another aspect of the invention, a CAM memory cell is provided that includes: an SRAM cell adapted to store a bit; a data line adapted to provide a corresponding comparand bit; an XOR gate adapted to XOR the stored bit and the comparand bit to provide an XOR output, and a switch adapted to close in response to the XOR output. 
     In accordance with another aspect of the invention, a CAM is provided that includes a plurality of memory cells arranged into ripple groups from a first ripple group to a last ripple group, each ripple group having an output node, the first ripple group being adapted to assert its output node if a content of its memory cells match a corresponding portion of a comparand word, each ripple group subsequent to the first ripple group being adapted to assert its output node only if both a content of its memory cells match a corresponding portion of the comparand word and the preceding ripple group has asserted its output node. 
     The scope of the invention is defined by the claims, which are incorporated into this section by reference. A more complete understanding of embodiments of the present invention will be afforded to those skilled in the art, as well as a realization of additional advantages thereof, by a consideration of the following detailed description of one or more embodiments. Reference will be made to the appended sheets of drawings that will first be described briefly. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a high-level conceptual diagram of a CAM in accordance with an embodiment of the invention; 
         FIG. 2  is a more detailed diagram of the first and second ripple groups in the CAM of  FIG. 1 . 
         FIG. 3  is a circuit diagram of first and second ripples groups of  FIG. 2  according to an embodiment of the invention; 
         FIG. 4  is a circuit diagram of first and second ripples groups of  FIG. 2  according to an embodiment of the invention; 
         FIG. 5  is a circuit diagram of a CAM memory cell without a masking bit in accordance with an embodiment of the invention; 
         FIG. 6  is a circuit diagram of a CAM memory cell having a masking bit in accordance with an embodiment of the invention; 
         FIG. 7  is a circuit diagram of a CAM memory cell without a masking bit in accordance with an embodiment of the invention; and 
         FIG. 8  illustrates a portion of the CAM memory cell of  FIG. 7  modified to include a masking bit. 
     
    
    
     Embodiments of the present invention and their advantages are best understood by referring to the detailed description that follows. It should be appreciated that like reference numerals are used to identify like elements illustrated in one or more of the figures. 
     DETAILED DESCRIPTION 
     Reference will now be made in detail to one or more embodiments of the invention. While the invention will be described with respect to these embodiments, it should be understood that the invention is not limited to any particular embodiment. On the contrary, the invention includes alternatives, modifications, and equivalents as may come within the spirit and scope of the appended claims. Furthermore, in the following description, numerous specific details are set forth to provide a thorough understanding of the invention. The invention may be practiced without some or all of these specific details. In other instances, well-known structures and principles of operation have not been described in detail to avoid obscuring the invention. 
     As described previously, conventional CAM searches are speedy but waste power. To address the need in the art for improved power consumption in CAMs, a CAM is disclosed that employs a “ripple” search across each stored word. In exemplary embodiments, each stored word is arranged into groups of bits, which may be denoted as “ripple groups.” A given ripple group will compare its contents to the corresponding comparand bits only if the preceding ripple group has declared a match. In this fashion, a match will ripple across the ripple groups. The default state of each ripple group output (match node) is a mismatch. Because a given ripple group will not compare its contents unless the preceding ripple group has declared a match, considerable power savings are obtained over conventional CAM architectures. Moreover, because the default output is a mismatch, the disclosed CAMs may efficiently be used in applications such as, for example, triggering a wordline in an output table lookup. 
     Turning now to  FIG. 1 , a conceptual diagram of an improved CAM architecture  100  is illustrated. In this architecture, each stored word in the CAM is stored across a plurality of “ripple groups”  105  arranged in sequence. For illustration clarity, the ripple groups for just one stored word are illustrated, the remaining stored words being analogous. Each ripple group includes a complex logic gate  109  having an enable input. Each complex logic gate may function as an OR gate if its enable input is asserted. Because the first ripple group  105 [1] has no preceding ripple group, its enable input is a control signal  115 . The remaining ripple groups have their enable input controlled by an OR output of the preceding ripple group. For example, a second ripple group  105 [2] receives an OR output OR[1] from the first ripple group. Similarly, a final ripple group  105 [n] receives an OR output OR[n−1] from the preceding (n−1)th ripple group (not illustrated). In one embodiment, each OR gate may be implemented as a NOR gate  110  followed by an inverter  111 . If an enable input is true, then the corresponding complex logic gate functions as a NOR gate/inverter combination with respect to its remaining input signals, which are designated as matchx(1) through matchx(n). These input signals may represent the complement of a comparison between a stored bit and a corresponding comparand bit. For example, each ripple group may include a plurality of CAM memory cells (not illustrated) wherein each CAM memory cell is adapted to provide a corresponding matchx input signal to its ripple group&#39;s NOR gate. If the stored bit matches the comparand bit, the matchx input signal is false. Conversely, if the stored bit mismatches the comparand bit, the matchx input signal is true. Both the number of CAM memory cells per ripple group and the total number of ripples groups may be varied to suit individual design needs. For example, suppose the CAM word size is 128 bits. In such an embodiment, each 128-bit word may be distributed across eight ripple groups storing 16 bits each. 
     Each ripple group&#39;s NOR gate will only be enabled if the previous ripple group has declared a match. Thus, if any preceding ripple group to a given ripple group has a mismatch (the NOR output being false), the given ripple group&#39;s NOR gate will not be enabled such that its output cannot change state. In contrast, a prior art CAM match line may be thought of as the collection of all the NOR output nodes in CAM  100 . In this prior art CAM, (assuming there is not a match for a given stored word) these output nodes are all pulled to ground after being charged to VDD, thereby wasting charge. 
     Operation of CAM  100  may be better understood through discussion of  FIG. 2 , which provides a more detailed view of ripple groups  105 [1] and  105 [2]. For illustration clarity, only a first ripple group  105 [1] and a second ripple group  105 [2] are shown. Each ripple group includes a plurality of CAM memory cells  110 . For example, an ith memory cell  110   i  is shown for first ripple group  105 [1]. Each CAM memory cell compares its stored bit to the corresponding comparand bit using, for example, an XOR gate  115  to provide an XOR output. These XOR outputs are true if the corresponding stored bit and comparand bit do not match. As used herein, a signal is said to be “asserted” if that signal is logically true, regardless of whether the signal is active high or active low. Similarly, a signal is denoted as “de-asserted” if that signal is logically false, regardless of whether the signal is active high or active low. 
     If the corresponding stored bit and the comparand bit match, the XOR output is false. The logical state of the XOR outputs may control the logical state of an OR node and a NOR node in each ripple group as follows. Prior to a ripple operation, the OR and NOR nodes are pre-charged to a power supply voltage VDD. For example, in the first ripple group  105 [1], a pre-charge circuit  125  controlled by a clock  120  charges a node OR[1] and a node NOR[1] to VDD. In one embodiment, the pre-charge occurs while the clock is low (subsequent to the falling edge). Subsequent to the clock rising edge, the pre-charge circuitry allows these nodes to float. 
     Prior to the clock rising edge, all the XOR gates have performed their comparison. Responsive to this comparison, each XOR output controls a corresponding switch  120  coupled between nodes x and y. It may thus be seen that if the stored bit and the comparand bit have the same binary state, the corresponding switch will remain open. However, if the bits do not match, the switch closes to couple an “OR” node from the preceding ripple group to the ripple group&#39;s NOR node. To begin the ripple operation, an OR[0] node is discharged to ground through a switch  130  controlled by the clock. Should any of the stored bits in the first ripple group not match the corresponding comparand bit, the corresponding switch  120  will close, thereby grounding node NOR[1]. Each NOR node thus functions as the logical NOR of its ripple group&#39;s XOR outputs. For example, node NOR[1] functions as a logical NOR of the XOR outputs in the first ripple group. Within each ripple group, an inverter  135  drives an OR node in response to receiving the NOR output. For example, in the first ripple group node OR[1] is the complement of node NOR[1]. The ground for each inverter is the preceding OR node. For example, in ripple group  105 [1], the inverter&#39;s ground is the OR[0] node. 
     If OR[1] is false (thereby pulled low in an active high system) so as to indicate a match for all bits in the first ripple group, switches  120  in the subsequent ripple group  105 [2] may affect node NOR[2]. It may thus be seen that the OR input to a given ripple group acts as the enable input signal discussed with regard to  FIG. 1 . If an OR input remains at VDD because of a mismatch in a preceding ripple group, a given ripple group&#39;s NOR node remains charged to VDD. It will be appreciated that before a ripple operation takes place, the CAM memory cell should have performed its comparison operation such that their XOR outputs are either true or false. 
     Note the advantages of such a ripple operation—should the first ripple group include one or more stored bits that do not match the corresponding comparand bits, only node NOR[1] is discharged. Because of the mismatch, all the subsequent NOR nodes remain charged. Conversely, if all the bits match in the first ripple group, the ripple operation “ripples” to the second ripple group (the subsequent ripple group). It may thus be generalized that for the ith ripple group, its NOR node can only be discharged if all the preceding ripple groups&#39; stored bits match the corresponding comparand bits. Moreover, because the OR output from the last ripple group ( FIG. 1 ) is default high, this OR output may be used directly to drive a wordline in an output memory (not illustrated). In this fashion, high speed operation is enabled. 
     The ripple groups may be implemented in numerous alternative embodiments. For example, a first ripple group implementation is illustrated in  FIG. 3 . Each ripple group  105  includes a plurality of CAM memory cells  110  coupled between node labeled “x” and a node labeled “y.” These x and y nodes correspond to those indicated in  FIG. 2 . As discussed with regard to  FIG. 2 , each CAM memory cell may function as an XOR of its stored bit and the corresponding comparand bit. If the XOR indicates a mismatch (the XOR result being true), the CAM memory cell connects node x to node y. Conversely, if the XOR result indicates a match (the XOR result being false), the CAM memory cell isolates node x from node y. The y nodes tie to the NOR nodes. Thus, in a first ripple group  105 [1], a node NOR[1] ties to the y nodes of its CAM memory cells. Similarly, in a second ripple group  105 [2], a node NOR[2] ties to the y nodes of this ripple group&#39;s CAM memory cells, and so on. 
     The ripple comparison of the word stored in the CAM memory cells across all the ripple groups to the comparand word is triggered by a clock  120 . For example, CAM  100  may be responsive to the rising edge of clock  120 . However, it will be appreciated that other embodiments could be responsive to the clock falling edge. The first ripple group  105 [1] has a node OR[0] tied to the complement of the clock, clkx  115 . Thus, prior to the rising edge of clock  120 , node OR[0] is charged to VDD. However, after a rising edge of clock  120 , node OR[0] is pulled low. 
     To perform the pre-charge of the OR nodes, each ripple group may include a PMOS transistor MP 1  having its drain tied to the corresponding OR node and its source tied to a power supply node VDD. The gate of MP 1  is driven by the clock such that prior to the clock rising edge, MP 1  conducts so as to charge the OR node to VDD. The OR node in each ripple group functions as the logical complement of the NOR node in the same ripple group. For example, node OR[2] in second ripple group  105 [2] functions as the complement of node NOR[2]. This inversion may occur by tying a ripple group&#39;s NOR node to a gate of an NMOS transistor MN 1 . If a NOR node is high, then MN 1  is conducting, which brings the corresponding OR node low as follows. Referring back to  FIG. 2 , it may be seen (in the case of a match) that all the OR nodes of all the ripple groups would have to be pulled to ground through switch  130 . To provide a more local and direct path to ground, each ripple group may include a NOR gate  300  that receives the clock complement clkx and the preceding ripple group&#39;s OR output. Subsequent to a clock rising edge (clkx being low), should the preceding OR output be pulled low, an output  305  of NOR gate  300  will go high. Output  305  controls the gate of an NMOS transistor MN 2 . Thus, if the preceding OR node is low and transistor MN 1  conducting (indicating a match in the corresponding ripple group), a path is provided to drain a given ripple group&#39;s OR node to ground. Conversely, should output  305  be high, this output functions to maintain the preceding OR node high by controlling a gate of a PMOS transistor MP 3  stacked in series with a PMOS transistor MP 4  between a power supply node VDD and the preceding OR node. The gate of transistor MP 4  is controlled by the preceding ripple group&#39;s NOR output. Transistor MP 4  is the complement to MN 1  in that if a ripple group&#39;s NOR node is low, MP 4  conducts so that the power supply voltage VDD is applied to the source of transistor MP 3 . In turn, because MP 3  will be conducting, the ripple&#39;s group OR node will be maintained at VDD (in contrast to the ripple group&#39;s NOR node, which is grounded). 
     The pre-charging of the NOR nodes occurs analogously to the pre-charging of the OR nodes. For example, each NOR node may tie to the drain of a PMOS transistor MP 2  whose source ties to the power supply node VDD. The clock drives the gate of MP 2  such that MP 2  conducts prior to the clock rising edge, thereby charging the corresponding NOR node to VDD. 
     An alternative ripple group embodiment is illustrated in  FIG. 4 . In this embodiment, a ripple group&#39;s memory cells have their x nodes isolated from the preceding ripple group&#39;s OR node by an inverter  400  and a NAND gate  405 . For example, should all the bits match in the first ripple group  105 [1], node OR[1] will be low during a ripple operation (after the rising edge of clock  120 ). Inverter  400  inverts this value and provides a true input to NAND gate  405 . NAND gate  405  also receives clock  120 , which is high during the ripple operation. Thus, an output  410  of NAND gate  405  will be low in response to these conditions. Output  410  is tied to an “eval” node of the corresponding ripple gate. For example, in the second ripple group  105 [2], output  410  is tied to a node eval[2]. The eval node acts as the “x” inputs to each of the memory cells. It follows that if the clock is high and the preceding ripple group&#39;s OR output is low for a given ripple group, the given ripple group&#39;s x inputs are also low. In this fashion, a NOR node may be pulled to ground during a ripple operation producing a match as discussed previously. Each NOR node controls the gate of a series-connected PMOS transistor MP 5  and an NMOS transistor MN 3 . If a NOR node is high (indicating a match for the corresponding ripple group&#39;s stored bits), it will drive the corresponding transistor MN 3  to conduct so that the corresponding OR node is drained to ground. Conversely, if a NOR node is low (indicating a mismatch for the corresponding ripple group&#39;s stored bits), it will drive the corresponding transistor MP 5  to conduct so that the corresponding OR node is maintained at VDD. Transistors MP 1  and MP 2  function as described with regard to  FIG. 3  to precharge the OR and NOR nodes. A local path to ground for the OR node of each ripple group is provided through inverter  400 . 
     If a NOR node is pulled low, it will drive the corresponding transistor MP 5  to conduct, thereby maintaining the corresponding OR node to remain high. In this fashion, the complement relationship between corresponding NOR/OR nodes is maintained. 
     Given this ripple group architecture, embodiments of CAM memory cells that function to provide the XOR gate output discussed with regard to  FIG. 2  will now be discussed. A first memory cell embodiment  500  is illustrated in  FIG. 5 . Cell  500  includes a conventional 6-T static random access memory (SRAM) cell  505  represented by cross-coupled inverters  510  and  515 . A word line w drives an NMOS transistor MN 4  to couple a “q” node to a bit line b. Similarly, word line  520  drives an NMOS transistor MN 5  to couple a “qx” node to a bit complement line bx. The comparand bit is carried on a data line d and in complement form on a complement data line dx. 
     Data line d drives a gate of a PMOS transistor MP 6 . Similarly, data line dx drives a gate of a PMOS transistor MP 7 . The comparison operation occurs as follows. Suppose the data line is high whereas the q node is low (indicating a mismatch). In such a case, MP 7  will conduct the high value at node qx to a common drain node (denoted as “mismatch” node) between transistors MP 6  and MP 7 . This active high mismatch node drives a gate of an NMOS transistor MN 6  coupled between nodes x and y. In this fashion, node x will couple to node y in response to this mismatch. An analogous operation occurs for the complement mismatch (node q being high while data line d is low). Prior to a comparison operation, lines d and dx are pre-charged to VDD. Because these lines control the gates of NMOS transistors MN 7  and MN 8 , the mismatch node is pulled to ground. This grounded state does not change if, however, the stored bit in the SRAM cell and the comparand bit match. For example, suppose d and q are both high such that qx and dx are both low. Neither transistors MP 6  or MP 7  are conducting in such a case. A similar operation occurs if both q and d are low. It will be appreciated that, rather than have separate bit and data lines, the bit lines may also function as the data lines. Each embodiment has its own advantages. For example, if the bit lines also function as data lines, routing overhead is reduced. However, if the bit lines and the data lines are separated, capacitive loading is reduced. As yet another alternative embodiment, transistors MN 7  and MN 8  may be eliminated. However, the mismatch node reliability may then be affected. 
     Turning now to  FIG. 6 , a CAM memory cell  600  that provides a masking property is illustrated. SRAM cell  505  couples to the bit lines through transistors MN 4  and MN 5  as discussed previously. Similarly, data lines d and dx drive the gates of transistors MP 6  and MP 7 , respectively, as also discussed with regard to  FIG. 5 . A masking bit is stored in an SRAM cell  601  formed using cross-coupled inverters  605  and  610 . Cell  601  may be written to through bit lines b[0] and bx[0] using NMOS transistors MN 8  and MN 9 , respectively. A complement node qx[0] of cell  601  controls a PMOS transistor MP 8  coupled to the drains of transistors MP 6  and MP 7 . Thus, if cell  601  stores a logical “1” such that qx[0] is low, transistor MP 8  conducts, thereby allowing the control of the mismatch node analogously as discussed with regard to  FIG. 5 . Alternatively, if cell  601  stores a logical “0” such that node qx[0] is high, the mismatch node will stay low regardless of whether a match or mismatch condition exists. In this fashion, bits in a stored word may be disregarded or ignored during a comparison operation. As discussed previously, the mismatch mode may be pulled low during a pre-charge state through operation of transistors MN 7  and MN 8 . Cell  600  may be modified into alternative embodiments as discussed with respect to  FIG. 5 . 
     Turning now to  FIG. 7 , a CAM memory cell  700  is illustrated that uses fewer transistors than cell  500 . In addition, the data lines d and dx receive less capacitive loading. Moreover, cell  700  uses less power. Cell  700  includes a memory cell  505  formed using cross-coupled inverters  510  and  515  as discussed with regard to cell  500 . In addition, cell  700  includes transistors NN 4  and MN 5  coupled between the memory cell and the bit and word lines as also discussed with regard to cell  500 . However, nodes q and qx drive the gates of PMOS transistors MP 6  and MP 7 , respectively. A first terminal for transistors MP 6  and MP 7  couple to data lines d and dx, respectively. A second terminal for transistors MP 6  and MP 7  both couple to the mismatch node. Prior to a comparison operation, data lines d and dx are discharged to ground. Because one of MP 6  or MP 7  will be on depending upon the values of q and qx, the mismatch mode will be pulled to the corresponding PMOS threshold voltage. During the comparison operation, either d or dx becomes charged to VDD. If there is a mismatch, this high voltage will couple through either MP 6  or MP 7  to charge the mismatch node high. However, if there is no mismatch, the mismatch node will stay at the threshold voltage. Because this threshold voltage (due to design mismatches or other uncertainties) may be too high so as to allow MN 6  to conduct slightly despite a match condition, the x node may be coupled to the mismatch node through a capacitor C. Thus, when the x node is pulled low, the mismatch node will also be pulled slightly lower, thereby ensuring that that MN 6  does not conduct significantly during a match condition. The capacitor may be implemented using an NMOS transistor or a metal layer capacitor. 
     It will be appreciated that cell  700  may be modified analogously as discussed with regard to cell  600  to include a masking bit so as to form a ternary memory cell. However, as seen in  FIG. 8 , the qx[0] output of the masking bit memory cell should drive the gates of a series-connected PMOS transistor MP 8  and an NMOS transistor MN 7 . The common terminal between MP 8  and MN 7  couples to the mismatch node. Thus, if the masking memory cell (not illustrated) stores a “1” such that qx[0] is low, the comparison operation discussed with regard to  FIG. 7  is enabled. Conversely, if the masking memory memory cell stores a “0” such that qx[0] is high, the comparison operation is prevented in that the mismatch node is grounded through MN 7 . 
     The above-described embodiments of the present invention are merely meant to be illustrative and not limiting. It will thus be obvious to those skilled in the art that various changes and modifications may be made without departing from this invention in its broader aspects. Therefore, the appended claims encompass all such changes and modifications as fall within the true spirit and scope of this invention.