Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-06-08
2004-02-03
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06687785
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates generally to semiconductor memories and specifically to content addressable memories.
2. Description of Related Art
Content addressable memories (CAMs) are frequently used for address look-up functions in Internet data routing. For example, routers used by local Internet Service Providers (ISPs) typically include one or more CAMs for storing a plurality of Internet addresses and associated data such as, for instance, corresponding address routing information. When data is routed to a destination address, the destination address is compared with all CAM words, e.g., Internet addresses, stored in the CAM array. If there is a match, routing information corresponding to the matching CAM word is output and thereafter used to route the data.
A CAM device includes a CAM array having a plurality of memory cells arranged in an array of rows and columns. Each memory cell stores a single bit of digital information, i.e., either logic zero or logic one. The bits stored within a row of memory cells constitute a CAM word. During compare operations, a comparand word is received at appropriate input terminals of a CAM device and driven into the CAM array using comparand lines to be compared with all the CAM words in the device. For each CAM word that matches the comparand word, a corresponding match line signal is asserted to indicate a match condition. If the comparand word matches more than one of the CAM words, the match line corresponding to each of the matching CAM words is asserted, and a “multiple match” flag is also asserted to indicate the multiple match condition. The match line signals from each CAM block are combined in a priority encoder to determine the index or address of the highest-priority matching CAM word. Associative information corresponding to the highest-priority matching CAM word stored in, for instance, an associated RAM, may also be provided.
A single CAM device may include one or more CAM blocks, each having an array of CAM cells. In such a device, the CAM blocks typically have consecutive address spaces. When one of the CAM blocks is defective, the corresponding address space is no longer available. As a result, the entire CAM device may no longer be suitable for its intended purpose, particularly when the address spaces in the remaining, non-defective CAM blocks are non-contiguous. Rather than discarding the CAM device, it would be desirable to disable the one or more defective CAM blocks, and operate the remaining non-defective CAM blocks using contiguous address space.
SUMMARY
A method and apparatus are disclosed that may be used to disable one or more defective CAM blocks, and to selectively re-assign priority between the remaining enabled CAM blocks. In accordance with one embodiment of the present invention, each CAM block includes an array of CAM cells organized in a number of rows and columns, where each row has a match line to indicate match conditions therein during a compare operation. Each block also includes a block priority encoder coupled to the number of match lines and having an output to provide a row index of a row that stores data that matches comparand data. The row indexes from the CAM blocks are provided to a main priority encoder that stores a dynamic block index for each of the plurality of CAM blocks. The main priority encoder combines each row index with a corresponding block index to generate a device index for each CAM block. The main priority encoder may re-assign priority between the plurality of CAM blocks by manipulating the dynamic block indexes.
In one embodiment, the main priority encoder includes select logic and a multiplexer chain. The multiplexer chain includes a plurality of multiplexers each having a first input coupled to an output of a previous multiplexer, a second input to receive the row index and block index from a corresponding CAM block, an output coupled to a first input of a next multiplexer, and a select terminal. The select logic is coupled to receive match information from the CAM blocks and in response thereto provides select signals to the plurality of multiplexers.
REFERENCES:
patent: 4244033 (1981-01-01), Hattori
patent: 4656626 (1987-04-01), Yudichak et al.
patent: 4670858 (1987-06-01), Almy
patent: 4845668 (1989-07-01), Sano et al.
patent: 4958377 (1990-09-01), Takahashi
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5053991 (1991-10-01), Burrows
patent: 5123105 (1992-06-01), Wyland et al.
patent: 5319589 (1994-06-01), Yamagata et al.
patent: 5383146 (1995-01-01), Threewitt
patent: 5388066 (1995-02-01), Hamamoto et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5440753 (1995-08-01), Hou et al.
patent: 5448733 (1995-09-01), Satoh et al.
patent: 5485418 (1996-01-01), Hiraki et al.
patent: 5513134 (1996-04-01), Cooperman et al.
patent: 5555397 (1996-09-01), Sasama et al.
patent: 5642322 (1997-06-01), Yoneda
patent: 5649149 (1997-07-01), Stormon et al.
patent: 5706224 (1998-01-01), Srinivasan et al.
patent: 5726942 (1998-03-01), Yoneda et al.
patent: 5818786 (1998-10-01), Yondea
patent: 5828593 (1998-10-01), Schultz et al.
patent: 5860085 (1999-01-01), Stormon et al.
patent: 5870324 (1999-02-01), Helwig et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5946704 (1999-08-01), Yoneda et al.
patent: 5999435 (1999-12-01), Henderson et al.
patent: 6044005 (2000-03-01), Gibson et al.
patent: 6081442 (2000-06-01), Igarashi et al.
patent: 0 381 249 (1990-08-01), None
patent: 0774758 (1997-05-01), None
patent: 0 872 802 (1998-10-01), None
patent: 0918335 (1999-05-01), None
Patent Abstracts of Japan, “Semiconductor Memory,” publication No. 07021785, published Jan. 24, 1995.
EPO Search Report dated Feb. 12, 2002 for corresponding PCT Application No. PCT/US01/18736.
Patent Abstracts of Japan, “Associative Memory System,” publication No. 08273376, and published Nov. 18, 1996.
Anderson Matthew D.
Kim Matthew
NetLogic Microsystems, Inc.
Paradice III William L.
LandOfFree
Method and apparatus for re-assigning priority in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for re-assigning priority in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for re-assigning priority in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338844