Performing lookup operations on associative memory entries
First Claim
1. A method performed by an associative memory for use in performing a lookup operation on the associative memory, the associative memory including a plurality of associative memory entries and memory for storing a plurality of modification mappings, said modification mappings including a particular modification mapping, the method comprising:
- receiving a search key;
receiving modification data;
modifying the search key based on the modification data and the particular modification mapping to generate a lookup word; and
performing the lookup operation on said associative memory entries based on the lookup word to generate a result.
0 Assignments
0 Petitions
Accused Products
Abstract
Methods and apparatus are disclosed for performing lookup operations using associative memories, including, but not limited to modifying search keys within an associative memory based on modification mappings, forcing a no-hit condition in response to a highest-priority matching entry including a force no-hit indication, selecting among various sets or banks of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, each block retrieves a modification mapping from a local memory and modifies a received search key based on the mapping and received modification data. In one implementation, each of the associative memory entries includes a field for indicating that a successful match on the entry should or should not force a no-hit result. In one implementation, an indication of which associative memory blocks or sets of entries to use in a particular lookup operation is retrieved from a memory.
-
Citations
31 Claims
-
1. A method performed by an associative memory for use in performing a lookup operation on the associative memory, the associative memory including a plurality of associative memory entries and memory for storing a plurality of modification mappings, said modification mappings including a particular modification mapping, the method comprising:
-
receiving a search key;
receiving modification data;
modifying the search key based on the modification data and the particular modification mapping to generate a lookup word; and
performing the lookup operation on said associative memory entries based on the lookup word to generate a result. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An apparatus including a plurality of associative memory entries, each of the plurality of associative memory entries comprising:
-
a first field including a value for use in a matching operation on a lookup word;
a second field including data for indicating that a successful match on the associative memory entry should or should not force a no-hit result; and
logic for identifying a no-match result indicating that there was not a matching entry of said associative memory entries if the second field of the highest-priority matching entry of said associative memory entries matching the lookup word indicates that a successful match should force a no-hit result. - View Dependent Claims (9, 10, 11)
-
-
12. A method performed by an associative memory in generating a lookup result, the associative memory including a plurality of associative memory entries, at least a particular entry of the plurality of associative memory entries including a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result, the method comprising:
-
performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry; and
generating a no-hit signal in response to the particular entry being identified as the highest-priority matching entry and the particular entry including the force no-hit indication. - View Dependent Claims (13, 14)
-
-
15. An associative memory configured to generated a lookup result, the associative memory including a plurality of associative memory entries, at least a particular entry of the plurality of associative memory entries including a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result, the method comprising:
- means for performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry, and for generating a no-hit signal in response to the particular entry being identified as the highest-priority matching entry and the particular entry including the force no-hit indication.
- View Dependent Claims (16, 17)
-
18. A method for generating a lookup result on a first plurality of associative memory entries and on a second plurality of associative memory entries, at least a first particular entry of the first plurality of associative memory entries including a force no-hit indication, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries, the method comprising:
-
performing a lookup operation based on a first lookup word to identify the first particular entry as a first highest-priority matching entry of the first plurality of associative memory entries;
generating a first no-hit signal in response to the first particular entry being identified as the first highest-priority matching entry and the first particular entry including the force no-hit indication;
performing a lookup operation based on a second lookup word to identify the second particular entry as a second highest-priority matching entry of the second plurality of associative memory entries;
generating a second highest-priority signal identifying the second particular entry; and
identifying the second particular entry as the lookup result in response to the first no-hit signal and the second highest-priority signal. - View Dependent Claims (19, 20, 21)
-
-
22. A method for generating a lookup result on a first plurality of associative memory entries and on a second plurality of associative memory entries, at least a first particular entry of the first plurality of associative memory entries including a force no-hit indication, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries, the method comprising:
-
performing a lookup operation based on a lookup word to identify the first particular entry as a first highest-priority matching entry of the first plurality of associative memory entries and to identify the second particular entry as a second highest-priority matching entry of the second plurality of associative memory entries; and
identifying the second particular entry as the lookup result in response to the first particular entry being identified as the first highest-priority matching entry, the first particular entry including the force no-hit indication, and the second particular entry being identified as the second highest-priority matching entry. - View Dependent Claims (23, 24, 25)
-
-
26. An apparatus for generating a lookup result on a first plurality of associative memory entries and on a second plurality of associative memory entries, at least a first particular entry of the first plurality of associative memory entries including a force no-hit indication, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries, the apparatus comprising:
-
means for performing a lookup operation based on a lookup word to identify the first particular entry as a first highest-priority matching entry of the first plurality of associative memory entries and to identify the second particular entry as a second highest-priority matching entry of the second plurality of associative memory entries; and
means for identifying the second particular entry as the lookup result in response to the first particular entry being identified as the first highest-priority matching entry, the first particular entry including the force no-hit indication, and the second particular entry being identified as the second highest-priority matching entry. - View Dependent Claims (27, 28)
-
-
29. An associative memory configured to perform lookup operations on a plurality of associative memory entries, at least a particular entry of the plurality of entries including a force no-hit indication identifying that a successful match on the particular entry should or should not force a no-hit result, the associative memory comprising:
-
means for performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry of said associative memory entries; and
means for generating a no-hit signal in response to the particular entry being identified as the highest-priority matching entry and the particular entry including the force no-hit indication. - View Dependent Claims (30, 31)
-
Specification