Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-09-13
2004-06-15
Iqbal, Nadeem (Department: 2114)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C711S133000
Reexamination Certificate
active
06751755
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to content addressable memories (CAMs) and more particularly to a CAM having redundancy capabilities.
BACKGROUND OF THE INVENTION
Content addressable memories (CAMs), also sometimes referred to as “associative memories”, can provide rapid matching functions between a number of stored data values and an applied comparand value. A typical CAM can store data values in one or more CAM cell arrays. The CAM cell arrays can be configured into a number of entries, each of which can provide a match indication. In a compare (i.e., match) operation, the data values stored within the entries can be compared to the comparand value (also referred to as a “search key”). If a data value matches an applied comparand value, the corresponding entry can generate an active match indication. If a data value does not match an applied comparand value, the corresponding entry can generate an inactive match indication (signifying a “mismatch”) condition.
Among the many various types of CAMs are binary CAMs and ternary CAMs. Binary CAMs can compare exact bit values of a comparand to corresponding bits of the entries. Ternary CAMs can enable the masking of selected portions of the entries from a compare operation.
In many applications, the entries within a CAM may be continuously updated. Consequently, some conventional CAMs may include a “status” bit (sometimes referred to as a “valid/invalid” or “occupied/unoccupied” bit). A status bit can be stored in one or more CAM cells in an entry. A status bit can have a “valid” logic state that can indicate an entry that stores usable data. A status bit can also have an “invalid” logic state that can indicate that the data stored within contains data that should no longer be used in a compare operation.
Various aspects of CAM operations are described in co-pending U.S. patent application Ser. No. 09/440,682 titled CONTENT ADDRESSABLE MEMORY HAVING PRIORITIZATION OF UNOCCUPIED ENTRIES (Sywyk et al '682). Sywyk et al. '682 discusses status bits and CAM entry priority. In addition, Sywyk et al '682 shows a novel way of determining which of the various entries is a “next free” entry. The contents of this patent application are incorporated by reference herein.
CAMs are typically manufactured as stand alone integrated circuits or may also be included within (embedded) as one portion of a larger integrated circuit. Thus, like most any other integrated circuits, CAMs may be susceptible to manufacturing defects.
In a typical manufacturing process, integrated circuits may be formed as “dice” on a semiconductor wafer. The wafer may be sliced into individual dice, and each die may then be packaged. In a manufacturing process, defects may be formed on the wafer, due to uncontrollable process variation, or the like. Consequently, a wafer yield (percentage of “good” dice on a wafer) may be less than 100%.
In conventional random access memories (RAMs) and read-only-memories (ROMs), one way to address defects has been to include redundant circuit elements. For example, a typical RAM may include memory cells that are addressable according to a row and column location. If a memory cell was defective, the column or row containing the defective memory cell could be replaced by a redundant column or redundant row. Then, when a RAM address corresponds to the defective memory cell, the redundant column or redundant row could be accessed instead of the column or row containing the defective memory cell. Further, the column or row containing the defective memory cell can be deactivated. In this way, a defective memory cell can be replaced by a redundant memory cell. Such an approach can result in increased yield in an overall manufacturing process.
While redundant circuit elements have been included in RAMs and ROMs, such approaches in CAMs can be more problematic. To better understand the difficulties involved in CAM redundancy schemes, a conventional CAM that does not include redundant elements will now be described.
Referring now to
FIG. 6
, a conventional CAM
600
may include a number of rows
602
-
0
to
602
-n. Each row (
602
-
0
to
602
-n) includes memory cells
604
that may store data values, and thereby form a CAM entry. Memory cells
604
may be binary and/or ternary CAM cells, for example.
Like a conventional RAM or ROM, a CAM
600
may include a row decoder
606
. A ROW decoder
606
can enable a row (
602
-
0
to
602
-n) to be accessed by way of word lines (WL
0
to WLn). Such accesses can allow data values to be read from or written to the rows (
602
-
0
to
602
-n).
However, unlike a conventional RAM or ROM, each row (
602
-
0
to
602
-n) may also provide a match indication on match line (ML
0
to MLn). Such match indications may then be prioritized by a priority encoder
608
. A priority encoder
608
can activate a ROM input (ROM
0
to ROMn) that corresponds to a highest priority match. As but one example, if lower numbered match lines have highest priority, in the event that match lines ML
0
and ML
2
were both activated, only ROM
0
would be activated. If however, match lines ML
2
and MLn were activated, only ROM
2
would be activated. An activated ROM input (ROM
0
to ROMn) may then encode into an index value INDEX, which can be output from a ROM
610
.
As can be shown by
FIG. 6
, circuits for prioritizing a match indication (M
0
to Mn) can complicate approaches to redundancy. In particular, if a redundant row was provided to replace a non-redundant row (
602
-
0
to
602
-n), it is not clear how the redundant row could have the same priority as the replaced non-redundant row.
It would be desirable to arrive at some way of implementing a redundancy scheme in a CAM, particularly one that could provide row redundancy in a CAM.
SUMMARY OF THE INVENTION
According to the disclosed embodiments, a content addressable memory (CAM) includes redundant rows that may be used to replace ordinary (i.e., non-redundant) rows. Redundant rows may provide redundant match indications while ordinary rows may provide ordinary match indications. Switching circuits may provide either a redundant match indication or an ordinary match indication as an input to a priority encoder. In this way, a redundant row may have the same priority as the ordinary row that it replaces.
According to one aspect of the embodiments, multiplexer circuits can receive redundant and ordinary match indications, and provide one or the other as an output according to a redundant enable signal.
According to another aspect of the embodiments, a redundant enable signal may be generated by a redundancy indication circuit that may include nonvolatile circuit elements, such as fusible links.
According to another aspect of the embodiments, multiple redundant rows may replace multiple ordinary rows.
According to another aspect of the embodiments, redundant rows may further include a redundant status indication and ordinary rows may include ordinary status indications. If redundant rows are used to replace ordinary rows, redundancy status indications from the redundant rows may be supplied to a priority encoder by mode multiplexers.
According to another aspect of the embodiments, a CAM may include redundancy multiplexers that select between redundant and ordinary indications and mode multiplexers that select between match and status indications.
REFERENCES:
patent: 6069573 (2000-05-01), Clark et al.
patent: 6249467 (2001-06-01), Pereira et al.
patent: 6275426 (2001-08-01), Srinivasan et al.
patent: 6307787 (2001-10-01), Al-Shamma et al.
patent: 6445628 (2002-09-01), Pereira et al.
patent: 6484271 (2002-11-01), Gray
Sywyk Stefan P.
Voelkel Eric H.
Cypress Semiconductor Corporation
Iqbal Nadeem
Sako Bradley T.
LandOfFree
Content addressable memory having redundancy capabilities does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memory having redundancy capabilities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory having redundancy capabilities will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306567