Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-03-07
2004-08-03
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S156000, C711S221000, C707S793000
Reexamination Certificate
active
06772279
ABSTRACT:
TECHNICAL FIELD
The present invention relates to content addressable memories (CAMs) and particularly to the use of comparand registers within CAMs and/or CAM based systems.
BACKGROUND OF THE INVENTION
Due to the increased prevalence of information networks, including the Internet, content addressable memories (CAMs) continue to proliferate. CAMs, also referred to as “associative memories” can provide rapid matching functions that are often needed in routers and network switches to process network packets. As just one example, a router can use a matching function to match the destination of an incoming packet with a “forwarding” table. The forwarding table can provide “next hop” information that can allow the incoming packet to be transmitted to its final destination, or to another node on the way to its final destination. Of course, CAMs can also be used for applications other than network hardware.
A CAM may perform the matching functions described above by providing the ability to apply a search key or “comparand” to a table of stored data values. A CAM may then determine if any of the data values match a given search key. A typical conventional search operation, along with a general architecture of a conventional CAM system will now be described in more detail.
Referring to
FIG. 9A
, an example of a conventional CAM system is shown, and is designated by the general reference number
900
. A conventional CAM system
900
may include a network processing unit (NPU)
902
, and a number of CAM blocks
904
-
1
and
904
-
2
that may be connected by control and data signals
908
.
Referring now to
FIG. 9B
, CAM blocks
904
are shown in more detail, and may include a CAM array
912
, CAM control circuits
914
, and a comparand register (CMPR) set
916
.
A CAM array
912
may contain any number of CAM storage cells. Data may be written to and/or read from such CAM storage cells. A CAM array
912
may also support a search function, where a search key or “comparand” may be compared against data stored in any number of CAM storage cells. If the data in any CAM storage cell matches a comparand value, then a search hit may be indicated. Otherwise, a search miss may be indicated.
CAM control circuits
914
can take CAM control and data signalsl
908
as inputs and generate signals that may be necessary to control the operation of a CAM array
912
.
A CMPR set
916
may include any number of storage locations that may be used to store comparand values used for search operations. In the particular example of
FIG. 9B
, a CMPR set
916
includes eight storage locations. Comparand values may be loaded into a location of a CMPR set
916
by CAM control and data signals
908
.
Having described an example of a CAM based system, as well as a CAM block, a conventional CAM search operation will now be described. To perform la search operation, an NPU
902
may provide to CAM blocks
904
a comparand value as well as the location within a comparand register set
916
to store the comparand data. A comparand value may then be compared to all the CAM storage locations within a CAM array
912
.
If any of the values stored in a CAM array
912
matches the comparand value, it is considered a search “hit.” Various actions may be taken in response to a search hit. As an example, an index value may be generated for the CAM storage location that matches a comparand value. Further, a search result may be communicated back to an NPU
902
by way of control and data signals
908
. It is noted that in a conventional case, a comparand register set
916
location corresponding to a matching comparand value may then be free for use again in a system.
If none of the values stored in a CAM array
912
matches a comparand value, such an operation may be considered a search “miss”. In this case, a comparand value stored at the specified comparand register set
916
location may be retained for later use. In particular, such a comparand value may be used in a “learn” operation. A learn operation provides a way for the CAM to “learn” the comparand value for a previously missed search operation. Thus, the next time the same comparand value is applied, a search hit may result.
A conventional CAM learn operation will now be described in more detail. To perform a learn operation, an NPU
902
may provide to CAM blocks
904
a location within a comparand register set
916
that contains the comparand value to be “learned”. The comparand value stored at this location can then be written into a CAM array
912
at a free or otherwise designated storage location. In this way, the CAM has “learned” the comparand value from a missed search. Associated data for such a comparand value may be written to, or otherwise made available, at some location indexed by a given designated location.
In a conventional learn operation, such as that described above, a network processing unit (NPU) and/or system software or firmware controlling such operations, may have to keep track of the values stored in the comparand register set
916
. For example, to perform a learn operation, a system may keep track of which comparand register set
916
locations contain comparand values for a missed search operations. Thus, in performing a learn operation, an NPU
902
may initially issue a search based on a register within a register set
916
. When the search indicates a “miss,” an NPU
902
recalls the register used in an initial search, and orders a learn operation based upon the same register.
Thus, a conventional approach may require an NPU
902
to access a CAM block (
904
-
1
and
904
-
2
) at least twice in an overall learn operation. One access issues an initial search operation. A second access issues a corresponding learn operation when the initial search gives a miss result. Further, an NPU
902
may have to track which register stores a comparand value within a given CAM block (
904
-
1
and
904
-
2
).
Because reductions in the number of times devices may access one another can increase the speed and efficiency of a system, it would be desirable to arrive at some way of reducing accesses between an NPU and a CAM blocks, or the like.
It is also noted that conventional approaches may result in constraints on when a learn operation may be performed. In particular, if all locations of a CMPR set
916
store comparand values that are in use, it may not be possible to issue a learn command.
Thus, it would be desirable to arrive at some way of providing more flexibility in how comparand storage registers are utilized in CAM system.
SUMMARY OF THE INVENTION
According to the present invention, a content addressable memory (CAM) system may include a free index list and a busy index list. A free index list may include locations for storing index values that correspond to comparand values for use in search operations. A busy index list may include locations for storing index values that correspond to comparand values for use in non-search operations.
According to one aspect of the embodiments, a free index list may include registers that store indexes to comparand registers.
According to another aspect of the embodiments, a busy index list may also include registers that store indexes to the comparand registers.
According to another aspect of the embodiments, a CAM system may further include head and tail pointers for a free index list that indicates the start and end of valid entries in the free index list. Head and tail pointers may also be provided for a busy index list.
According to another aspect of the embodiments, a CAM system may further include a descriptor command list. A descriptor command list may store values associated with commands issued to CAM cells. Each location of a descriptor command list may include an index field that stores an index value for a comparand, as well as a valid field that stores a valid indication for the descriptor command list location.
According to another aspect of the embodiments, a CAM system may further include at least one CAM block. A CAM block may include at least one array of CAM cells and comparand
Hou Wen-Chau
Sun Chih-Ping
Zhang Wei
Cypress Semiconductor Corporation
Peikari B. James
Sako Bradley T.
LandOfFree
Method and apparatus for monitoring the status of CAM... 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 monitoring the status of CAM..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for monitoring the status of CAM... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3333514