Detection of errors in a ternary content addressable memory

Patent metadata

Field	Value
Publication number	US-10243590-B1
Application number	US-201514857787-A
Country	US
Kind code	B1
Filing date	Sep 17, 2015
Priority date	Sep 17, 2015
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

Abstract

A ternary content addressable memory (TCAM) may implement complete detection of single and double bit errors for entries. A single error correction double error detection (SECDED) error correction code may be generated and maintained for each entry in the TCAM. The SECDED error correction code may be generated from the parity bit and bits that indicate don't−care conditions in memory cells storing a value for an entry in the TCAM. When an entry of the TCAM is accessed, the value of the entry may be validated with respect to the SECDED error correction code. All single bit errors and double bit errors in the value or data stored for the value, such as a parity bit or value bit, may be detected. All single bit errors and some double bit errors may be corrected.

First claim

What is claimed is:

1. A system, comprising:
a packet processor that implements a ternary content addressable memory (TCAM), wherein the TCAM stores a plurality of entries, wherein an entry is stored in a plurality of memory cells that each comprise a respective data bit and a respective mask bit;
wherein the TCAM is configured to:
for respective values of the entries stored in the TCAM:
encode as a single error correction double error detection (SECDED) error correction code:
a parity bit, stored for the data bits of the memory cells of the value, and
respective bits that identify the existence of a don't−care condition in the memory cells of the value;

maintain the SECDED error correction code for the entry;

receive a lookup key;
identify one of the entries as a match for the lookup key;
validate the value of the identified entry with respect to the SECDED error correction code; and
in response to a determination that the value is valid; return a lookup value for the identified entry.

2. The system of claim 1 , wherein TCAM is further configured to:
receive another lookup key;
identify another one of the entries as a match for the other lookup key;
validate the value of the other entry with respect to the SECDED error correction code far the other entry;
based on the validation of the other entry, detect a bit flip in the parity bit stored for the data bits of the value of the other entry; and
correct the parity bit.

3. The system of claim 1 , wherein to decode the SECDED error correction code with respect to the value of the identified entry to validate the value, the TCAM is configured to:
validate the parity bit and the bits that identify the existence of the don't−care condition in the memory cells of the entry;
determine bits that identify the existence of an illegal condition in the memory cells of the entry; and
based on the validation of the parity bit and the bits that identify the existence of the don't−care condition and based on the bits that identify the existence of the illegal condition the memory cells of the entry, validate the data bits and the mask bits for the identified entry.

4. The system of claim 1 , wherein the system is a network switch.

5. A method, comprising:
maintaining single error correction double error detection (SECDED) error correction codes for respective values of a plurality of entries stored in a ternary content addressable memory (TCAM) at the TCAM wherein individual ones of the plurality of entries of the TCAM comprise a plurality of memory cells, wherein a memory cell comprises a data bit and a mask bit, wherein the SECDED error correction codes are generated for the respective values according to:
parity bits, stored for the data bits of the memory cells of the plurality of entries, and
respective bits that identify the existence of a don't−care condition is the memory cells of the plurality of entries;

receiving input data or a lookup key at the TCAM;
identifying, by the TCAM, one of the plurality of entries as a match for the input data or the lookup key; and
validating, by the TCAM, the value of the identified entry with respect to the SECDED error correction code.

6. The method of claim 5 , wherein the SECDED error correction code is further generated from a valid bit for the one entry, wherein the valid bit indicates that the one entry is valid for perforating lookups, and wherein validating the respective value of the one entry comprises validating the valid bit.

7. The method of claim 6 , wherein validating the respective value of the one entry further comprises:
detecting a bit flip in a corresponding one of the parity bits that is stored for the data bits of the memory cells of the one entry; and
correcting the bit flip in the corresponding one parity bit.

8. The method of claim 5 , wherein validating the respective value of the one entry comprises:
detecting a double bit flip error in the value; and
correcting the double bit flip error in the value.

9. The method of claim 5 , further comprising encoding, by the TCAM, the SECDED error correction codes for the respective values of a plurality of entries stored in the TCAM.

10. The method of claim 9 , wherein encoding the SECDED error correction codes, comprises:
separately generating portions of the SECDED error correction codes; and
combining the separately generated portions into the SECDED error correction codes.

11. The method of claim 5 , wherein the TCAM is implemented as part of a networking device.

12. A ternary content addressable memory (TCAM) that stores a plurality of entries, wherein an entry is stored in a plurality of memory cells that each comprise a respective data bit and a respective mask hit, and wherein the TCAM is configured to:
for respective values of individual ones of the plurality of entries:
maintain a single error correction double error detection (SECDED) error correction code encoded from:
a parity bit, stored for the data bits of the memory cells of the value, and
respective bits that identify the existence of a don't−care condition in the memory cells of the value; and

receive input data or a lookup key;
identify one of the plurality of entries as a match for the input data or the lookup key;
validate the value of the identified entry with respect to the SECDED error correction code.

13. The TCAM of claim 12 wherein to validate the value, the TCAM is configured to:
detect a bit flip in the parity bit; and
correct the bit flip in the parity.

14. The TCAM of claim 12 , wherein the TCAM is further configured to:
for the respective values of individual ones of the plurality of entries:
encode the parity bit stored for the data bits of the memory cells of the value and the respective bits that identify the existence of the don't−care condition as the SECDED error correction code for the value.

15. The TCAM of claim 14 ,
wherein a valid bit for the entry is included in the SECDED error correction code; and
wherein to validate the value, the TCAM is configured to validate the valid bit far the entry.

16. The TCAM of claim 12 , wherein to validate the value, the TCAM is configured to:
detect a double bit flip error in the value; and
correct the double bit flip error in the value.

17. The TCAM of claim 12 , wherein the access to the entry is performed as part of a scrub operation for the TCAM that accesses the plurality of entries.

18. The TCAM of claim 12 , wherein the TCAM is implemented as part of an application specific integrated circuit (ASIC) included in a networking device.

Assignees

• Amazon Tech Inc

Inventors

• Seshadri Kiran Kalkunte

Classifications

• G11C15/00 Primary

  Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores · CPC title

• H03M13/2906 Primary

  using block codes (H03M13/2957 takes precedence) · CPC title

• G06F11/1064

  in cache or content addressable memories · CPC title

• H03M13/19

  Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes · CPC title

• G11C15/04

  using semiconductor elements · CPC title