Error correcting content addressable memory

• US 7,254,748 B1
• Filed: 10/14/2003
• Issued: 08/07/2007
• Est. Priority Date: 10/14/2003
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Venkatachary, Srinivasan, Voelkel, Eric H., Sankar, Rochan, Wright, Andrew J.
• Primary Examiner(s): Baderman; Scott
• Assistant Examiner(s): Truong; Loan
• Application Number:
  US10/685,026
• Time in Patent Office: 1,393 Days
• Field of Search: 714/43, 714/54, 714/42
• US Class Current: 714/43
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories

Abstract

A CAM and method for operating a CAM are presented. Copies of a CAM database are duplicated and placed in a first set of CAM locations and a second set of CAM locations. An error detector is used to determine false matches in the case of soft errors within the entries producing those false matches. While the entries producing a match should have the same index location, errors might cause those match lines to have an offset. If so, the present CAM, through use of duplicative sets of CAM locations, will detect the offset and thereafter the values in each index location that produces a match, along with the corresponding parity or error detection encoding bit(s). If the parity or error detection encoding bit(s) indicate an error in a particular entry, then that error is located and the corresponding entry at the same index within the other, duplicative set of CAM locations is copied into the that erroneous entry. Since duplicative copies are by design placed into the first and second sets of CAM locations, whatever value exists in the opposing entry can be written into the erroneous entry to correct errors in that search location. The first and second sets of CAM locations are configurable to be duplicative or distinct in content, allowing error detection and correction to be performed at multiple user-specified granularities. The error detection and correction during search is backward compatible to interim parity scrubbing and ECC scan, as well as use of FNH bits set by a user or provider.

Claims

1. A content addressable memory (CAM), comprising:

a first set of CAM locations coupled to store a first set of values;

a second set of CAM locations coupled to store a second set of values;

an input control circuit coupled to the first and second sets of CAM locations and operable in an error detection mode and a normal mode, wherein the second set of values is a copy of the first set of values when the input control circuit is in the error detection mode, and wherein the second set of values is independent from the first set of values when the input control circuit is in the normal mode; and

a comparator coupled to compare a search key value against the first and second set of values and report an error if a first location within the first set of CAM locations that produces a match is different from a first location within the second set of CAM locations that produces a match when the input control circuit is in the error detection mode.

2. The CAM as recited in claim 1, wherein the search key value comprises a destination address within a packet of information.

3. The CAM as recited in claim 1, further comprising a plurality of priority encoders that provide a priority order by which the first and second sets of values within the respective first and second sets of CAM locations is compared against the search key value relative to other sets of values in other locations within the first and second sets of CAM locations.

4. The CAM as recited in claim 1, further comprising a third set of CAM locations coupled to store a non-duplicative third set of binary values dissimilar from the first and second set of Values, and the combination of first, second and third sets of CAM locations encompasses the entirety of locations within the CAM.

5. The CAM as recited in claim 1, further comprising one or more error detection encoded bits corresponding to each of the first and second sets of values.

6. The CAM as recited in claim 5, further comprising an error location circuit coupled to:

check the first and second sets of values using the error detection encoded bits to determine which one of the first or second sets of values is in error;

record, as a result of the check, whether the error is within the first set of values, the second set of values, both the first and second sets of values; and

record, as a result of the check, the index value corresponding to the set of values that is not in error.

7. The CAM as recited in claim 6, further comprising an error correction circuit coupled to (i) receive the set of values within the second set of CAM locations and at the same index value as the first set of values;

and (ii) write the set of values into the first set of values if the error is within first set of values.

8. The CAM as recited in claim 6, further comprising an error correction circuit coupled to (i) receive a set of values within the first set of CAM locations at the same index value as the second set of values, and (ii) write the set of values into the second set of values if the error is within the second set of values.

9. The CAM as recited in claim 6, further comprising an error correction circuit coupled to (i) receive an index value corresponding to the set of values not in error within the first set of CAM locations;

(ii) receive an index value corresponding to the set of values not in error within the second set of CAM locations, and (iii) select an index value based on a priority order by which the sets of values within the first and second sets of CAM locations are compared against the search key value relative to other sets of values within the first and second set of CAM locations.

10. The CAM as recited in claim 6 further comprising an error correction circuit coupled to signal a con-correctable error if the error is in both the first and second sets of values.

11. The CAM as recited in claim 1, further comprising:

a match suppression bit associated with both the first set of values and the second set of values; and

wherein

the comparator is configured to report an error if the first location within the first set of CAM locations that produces a match is different from the first location within the second set of CAM locations that produces a match, regardless of whether the match suppression bit is a set when the input control circuit is in the error detection mode.

12. The CAM as recited in claim 11, further comprising a read logic circuit coupled to keep track of the first location within either the first set of CAM locations or the second set of CAM locations in which the match occurs if the match suppression bit is set at that location.

13. The CAM as recited in claim 12, further comprising:

one or more error detection encoded bits corresponding to each of the first and second sets of values; and

an error location circuit coupled to check the first and second sets of values using the error detection encoded bits and to record, as a result of the check, whether the error is within the first set of values, the second set of values, or both.

14. The CAM as recited in claim 13, wherein the error location circuit is coupled to perform the check for the corresponding sets of values in the opposing first and second sets of CAM locations corresponding to the same index as the first and second sets of values and to record, as a result of the compare, where the error exists within the set of values.

15. The CAM as recited in claim 14, further comprising an error correction circuit coupled to (i) receive the set of values within the second set of CAM locations and at the same index value as the first set of values;

and (ii) write the set of values into the first set of values if the error is within the first set of values.

16. The CAM as recited in claim 14, further comprising an error correction circuit coupled to (i) receive the set of values within the first set of CAM locations at the same index value as the second set of values;

and (ii) write the set of values into the second set of values if the error is within the second set of values.

17. A content addressable memory (CAM), comprising:

a first block of CAM locations;

a second block of CAM locations; and

an input control circuit operable in an error detection mode to receive a set of values and to store the set of values in the first block of CAM locations and a copy of the set of values in the second block of CAM locations, and operable in a normal mode to receive first and second sets of values and to store the first set of values in the first block of CAM locations and the second set of values in the second block of CAM locations.

18. The CAM as recited in claim 17, further comprising an output control circuit coupled to:

receive a signal from the input control circuit indicating whether the set of values stored in the second block of CAM locations is a copy of the set of values stored in the first block of CAM locations; and

select a first set of values from the first block of CAM locations, a second set of values from the second block of CAM locations, or both the first and second sets of values from the respective first and second blocks of CAM locations.

19. The CAM as recited in claim 18, wherein the output control circuit provides a priority order by which the first set of values from the first block of CAM locations and the second set of values from the second block of CAM locations are compared against a search key value relative to other sets of values within the first and second blocks of CAM locations.

20. The CAM as recited in claim 18, further comprising an error location circuit coupled to compare a search key value against the first and second sets of values and report an error if a first location within the first block of CAM locations that produces a match is different from a first location within the second block of CAM locations that produces a match.

21. The CAM as recited in claim 18, further comprising a plurality of CAM block pairs, wherein each pair is coupled to operate independent of other CAM block pairs.

31. The CAM as recited in claim 17, wherein the input control circuit comprises circuitry to activate a plurality of word lines in response to receiving an incoming write address, wherein a first one of the plurality of activated word lines is coupled to the first block of CAM locations and a second one of the plurality of activated word lines is coupled to the second block of CAM locations.

22. A method of operation within a content addressable memory (CAM), comprising:

selecting between an error detection mode of operation and a normal mode of operation in response to a signal received by an input control circuit;

storing a first set of values in a first set of CAM locations and a duplicative set of values in a second set of CAM locations when the error detection mode is selected;

searching for matches between a key and duplicative sets of values within the respective first and second sets of CAM locations;

recording the first location within the first set of CAM locations and the first location within the second set of CAM locations that produce a match; and

generating an error if the first location within the first set of CAM locations is at a different index than the first location within the second set of CAM locations.

23. The method as recited in claim 22, further comprising:

checking the first and second sets of values using one or more error detection encoding bits to determine which one of the first or second sets of values is in error; and

depending on the outcome of said checking, recording which of the duplicative sets of values is in error.

24. The method as recited in claim 22, further comprising:

copying over one of the duplicative sets of values within the first set of CAM locations having a recorded error from a set of values within the second set of CAM locations and having the same index as the first set of CAM locations if there was no error recorded at an index in the second set.

25. The method as recited in claim 22, further comprising:

copying over one of the duplicative sets of values within the second set of CAM locations having a recorded error from a set of values within the first set of CAM locations and having the same index as the second set of CAM locations if there was no error recorded in an index in the first set.

26. The method as recited in claim 22, further comprising:

detecting whether a hit suppression bit is set in the first location within the first and second set of CAM locations that produces a match.

27. The method as recited in claim 22, further comprising allowing a scan operation to occur in parallel with said searching and recording to enhance reliability within the CAM.

28. The method as recited in claim 22, further comprising allowing a parity or error detection scan operation to occur in parallel with said searching and recording to capture errors within both the first and second sets of CAM locations.

29. The method as recited in claim 22, further comprising configuring the first and second sets of CAM locations to selectively store duplicative values.

30. The method as recited in claim 22, further comprising selecting a single search result from the combined first and second sets of CAM locations, or selecting a first search result from the first set of CAM locations and a second search result from the second set of CAM locations.