Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-06-08
2004-07-13
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06763425
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 translate address space in the disabled CAM blocks to the remaining enabled CAM blocks. In accordance with one embodiment of the present invention, each CAM block is coupled to a corresponding block select circuit and to an address translation circuit. Each block select circuit provides a select signal to a corresponding CAM block to selectively enable or disable the CAM block. The address translation circuit includes logic that translates address space from disabled (e.g., defective) CAM blocks to enabled (e.g., non-defective) CAM blocks. During read and write operations, an address to access a row in a first of the CAM blocks is received into the address translation logic. If the first CAM block is disabled, the address translation logic translates the address to access a row in a second of the CAM blocks. Conversely, if the first CAM block is enabled, the address translation logic facilitates access to the row in the first CAM block.
In one embodiment, the address translation logic includes decode logic providing a number of decode signals, a plurality of multiplexers each having a number of inputs to receive the number of decode signals and an output to provide a block select signal to a corresponding CAM block, and a plurality of memory elements for storing multiplexer select values for the corresponding plurality of multiplexers. During read and write operations, one or more block address bits from the address are decoded by the decode logic to assert one of the decode signals. The multiplexers, which control which CAM block is selected for the operation in response to the asserted decode signal, may be programmed to selectively translate an address accessing a row in a first CAM block to access a row in a second CAM block by manipulating the multiplexer select values stored in the memory elements.
REFERENCES:
patent: 4244033 (1981-01-01), Hattori
patent: 4656626 (1987-04-01), Yudichak et al.
patent: 4670858 (1987-06-01), Almy
patent: 4813002 (1989-03-01), Joyce et al.
patent: 4845668 (1989-07-01), Sano et al.
patent: 4888731 (1989-12-01), Chuang et al.
patent: 4958377 (1990-09-01), Takahashi
patent: 4959811 (1990-09-01), Szczepanek
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: 5440715 (1995-08-01), Wyland
patent: 5448733 (1995-09-01), Satoh et al.
patent: 5485418 (1996-01-01), Hiraki et al.
patent: 5524231 (1996-06-01), Brown
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: 5818786 (1998-10-01), Yoneda
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: 6275426 (2001-08-01), Srinivasan et al.
patent: 6487131 (2002-11-01), Clark 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, “Associative Memory System,” publication No. 08273376, published Nov. 18, 1996.
Patent Abstracts of Japan, “Semicondutor Memory,” publication No. 07021785, published Jan. 24, 1995.
EPO Search Report dated Feb. 12, 2002 for corresponding PCT Application No. PCT/US01/18736.
Anderson Matthew D.
Kim Matthew
NetLogic Microsystems, Inc.
Paradice III William L.
LandOfFree
Method and apparatus for address translation 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 address translation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for address translation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3190868