Prioritized content addressable memory

#The present invention relates to a data search method and apparatus for locating data in a content addressable memory.

#A content addressable memory (“CAM”) typically stores data in a plurality of memory locations. The CAM may include value matching logic that compares input data against the stored data and generates an indicator signal identifying those memory locations where the input value matches a stored value. A value match often is called a “hit.” Such properties of CAMs are well-known.

#A CAM may be used as part of a prioritized search. That is, if input data causes several hits, there may be only desired match. The desired match may be identified by a prioritization scheme that operates independently of the CAM process. In this case, a search may be performed against the matching entries to identify the one that should be identified as a match. Unfortunately, a prioritized search typically implies an entry-for-entry search of the matching locations, a process that can introduce severe latency into the search process.

#FIG. 1 illustrates a prioritized CAM according to an embodiment of the present invention.

#FIG. 2 illustrates a method of operation of a prioritized CAM according to an embodiment of the present invention.

#FIG. 3 is a block diagram illustrating an exemplary processor core according to an embodiment of the present invention.

#Embodiments of the present invention provide a prioritized CAM that reduces the match and scan latency. Prior to receiving an input value on which to perform a value match, the prioritized CAM performs an internal value match of each entry against the others. The internal value match identifies redundant values stored throughout the CAM. Each of the redundant values are prioritized. Thus, when a new value is input to the CAM, the new value is compared against each of the redundant values having the highest priority and the unique values. Only one hit can be possible. Thus, the prioritized CAM achieves an “at most one hit” property.

#FIG. 1 illustrates a prioritized CAM 100 according to an embodiment of the present invention. The CAM 100 may include a memory file 110, a controller 120 and a priority matrix 130. The memory file 110 may be populated by a plurality of CAM registers 111-119. While nine CAM registers are shown in the embodiment of FIG. 1, the CAM 100 may include as few or as many registers as are desired. The CAM registers 111-119 may include value matching logic that permits a comparison to be made of data stored in the registers 111-119 against an input value on line 121. Hits may be identified to the controller 120 over lines 122.

#The controller 120 may receive an input data signal over input 123 and may output the input data signal to the register over line 121. The controller 120 also may control the priority matrix 130 over line 124. In one embodiment, the controller 120 may be a state machine.