PERFORMING LOOKUP OPERATIONS USING ASSOCIATIVE MEMORIES OPTIONALLY INCLUDING MODIFYING A SEARCH KEY IN GENERATING A LOOKUP WORD AND POSSIBLY FORCING A NO-HIT INDICATION IN RESPONSE TO MATCHING A PARTICULAR ENTRY
First Claim
1. A method performed by an associative memory for use in performing a lookup operation on a plurality of associative memory entries included in the associative memory, the method comprising:
- receiving a search key and modification data;
identifying a modification mapping;
modifying the search key based on the modification data and the modification mapping to generate a lookup word; and
performing the lookup operation on the plurality of associative memory entries based on the lookup word to generate a result.
2 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
34 Claims
-
1. A method performed by an associative memory for use in performing a lookup operation on a plurality of associative memory entries included in the associative memory, the method comprising:
-
receiving a search key and modification data;
identifying a modification mapping;
modifying the search key based on the modification data and the modification mapping to generate a lookup word; and
performing the lookup operation on the plurality of associative memory entries based on the lookup word to generate a result. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An associative memory comprising:
-
a memory for storing a plurality of modification mappings;
a plurality of associative memory entries;
one or more inputs for receiving a search key and modification data; and
a control for retrieving a particular modification mapping of said plurality of modification mappings from the memory, for modifying the search key based on the modification data and the particular modification mapping to generate a lookup word, and for initiating a lookup operation in the plurality of associative memory entries based on the lookup word. - View Dependent Claims (8)
-
-
9. An associative memory including a plurality of associative memory entries, the associative memory comprising:
-
means for receiving a search key and modification data;
means for identifying a modification mapping;
means for modifying the search key based on the modification data and the modification mapping to generate a lookup word;
means for performing a lookup operation on the plurality of associative entries based on the lookup word to generate a result. - View Dependent Claims (10, 11, 12, 13, 14)
-
-
15. A method for use in performing a lookup operation in an associative memory, the associative memory including a first associative memory block and a second associative memory block, the method comprising:
-
the first associative memory block receiving a profile ID;
the first associative memory block retrieving a first modification mapping based on the profile ID;
the first associative memory block receiving a search key and modification data;
the first associative memory block modifying the search key based on the first modification mapping and said modification data to generate a first lookup word;
the first associative memory block performing a lookup operation based on the first lookup word to produce a first lookup result;
the second associative memory block receiving the profile ID;
the second associative memory block retrieving a second modification mapping based on the profile ID;
the second associative memory block receiving the search key and said modification data;
the second associative memory block modifying the search key based on the second modification mapping and said modification data to generate a second lookup word; and
the second associative memory block performing a lookup operation based on the second lookup word to produce a second lookup result. - View Dependent Claims (16, 17, 18)
-
-
19. An associative memory for producing a first lookup result and a second lookup result, the associative memory comprising:
-
a first associative memory block including;
a first control, a first memory, and a first plurality of associative memory entries;
wherein the first control is configured to receive a profile ID, a search key, and modification data, to retrieve a first modification mapping from the first memory based on the profile ID, to generate a first lookup word based on the search key, said modification data, and the first modification mapping, and to perform a lookup operation on the first plurality of associative memory entries based on the first lookup word to produce the first lookup result; and
a second associative memory block including;
a second control, a second memory, and a second plurality of associative memory entries;
wherein the second control is configured to receive the profile ID, the search key, and said modification data, to retrieve a second modification mapping from the second memory based on the profile ID, to generate a second lookup word based on the search key, said modification data, and the second modification mapping, and to perform a lookup operation on the second plurality of associative memory entries based on the second lookup word to produce the second lookup result. - View Dependent Claims (20, 21, 22)
-
-
23. A computer-readable medium having stored thereon an associative memory entry, the associative memory entry comprising:
-
a first field including a value for use in a matching operation on a lookup word; and
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. - View Dependent Claims (24, 25, 26)
-
-
27. A computer-readable medium having stored thereon an associative memory entry, the associative memory entry comprising:
-
a first field including a value for use in a matching operation on a lookup word; and
a second field including data to force a no-hit result should the associative memory entry be a highest-priority matching entry.
-
-
28. A method for generating a lookup result, the method comprising:
-
programming 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;
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.
-
-
29. A method for generating a lookup result, the method comprising:
-
programming a first 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;
programming a second plurality of associative memory entries, the first plurality of associative memory entries having a higher priority than the second plurality of associative memory entries;
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 (30)
-
-
31. An associative memory comprising:
-
a plurality of associative memory entries, each of the plurality of associative memory entries comprising a value for use in a matching operation on a lookup word and a force or do not force a no-hit indication identifying that a successful match on said associative memory entry should or should not force a no-hit result; and
control logic for performing a lookup operation on the plurality of associative memory entries based on a lookup word to identify a particular highest-priority matching entry. - View Dependent Claims (32)
-
-
33. An apparatus comprising:
-
means for programming a plurality of entries of an associative memory, 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;
means for performing a lookup operation based on a lookup word to identify the particular entry as a highest-priority matching entry; 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 (34)
-
Specification