Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-08-24
2003-03-25
Nelms, David (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S230030, C365S230050
Reexamination Certificate
active
06538911
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to memory circuits, and more specifically to systems and methods for improved content addressable memory searching using selectable memory blocks.
2. Description of the Related Art
A content addressable memory (CAM) semiconductor device is a device that allows the entire contents of the memory to be searched and matched instead of having to specify one or more particular memory locations in order to retrieve data from the memory. Thus, a CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks.
CAMs provide performance advantages over conventional memory devices having conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired search term, or comparand, against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a non-CAM based database of 1000 entries may take ten separate search operations whereas a CAM device with 1000 entries may be searched in a single operation, resulting in significant time and processing savings. Internet routers often include a CAM for searching the address of specified data, allowing the routers to perform fast address searches to facilitate more efficient communication between computer systems over computer networks.
Conventional CAMs typically include a two-dimensional row and column content addressable memory core array of cells. In such an array, each row typically contains an address, pointer, or bit pattern entry. In this configuration, a CAM may perform “read” and “write” operations at specific addresses as is done in conventional random access memories (RAMs). However, unlike RAMs, data “search” operations that simultaneously compare a bit pattern of data against an entire list (i.e., column) of pre-stored entries (i.e., rows) can be performed.
FIG. 1
shows a simplified block diagram of a conventional CAM
100
. The CAM
100
includes a data bus
102
for communicating data, an instruction bus
104
for transmitting instructions associated with an operation to be performed, and an output bus
106
for outputting a result of the operation. For example, in a search operation, the CAM
100
may output a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data.
In operation, the CAM
100
uses search data, or “comparand”, supplied using the data bus
102
, to perform a parallel compare of the comparand to all of the valid entries stored within the CAM
100
. If a match is found, referred to as a “hit”, the address of the matching entry is output from the CAM using the output bus
106
. In cases where multiple entries match the comparand, such as when a “ternary” CAM is used that allows entries to include bits with a “don't care” state, the CAM
100
may have a priority encoder that resolves the address of the highest priority matching entry.
The CAM often performs look-up functions based on elements of a cell, frame, packet, or datagram header to make intelligent forwarding decisions. The process is similar to a post office reading the address on an envelope to determine the next post office to which the envelope will be delivered. To satisfy the constant need for increasing bandwidth and table size, CAMs have become increasingly fast and dense. Frequently, CAMs are pipelined to increase the look-up rate of the CAM, allowing several look-up functions to be executed in parallel.
While CAMs offer one of the fastest look-up solutions currently available, they have the potential to consume significant power as CAMs scale for increasing density and speed. The parallel search associated with each search operation requires that the comparand be compared to every valid entry in the table. This causes significant consumption of power as many long internal metal tracks transition from one power rail to the other. This type of power is frequently referred to as “CV
2
F” power since it is derived from the capacitance of the nodes that are transitioning, the square of the voltage difference between the beginning and the end of the transition and the frequency of the transition.
Although most of the CAM memory includes valid entries, often many sections of memory having valid entries do not include actual address data and thus will present a “miss” when the search data is compared to these entries. Since, power consumed in determining an entry does not match the comparand is effectively wasted, searching these entries waste power.
In view of the foregoing, there is a need for low power search methods for use in content addressable memory circuits. The methods should reduce the power required to perform searches in the CAM and preferably not waste power searching entries known to contain non-usable data.
SUMMARY OF THE INVENTION
Broadly speaking, the present invention fills these needs by providing architectures and methods that significantly reduce the power consumption of a CAM by using a block select method applied coincident with search input data. In one embodiment, a CAM is disclosed having a plurality of memory blocks for storing data within the CAM, and a search port in communication with the plurality of memory blocks. The search port is capable of facilitating search operations using the memory blocks. Also included in the CAM is a block select bus capable of selecting at least one specific memory block from the plurality of memory blocks. By using the block select bus, the search operations are performed using only the selected memory blocks. A maintenance port can also be included that is in communication with the plurality of memory blocks. The maintenance port is capable of facilitating maintenance operations using the memory blocks. Similar to search operations, the block select signal or a similar signal is capable of selecting at least one specific memory block from the plurality of memory blocks, wherein the maintenance operations are performed using only the selected memory blocks.
In another embodiment, a system is disclosed for selecting memory blocks within a content addressable memory. The system includes a block select memory that stores a plurality of memory block selection configurations. Each of the memory block selection configuration determines specific memory blocks of a CAM to enable for a CAM operation. Also included is a binary decode circuit for decoding a binary block select signal. The binary decode circuit selects a particular block selection configuration to utilize for a CAM operation. In one aspect of the present invention, the block select memory includes a block select configuration register having a plurality of bytes, with each byte storing a memory block selection configuration. Each byte comprises a plurality of bits, with each bit in communication with a particular memory block of the CAM. Each bit is then used to enable and disable the particular memory block in communication with the bit. In another aspect, the block select memory includes a plurality of block selection registers, where each block selection register stores a memory block selection configuration. Each block selection register includes a plurality of bits, with each bit in communication with a particular memory block of the CAM and capable of enabling and disabling the particular memory block in communication with the bit.
A system for low power operation of a CAM is disclosed in a further embodiment of the present invention. The system includes a CAM having a plurality of memory blocks, and a block select bus in communication with the CAM, where the block select bus is capable of selecting particular memory blocks from the plurality of memory blocks. The system also includes a first functional circuit capable of outputting a binary block select pattern to the block select bus by applying a first function to received search data. The
Allan Graham A.
Gibson G. F. Randall
Podaima Jason Edward
Auduong Gene N.
Martine & Penilla LLP
Nelms David
SiberCore Technologies, Inc.
LandOfFree
Content addressable memory with block select for power... 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 with block select for power..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory with block select for power... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3006220