Abstract:
Parity and mask bit(s) are stored in a random access memory (RAM) that is coupled to a CAM. This CAM may be part of a TLB. The parity and mask bits(s) are stored in conjunction with the CAM entry write. Upon a CAM query match, the reference parity bit(s) and mask bit(s) stored at the address output by the CAM are output from the RAM. These reference parity bit(s) are compared to parity bit(s) generated from a query data value that is masked by the retrieved mask bit(s). In the absence of a CAM or RAM bit error, the reference parity bit(s) from the RAM and the parity bit(s) generated from the masked query data will match. If a CAM or RAM bit error occurred, these two sets of parity bit(s) will not match and thus an error will be detected. This error may be used as an indication that a false CAM match has occurred.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]    A copending United States patent application commonly owned by the assignee of the present document and incorporated by reference in its entirety into this document is being filed in the United States Patent and Trademark Office on or about the same day as the present application. This related application is: Hewlett-Packard docket number 100200823-1, Ser. No. ______, titled “DETECTION OF BIT ERRORS CONTENT ADDRESSABLE MEMORIES.” 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    This invention relates generally to content-addressable memories (CAMs) and more particularly to detecting bit errors that may occur in the data stored in a CAM.  
         BACKGROUND  
         [0003]    CAM structures perform pattern matches between a query data value and data previously stored in an entry of the CAM. A match causes the address of the matching entry to be output. Bit value errors may occur in CAM entries at any time due to external energy being imparted to the circuit. For example, an alpha particle strike may cause one of the storage elements in a CAM to change state. If this occurs, an incorrect query match may result causing an incorrect address to be output from the circuit. If the CAM address is used to drive a RAM, this error will also cause incorrect data to be output from the RAM. Since the contents of the CAM entries are typically not known external to the CAM, this incorrect (or false) query match may not be detected.  
         SUMMARY OF THE INVENTION  
         [0004]    Parity and mask bit(s) are stored in a random access memory (RAM) that is coupled to a CAM. The parity and mask bits(s) are stored in conjunction with the CAM entry write. Upon a CAM query match, the reference parity bit(s) and mask bit(s) stored at the address output by the CAM are output from the RAM. These reference parity bit(s) are compared to parity bit(s) generated from a query data value that is masked by the retrieved mask bit(s). In the absence of a CAM or RAM bit error, the reference parity bit(s) from the RAM and the parity bit(s) generated from the masked query data will match. If a CAM or RAM bit error occurred, these two sets of parity bit(s) will not match and thus an error will be detected. This error may be used as an indication that a false CAM match has occurred. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0005]    [0005]FIG. 1 is a block diagram illustrating the detection of CAM bit errors.  
         [0006]    [0006]FIG. 2 is a block diagram illustrating the detection of CAM bit errors with maskable bits.  
         [0007]    [0007]FIG. 3 is a flowchart illustrating steps to detect CAM bit errors.  
         [0008]    [0008]FIG. 4 is a flowchart illustrating steps to detect CAM bit errors in a CAM with maskable bits.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0009]    [0009]FIG. 1 is a block diagram illustrating the detection of CAM bit errors. In FIG. 1, arrow  102  represents data being written into CAM  120  at an address represented by arrow  109 . Data  102  is also supplied to a parity generator  122 . Parity generator  122  generates one or more input parity bits  105  from data  102 . The input parity  105  generated by  122  may be a simple single bit parity such as odd or even parity, or a more complex multi-bit parity such as an error correcting code (ECC). The input parity bit(s) generated by parity generator  122  are represented by arrow  105 . The input parity  105  is written into RAM  121  at an address corresponding to the address shown as arrow  109 . Accordingly, after an entry is written in CAM  120  at a particular address, there will be a corresponding input parity entry stored in RAM  121  at a corresponding address.  
         [0010]    When query data is supplied to CAM  120 , CAM  120  may output the address that contains that query data, or indicate that that query data is not in the CAM. In FIG. 1, the query data is represented by arrow  101 . This query data is also supplied to parity generator  123 . In the case of a query match, the address being output by CAM  120  is represented by arrow  103 . The address of the query match  103  is forwarded to RAM  121  to retrieve (at least) the parity stored in the RAM at the corresponding address. The stored parity output by the RAM is represented by arrow  107 . Any additional data stored in RAM  121  at the corresponding address may also be output. This additional data is represented by arrow  104 .  
         [0011]    Parity generator  123  outputs query parity bit(s) represented by arrow  106 . The query parity bit(s)  106  generated by parity generator  123  would typically be the same encoding as those produced by parity generator  122 . However, it may differ from the encoding generated by parity generator  122  by certain inversions, or other transformations etc. depending upon the functioning of parity compare  124  and RAM  121 . Parity bit(s)  106  and stored parity output  107  are compared by a comparator  124 . The results of this compare  108  indicate whether or not there was a bit error in the queried entry in the CAM or in the stored parity corresponding to that entry.  
         [0012]    [0012]FIG. 2 is a block diagram illustrating the detection of CAM bit errors with maskable bits. In FIG. 2, arrow  202  represents data being written into CAM  220  at an address represented by arrow  209 . Data  202  is also supplied to a mask block  225 . Arrow  210  represents input mask bits. Input mask bits  210  are supplied to CAM  220 , mask block  225 , and RAM  221 . Input mask bits  210  are stored in CAM  220  at the same address  209  as data  202  and tell CAM  220  which bits to consider or not consider when determining if a query matches the entry at address  209 .  
         [0013]    Mask block  225  takes data  202  and mask bits  210  and sets certain bits in data  202  to a predetermined value (i.e. logical 1 or 0). The bits that are set to this predetermined value are given by the values of mask bits  210 . For example, if data  202  was four bits wide (and it could be any arbitrary length) and its binary value was “1100” and mask bits  210 &#39;s binary value was “1010” (and 1 was chosen to mean pass, 0 to mean mask), mask block  225  may output “1000”—effectively masking bits  0  and  2  (numbering bits from right-to-left with bit  0  being the rightmost, bit  3  the leftmost) of data  202  to a logical 0. Data  202  could also have been masked to logical 1&#39;s making the mask block output  211  “1101”. Mask block output  211  is supplied to parity generator  222 .  
         [0014]    Parity generator  222  generates one or more input parity bits  205  from mask block output  211 . The input parity  205  generated by  222  may be a simple single bit parity such as odd or even parity, or a more complex multi-bit parity such as an error correcting code (ECC). Note that parity calculations should be limited to those bits which affect or control query matches. This is because errors in masked bits will not result in incorrect matches since masked bits are ignored when determining if there is a match. For example, if data bit  13  is masked in a CAM entry, the parity for that entry should be the same regardless of the value of bit  13  of the query data. Accordingly, bit  13  should be masked before the parity calculation related to that entry. The input parity bit(s) generated by parity generator  222  are represented by arrow  205 . The input parity  205  is written into RAM  221  along with mask bits  210  at an address corresponding to the address shown as arrow  209 . Accordingly, after an entry is written in CAM  220  at a particular address, there will be a corresponding input parity entry and mask bit entry stored in RAM  221  at a corresponding address.  
         [0015]    When query data is supplied to CAM  220 , CAM  220  may output the address that contains that query data  201 , or indicate that that query data  201  is not in the CAM. In FIG. 2, the query data is represented by arrow  201 . This query data is also supplied to mask block  226 . In the case of a query match, the address being output by CAM  220  is represented by arrow  203 . The address of the query match  203  is forwarded to RAM  221  to retrieve (at least) the parity and mask bits stored in the RAM  221  at the corresponding address. The stored parity output by the RAM is represented by arrow  207 . The stored mask bits are represented by arrow  212 . Any additional data stored in RAM  221  at the corresponding address may also be output. This additional data is represented by arrow  204 .  
         [0016]    Mask block  226  takes query data  201  and stored mask bits  212  and sets certain bits in query data  201  to a predetermined value (i.e. logical 1 or 0). The function of mask block  226  is similar to mask block  225 . The output of mask block  226  is represented by arrow  213  and is supplied to parity generator  223 .  
         [0017]    Parity generator  223  outputs query parity bit(s) represented by arrow  206 . The query parity bit(s)  206  generated by parity generator  223  would typically be the same encoding as those produced by parity generator  222 . However, it may differ from the encoding generated by parity generator  222  by certain inversions, or other transformations etc. depending upon the functioning of parity compare  224 , mask blocks  225  and  226 , parity generators  222  and  223 , and RAM  221 . Parity bit(s)  206  and stored parity output  207  are compared by a comparator  224 . The result of this compare  208  indicates whether or not there was a bit error in the queried entry in the CAM  221 , the mask bits either in the CAM  221 , or in the stored parity or mask bits corresponding to that entry.  
         [0018]    [0018]FIG. 3 is a flowchart illustrating steps to detect CAM bit errors. These steps are applicable to the block diagram in FIG. 1, but are not limited to application with only that arrangement of blocks. Other arrangements of blocks may be used to complete these steps. In FIG. 3, in a step  302  input parity is generated on input data that is being written into the CAM. The generated input parity may be a simple single bit parity such as odd or even parity, or a more complex multi-bit parity such as an error correcting code (ECC). In a step  304 , the input data is stored in a CAM at an input address. In a step  306 , the input parity is stored in a RAM at an address that corresponds to the address the input data was stored at in the CAM. In other words, the input parity is stored at an address that, when a query matches in the CAM and the CAM outputs an address, the RAM will output the input parity when the address the CAM outputs is used either directly as an address or as an index to an address that is applied to the RAM&#39;s address inputs.  
         [0019]    In a step  308 , the CAM is queried by supplying the appropriate inputs of the CAM with query data. In a step  310 , query parity is generated on the query data that is being applied to the CAM. This parity algorithm should produce a result that matches the algorithm used in step  302  or only differs by insignificant factors such as an inversion or other insignificant transformations. In a step  312 , a stored parity is retrieved from the RAM by accessing a RAM location that corresponds to the address supplied by the CAM when it was queried in step  308 . In a step  314 , the generated query parity and the stored parity from the RAM are compared. If they match, no bit error in either the CAM contents or RAM stored parity contents has been detected. If they do not match, a bit error in either the CAM contents or RAM stored parity content has been detected.  
         [0020]    [0020]FIG. 4 is a flowchart illustrating steps to detect CAM bit errors in a CAM with maskable bits. These steps are applicable to the block diagram in FIG. 2, but are not limited to application with only that arrangement of blocks. Other arrangements of blocks may be used to complete these steps. In FIG. 4, in a step  401 , the input data is masked according to a set of mask bits. In a step  402  input parity is generated on the masked input data from step  401 . The generated input parity may be a simple single bit parity such as odd or even parity, or a more complex multi-bit parity such as an error correcting code (ECC). Note that parity calculations should be limited to those bits which affect or control query matches. For example, if data bit  13  is masked in a CAM entry, the parity for that entry should be the same regardless of the value of bit  13  of the query data. Accordingly, bit  13  should be masked before the parity calculation related to that entry. In a step  404 , the input data and the set of mask bits are stored in a CAM at an input address. In a step  406 , the input parity and the set of mask bits are stored in a RAM at an address that corresponds to the address the input data was stored at in the CAM. In other words, the input parity and mask bits are stored at an address that, when a query matches in the CAM and the CAM outputs an address, the RAM will output the input parity and mask bits when the address the CAM outputs is used either directly as an address or as an index to an address that is applied to the RAM&#39;s address inputs.  
         [0021]    In a step  408 , the CAM is queried by supplying the appropriate inputs of the CAM with query data. In a step  412 , a stored parity and stored mask bits are retrieved from the RAM by accessing a RAM location that corresponds to the address supplied by the CAM when it was queried in step  408 . In a step  413 , the query data is masked according to the stored mask bits retrieved in step  412 . In a step  410 , query parity is generated on the masked query data from step  413 . This parity algorithm should produce a result that matches the algorithm used in step  402  or only differs by insignificant factors such as an inversion or other insignificant transformations. In a step  414 , the generated query parity and the stored parity from the RAM are compared. If they match, no bit error in either the CAM contents, or RAM stored parity contents, or RAM stored mask bits has been detected. If they do not match, a bit error in either the CAM contents, RAM stored parity contents, or stored mask bits has been detected.  
         [0022]    One use of a CAM with or without mask bits is in a translation look-aside buffer or TLB. In this application, a virtual address (or portion thereof) is sent to the CAM. If a hit occurs, the CAM causes at least a portion of the physical address to be output by a RAM. A bit error in the CAM of a TLB may cause one of two things to happen. The first, is the bit error will prevent an otherwise valid TLB entry from getting hit (i.e. the bit error causes a TLB entry that should match not to match). In this case, since the replacement of entries in a TLB is often done on a least-recently used basis, the erroneous entry will eventually be replaced because it never matches. This type of bit error won&#39;t be detected. However, since the offending entry is eventually replaced or re-written, this type of bit error does not tend to cause serious problems. The second is a bit error that causes a TLB entry to match when it should not. This type of bit error can cause serious problems in the operation of the computer and, since it causes matches, may not be eventually replaced for lack of use. However, the methods and apparatus described above facilitate the detection of this type of bit error so that this entry may be invalidated, re-written, or otherwise handled before the bit error causes problems.