Abstract:
The present invention provides a content addressable memory (CAM) match detection circuit that maintains traditionally achieved levels of accuracy while greatly reducing the amount of power dissipated. In accordance with an exemplary embodiment of the invention, rather than allowing the Matchline voltage to swing between a precharge voltage level (e.g., VDD) and Ground, the Matchline voltage is restricted to swinging between the precharge voltage level (e.g., VDD) and a Negative Reference voltage level that is lower than the precharge voltage level but higher than Ground.

Description:
[0001]    This application claims the benefit of U.S. Provisional Application No. 60/324,365 filed Sep. 24, 2001, the content of which is incorporated herein in its entirety. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    The present invention relates generally to semiconductor memory, and more particularly to a match detection circuit for a content addressable memory.  
         BACKGROUND OF THE INVENTION  
         [0003]    A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data being stored within a given memory location) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.  
           [0004]    In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.  
           [0005]    In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected bib an address bus, or the data can be written into the first empty memory location. Every location has a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.  
           [0006]    Once information is stored in a memory location, it is found by comparing every bit in memory with data placed in a match detection circuit. When the content stored in the CAM memory location does not match the data placed in the match detection circuit, the CAM device returns a no match indication. When the content stored in the CAM memory location matches the data placed in the match detection circuit, the CAM device returns a match indication. In addition, the CAM may return the identification of the address location in which the desired data is stored. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memoir.  
           [0007]    Locally, CAMs perform an exclusive-NOR (XNOR) function, so that a match is indicated only if both the stored bit and the corresponding input bit are the same state. CAMs are designed so that any number of stored bits may be simultaneously detected for a match with the input bits in the match detection circuit. One way in which this is achieved is by coupling a plurality of storage devices and logic circuits to a common Matchline, as depicted in FIG. 1.  
           [0008]    Turning to FIG. 1, a schematic diagram of a conventional match detection circuit  100  is depicted. A first source/drain terminal of a precharge transistor  102  is coupled to a positive voltage source (e.g., VDD). The gate of transistor  102  is coupled to a signal line  138  for receiving a Precharge signal. A second source/drain terminal of transistor  102  is coupled to a Matchline  140  for precharging the Matchline  140  to a predetermined voltage level (e.g., VDD).  
           [0009]    Respective outputs Q 0 , Q 1 , Q n−1  of storage elements  104 ,  114 ,  124 , which are to be respectively compared with the input bits B 0 , B 1 , B n−1  are respectively coupled to gates of transistors  106 ,  116  and  126 . First respective source/drain terminals of transistors  106 ,  116  and  126  are coupled to the Matchline  140 .  
           [0010]    Second respective source/drain terminals of transistors  106 ,  116  and  126  are respectively coupled to transistors  110 ,  120  and  130 . Second respective source/drain terminals of transistors  110 ,  120  and  130  are coupled to ground. The gates of transistors  110 ,  120  and  130  are respectively coupled to complements B 0 ′, B 1 ′ and B n−1 ′ of the respective input bits.  
           [0011]    Further, the respective complements of the outputs Q 0 ′, Q 1 ′ and Q n−1 ′ of the storage elements  104 ,  114  and  124  are respectively coupled to gates of transistors  108 ,  118  and  128 . First respective source/drain terminals of transistors  108 ,  118  and  128  are coupled to the Matchline  140 . Second source/drain terminals of transistors  108 ,  118  and  128  are respectively coupled to first source/drain terminals of transistors  112 ,  122  and  132 . Second respective source/drain terminals of transistors  112 ,  122  and  132  are coupled to ground. The gates of transistors  112 ,  122  and  132  are respectively coupled to the input bits B 0 , B 1  and B n−1  to be respectively compared with the complements Q 0 ′, Q 1 ′ and Q n−1 ′ of the stored bits being stored in storage elements  104 ,  114  and  124 .  
           [0012]    Also coupled to the Matchline  140  is a buffer  136  for buffering the Matchline  140  voltage and for outputting the Match signal. A Match signal of logic HIGH (e.g., VDD) represents that an exact match was detected between the input bits B 0 , B 1 , B n−1  and the stored bits Q 0 , Q 1 , Q n−1 . A Match signal of logic LOW (e.g., Ground) represents that at least one bit of the stored bits did not match its corresponding input bit causing the Matchline to be pulled to Ground. Capacitor  134  represent the parasitic capacitance of the Matchline  140  that is precharged to the initial predetermined value (e.g., VDD).  
           [0013]    During operation of the FIG. 1 match detection circuit  100 , the Precharge signal goes logic HIGH then logic LOW in order to precharge the Matchline  140  to VDD. The state of the stored bits Q 0 , Q 1 , Q n−1  stored by the respective storage elements  104 ,  114 ,  124  and their complements Q 0 ′, Q 1 ′, Q n−1 ′ are respectively coupled to the gates of p-type transistors  106 ,  116 ,  126 ,  108 ,  118 ,  128 . Consequently, depending upon the states at their respective gates, the transistors  106 ,  116 ,  126 ,  108 ,  118 ,  128  may become active and conduct.  
           [0014]    Similarly, the state of the input bits B 0 , B 1 , B n−1  and their complements B 0 ′, B 1 ′, B n−1 ′ are coupled to the gates of p-type transistors  112 ,  122 ,  132 ,  110 ,  120 ,  130 . Consequently, depending upon the states at their respective gates, the transistors  112 ,  122 ,  132 ,  110 ,  120 ,  130  may become active and conduct.  
           [0015]    When a match is detected, at least one transistor of each serially connected pair of transistors (e.g.,  106  and  110 ,  108  and  112 , etc.) is inactive and not conducting. Therefore, when the Matchline  140  remains logic HIGH, this signifies to the outside world that a match has been detected and potentially enables any other functions desired when a match is detected (e.g., provide the user with the address of the memory location where the match as found, forward the data to another location, etc.).  
           [0016]    However, when a mismatch is detected, as is most often the case during a search for a particular bit pattern, at least one pair of serially connected transistors (e.g.,  106  and  110 ) is active and conducting and the Matchline  140  is coupled to Ground. When the Matchline  140  is coupled to Ground, the Match signal goes logic LOW and signifies to the outside world that a mismatch has been detected in this particular series of storage elements  104 ,  114 ,  124 .  
           [0017]    In the above-identified search process, the searched data (i.e., the input bits) is simultaneously compared with every data word in the CAM in order to find a match between the stored data and the input data. Since the comparison operation is conducted simultaneously on the entire memory, and is typically repeated at a very high frequency, this operation consumes a significant amount of power.  
           [0018]    Power dissipation, P, in complementary metal-oxide semiconductor (CMOS) circuits, such as that depicted in FIG. 1, is related to the magnitude of signal swing, V, the load capacitance C, and the frequency of operation F as P=C*F*V 2 . Since the magnitude of signal swing, V, for typical match detection circuits is from VDD to Ground, the power dissipated by the circuit is exceedingly high. Therefore, it is desirable to find a way to reduce power dissipation of CAM match detection circuits while maintaining the same levels of accuracy.  
         BRIEF SUMMARY OF THE INVENTION  
         [0019]    The present invention provides a CAM match detection circuit that maintains traditionally, achieved levels of accuracy while greatly reducing the amount of power dissipated. In accordance with an exemplary embodiment of the invention, rather than allowing the Matchline  140  voltage to swing between a precharge voltage level (e.g., VDD) and Ground, the Matchline voltage is restricted to swinging between the precharge voltage level (e.g., VDD) and a Negative Reference voltage level that is lower than the precharge voltage level but higher than Ground. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0020]    The above and other features and advantages of the invention will be more readily understood from the following detailed description of the invention which is provided in connection with the accompanying drawings.  
         [0021]    [0021]FIG. 1 is a simplified schematic diagram of a conventional match detection circuit;  
         [0022]    [0022]FIG. 2 is a simplified schematic diagram of a match detection circuit, in accordance with an exemplary embodiment of the invention;  
         [0023]    [0023]FIG. 3 is a schematic diagram of a processor system employing the match detection circuit of FIG. 2, in accordance with an exemplar) embodiment of the invention;  
         [0024]    [0024]FIG. 4 illustrates a memory chip containing a CAM array that employs a plurality of FIG. 2 match detection circuits;  
         [0025]    [0025]FIG. 5 depicts a simplified block diagram of a router employing the FIG. 4 memory chip containing a CAM array;  
         [0026]    [0026]FIG. 6 depicts a match detection circuit, in accordance with an exemplary embodiment of the invention;  
         [0027]    [0027]FIG. 7 depicts a portion of the FIG. 2 match detection circuit, in accordance with an exemplary embodiment of the invention;  
         [0028]    [0028]FIG. 8 depicts a portion of the FIG. 2 match detection circuit, in accordance with another exemplary embodiment of the invention;  
         [0029]    [0029]FIG. 9 depicts the FIG. 8 match detection circuit, in accordance with another exemplary embodiment of the invention;  
         [0030]    [0030]FIG. 10 depicts a portion of the FIG. 2 match detection circuit, in accordance with another exemplary embodiment of the invention;  
         [0031]    [0031]FIG. 11 depicts the FIG. 10 match detection circuit, in accordance wraith another exemplary embodiment of the invention;  
         [0032]    [0032]FIG. 12 depicts a portion of the FIG. 2 match detection circuit, in accordance with another exemplary embodiment of the invention; and  
         [0033]    [0033]FIG. 13 depicts the FIG. 12 match detection circuit, in accordance with another exemplary, embodiment of the invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0034]    In the following detailed description, reference is made to the accompanying drawings which form a part hereof, and in which is shown bib way of illustration specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those of ordinary skill in the art to make and use the invention, and it is to be understood that structural, logical or procedural changes may be made to the specific embodiments disclosed without departing from the spirit and scope of the present invention.  
         [0035]    [0035]FIG. 2 depicts a simplified schematic diagram of a CAM match detection circuit  200 , in accordance with an exemplary embodiment of the invention. The configuration of the FIG. 2 match detection circuit  200  differs from that of the FIG. 1 match detection circuit  100  in that the respective second source/drain terminals of transistors  110 ,  112 ,  120 ,  122 ,  130  and  132  are coupled to a common Negative Reference NEGREF voltage line  205 , rather than to Ground.  
         [0036]    The storage elements  104 ,  114 ,  124  mall be any complementary storage element, e.g., a flip-flop storage element, known in the art that provides a logic state of the stored value and its complementary logic state (e.g., Q 0  and Q 0 ′).  
         [0037]    The operation of the FIG. 2 match detection circuit  200  differs from that of the FIG. 1 match detection circuit  100  in that the Matchline  140  voltage swings from the precharge voltage (e.g., VDD) to a Negative Reference voltage NEGREF level when a mismatch is detected. The Negative Reference voltage NEGREF level is supplied on NEGREF line  205  and is a predetermined voltage level between Ground and the precharge voltage (e.g., VDD).  
         [0038]    The Negative Reference NEGREF voltage can be supplied from an independent power source V NEG  external to the CAM that is regulated with a voltage regulator  210  to deliver a desired voltage level. Voltage regulator  210  mall be, for example, a standard voltage regulator such as a 7905 3-terminal negative voltage regulator.  
         [0039]    It should be noted that the present invention does not supplant the Ground connection to the CAM. For example, as depicted in FIG. 2, the Ground connection is still in tact and coupled to VSS. In accordance with an exemplary embodiment of the invention, the CAM match detection circuit  200  is modified such that when a mismatch is detected, the Matchline  140  is driven to a voltage higher than Ground so as to reduce the magnitude of the voltage swing. The reduction in the magnitude of the voltage swing results in exponentially reduced power dissipation levels.  
         [0040]    It is desirable to complete the precharging of the Matchline  140  prior to the time when the input bits B 0 , B 1 , B n−1 , are respectively received at transistors  112 ,  122  and  132 . This ensures that the Matchline  140  is sufficiently charged to its logic HIGH state before the comparison is made between the stored bits and the input bits.  
         [0041]    [0041]FIG. 3 illustrates an exemplary processing system  300  which utilizes the FIG. 2 CAM match detection circuit. The processing system  300  includes one or more processors  301  coupled to a local bus  304 . A memory controller  302  and a primary bus bridge  303  are also coupled the local bus  304 . The processing system  300  may include multiple memory controllers  302  and/or multiple primary bus bridges  303 . The memory controller  302  and the primary bus bridge  303  may be integrated as a single device  306 .  
         [0042]    The memory controller  302  is also coupled to one or more memory buses  307 . Each memory bus accepts memory components  308 . Any one of memory components  308  may contain a CAM array containing a match detection circuit such as the match detection circuit  200  described in connection with FIG. 2.  
         [0043]    The memory components  308  may be a memory card or a memory module. The memory components  308  may include one or more additional devices  309 . For example, in a SIMM or DIMM, the additional device  309  might be a configuration memory, such as a serial presence detect (SPD) memory. The memory controller  302  may also be coupled to a cache memory  305 . The cache memory  305  may be the only cache memory in the processing system. Alternatively, other devices, for example, processors  301  may also include cache memories, which may form a cache hierarchy with cache memory  305 . If the processing system  300  include peripherals or controllers which are bus masters or which support direct memory access (DMA), the memory controller  302  may implement a cache coherency protocol. If the memory controller  302  is coupled to a plurality of memory buses  307 , each memory bus  307  may be operated in parallel, or different address ranges may be mapped to different memory buses  307 .  
         [0044]    The primary bus bridge  303  is coupled to at least one peripheral bus  31 ). Various devices, such as peripherals or additional bus bridges may be coupled to the peripheral bus  310 . These devices may include a storage controller  311 , an miscellaneous I/o device  314 , a secondary bus bridge  315 , a multimedia processor  318 , and an legacy device interface  320 . The primary bus bridge  303  may also coupled to one or more special purpose high speed ports  322 . In a personal computer, for example, the special purpose port might be the Accelerated Graphics Port (AGP), used to couple a high performance video card to the processing system  300 .  
         [0045]    The storage controller  311  couples one or more storage devices  313 , via a storage bus  312 , to the peripheral bus  310 . For example, the storage controller  311  may be a SCSI controller and storage devices  313  may be SCSI discs. The I/O device  314  may be any sort of peripheral. For example, the I/O device  314  may be an local area network interface, such as an Ethernet card. The secondary bus bridge may be used to interface additional devices via another bus to the processing system. For example, the secondary bus bridge may be an universal serial port (USB) controller used to couple USB devices  317  via to the processing system  300 . The multimedia processor  318  may be a sound card, a video capture card, or any other type of media interface, which may also be coupled to one additional devices such as speakers  319 . The legacy device interface  320  is used to couple legacy devices, for example, older styled keyboards and mice, to the processing system  300 .  
         [0046]    The processing system  300  illustrated in FIG. 3 is only an exemplary processing system with which the invention may be used. While FIG. 3 illustrates a processing architecture especially suitable for a general purpose computer, such as a personal computer or a workstation, it should be recognized that well known modifications can be made to configure the processing system  300  to become more suitable for use in a variety of applications. For example, many electronic devices which require processing may be implemented using a simpler architecture which relies on a CPU  301  coupled to memory components  308  and/or memory devices  309 . The modifications may include, for example, elimination of unnecessary components, addition of specialized devices or circuits, and/or integration of a plurality of devices.  
         [0047]    [0047]FIG. 4 depicts a CAM array employing a plurality of match detection circuits  200  such as the one depicted in FIG. 2. The CAM array may be included on a semiconductor memory chip  400  so that it may be incorporated into a processor system such as the one depicted in FIG. 3.  
         [0048]    [0048]FIG. 5 is a simplified block diagram of a router  500  as may be used in a communications network, such as, e.g., part of the Internet backbone. The router  500  contains a plurality of input lines and a plurality of output lines. When data is transmitted from one location to another, it is sent in a form known as a packet. Oftentimes, prior to the packet reaching its final destination, that packet is first received by a router, or some other device. The router  500  then decodes that part of the data identifying the ultimate destination and decides which output line and what forwarding instructions are required for the packet.  
         [0049]    Generally, CAMs are very, useful in router applications because historical routing information for packets received from a particular source and going to a particular destination is stored in the CAM of the router. As a result, when a packet is received by the router  500 , the router already has the forwarding information stored within its CAM. Therefore, only that portion of the packet that identifies the sender and recipient need be decoded in order to perform a search of the CAM to identify which output line and instructions are required to pass the packet onto a next node of its journey.  
         [0050]    Still referring to FIG. 5, router  500  contains the added benefit of employing a semiconductor memory chip containing a CAM array, such as that depicted in FIG. 4. Therefore, not only does the router benefit from having a CAM but also benefits by having a CAM with reduced power dissipation, in accordance with an exemplary embodiment of the invention.  
         [0051]    Turning to FIG. 6, another exemplary embodiment of the invention is depicted. The FIG. 6 match detection circuit  600  differs from the FIG. 2 match detection circuit  200  in that the matchline is precharged to NEGREF, rather than VDD. When a mismatch is detected between a stored bit and an input bit, the matchline is boosted to VDD, rather than NEGREF. In accordance with this exemplary embodiment of the invention, the FIG. 6 match detection circuit  600  has a reduced signal swing as compared with the FIG. 1 match detection circuit  100 .  
         [0052]    Turning to FIG. 7, a portion  700  of the FIG. 2 match detection circuit  200  is depicted to show another orientation of the storage element (e.g.,  104 ) and the input bit (e.g., B 0 ). The operation of the FIG. 7 embodiment is identical to that of the FIG. 2 match detection circuit  200 .  
         [0053]    Turning to FIG. 8, a portion  800  of the FIG. 2 match detection circuit  200  is depicted to show n-type transistors  802 ,  806  coupled to the storage device  104 . N-type transistor  802  is in series with p-type transistor  804  and n-type transistor  806  is in series with p-type transistor  808 . In addition, the true logic state of the stored bit Q 0  and the true logic state of the input bit B 0  are respectively received at gates of transistors  802  and  804 , while complements Q 0 ′, B 0 ′ of the logic state of the stored bit and of the input bit are respectively received at gates of transistors  806  and  808 . When a mismatch is detected between the stored bit Q 0  and the input bit B 0 , the matchline is brought from VDD to NEGREF.  
         [0054]    Turning to FIG. 9, a portion  900  of the FIG. 8 match detection circuit  800  is depicted to show another orientation of the storage element  104  and the input bit B 0 . The operation of the FIG. 9 embodiment is identical to that of the FIG. 8 embodiment.  
         [0055]    Turning to FIG. 10, a portion  1000  of the FIG. 2 match detection circuit  200  is depicted to show n-type transistors  1004 ,  1008  respectively coupled to the input bit B 0  and its complement B 0 ′. N-type transistor  1004  is in series with p-type transistor  1002  and n-type transistor  1008  is in series with p-type transistor  1006 . In addition, the true logic state of the stored bit Q 0  and the true logic state of the input bit B 0  are respectively received at gates of transistors  1002  and  1004 , while complements Q 0 ′, B 0 ′ of the logic state of the stored bit and of the input bit are respectively received at gates of transistors  1006  and  1008 . When a mismatch is detected between the stored bit Q 0  and the input bit B 0 ′, the matchline is brought from VDD to NEGREF.  
         [0056]    Turning to FIG. 11, a portion  1100  of the FIG. 10 match detection circuit  1000  is depicted to show another orientation of the storage element  104  and the input bit B 0 . The operation of the FIG. 11 embodiment is identical to that of the FIG. 10 embodiment.  
         [0057]    Turning to FIG. 12, a portion  1200  of the FIG. 2 match detection circuit  200  is depicted to show n-type transistors  1202 - 1208  in place of p-type transistors  106 - 112 . Here, the true logic state of the stored bit Q 0  as well as the true logic state of the input bit B 0  are respectively received at gates of series connected transistors  1202  and  1204 . The complements Q 0 ′, B 0 ′ of the logic states of the stored bit and the input bit are respectively received at gates of series connected transistors  1206 ,  1208 . When a mismatch is detected between the stored bit Q 0  and the input bit B 0 , the matchline is brought from VDD to NEGREF.  
         [0058]    Turning to FIG. 13, a portion  1300  of the FIG. 12 match detection circuit  1200  is depicted to show another orientation of the storage element  104  and the input bit B 0 . The operation of the FIG. 13 embodiment is identical to that of the FIG. 12 embodiment.  
         [0059]    It is desirable to have a CAM match detection circuit  200  that dissipates less power while maintaining traditionally achieved levels of performance. The present invention accomplishes this by providing a match detection circuit  200  that reduces the magnitude of signal swing when a mismatch is detected. As illustrated by several exemplary embodiments of the invention, the Matchline voltage swings from the predetermined voltage (e.g., VDD) to the NEGREF voltage, where the NEGREF voltage is at a level higher than Ground (0v). Alternatively, in other exemplary embodiments, the matchline voltage swings from NEGREF to VDD. The reduced voltage swing during match detection greatly reduces the power dissipated by each circuit  200 .  
         [0060]    While the invention has been described in detail in connection with preferred embodiments known at the time, it should be readily understood that the invention is not limited to the disclosed embodiments. Rather, the invention can be modified to incorporate any number of variations, alterations, substitutions or equivalent arrangements not heretofore described, but which are commensurate with the spirit and scope of the invention. For example, although the invention has been described in connection with specific circuits employing different configurations of p-type and n-type transistors, the invention may be practiced with many other configurations without departing from the spirit and scope of the invention. Accordingly, the invention is not limited by the foregoing description or drawings, but is only limited by the scope of the appended claims.