Performing lookup operations using associative memories optionally including selectively determining which associative memory blocks to use in identifying a result and possibly propagating error indications

• US 20040030802A1
• Filed: 08/10/2002
• Published: 02/12/2004
• Est. Priority Date: 08/10/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Eatherton, William N., Ertemalp, Fusun, Lee, Jaushin, Priyadarshan, Bangalore L., Warkhede, Priyank Ramesh
• Granted Patent: US 7,065,609 B2
• Time in Patent Office: Days
• US Class Current: 709/245
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

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 blocks or sets of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, indications of which associative memory blocks to use and/or enable in a particular lookup operation are retrieved from one or more memories, such as that based on received a profile ID. In one implementation, which may or may not be in a cascaded configuration, one or more identified or received error conditions are propagated in such a manner as to identify a source of each error condition.

Claims

1. A method for generating a lookup result, the method comprising:

retrieving an indication of a subset of a plurality of associative memory blocks to use in determining the lookup result, each of the subset of the plurality of associative memory blocks indicating an associative memory block lookup result;

selecting a highest priority hit result from said associative memory block lookup results from the subset of the plurality of associative memory blocks; and

indicating the highest priority hit result as the lookup result.

2. The method of claim 1, comprising receiving a profile ID;

wherein the indication of the subset of the plurality of associative memory blocks to use is retrieved from a memory based on the profile ID.

3. The method of claim 2, further comprising identifying, based on the profile ID, which of the plurality of associative memory blocks to enable in generating the lookup result.

4. The method of claim 1, wherein said selecting the highest priority hit result further includes selecting from one or more previous stage results.

5. The method of claim 1, wherein each of the plurality of associative memory blocks includes one or more associative memory banks, each of said one or more associative memory banks including a plurality of associative memory entries.

6. The method of claim 1, wherein each of the plurality of associative memory blocks includes a plurality of associative memory entries.

7. The method of claim 1, comprising selecting a particular one of a plurality of output buses, wherein said indicating includes indicating the lookup result on the particular one of the plurality of output buses.

8. The method of claim 7, comprising receiving an indication of the particular one of the output buses;

wherein said selecting is performed based on the indication.

9. The method of claim 7, comprising retrieving from a memory an indication of the particular one of the output buses;

wherein said selecting is performed based on the indication.

10. The method of claim 9, comprising receiving a profile ID;

wherein said retrieving is performed based on the profile ID.

11. An associative memory device comprising:

a plurality of associative memory blocks, each of the associative memory blocks indicating an associative memory block lookup result; and

an output selector configured to retrieve from a memory an indication of the plurality of associative memory blocks to consider in producing an overall lookup result, and to select among said plurality of associative memory block lookup results based on the indication of the plurality of associative memory blocks to consider in producing the overall lookup result.

12. The associative memory device of claim 11, wherein the associative memory device is configured to receive one or more previous stage results;

and wherein the output selector is configured to further select among said one or more previous stage results in addition to the plurality of associative memory blocks in producing the overall lookup result.

13. The associative memory device of claim 12, wherein the indication further indicates which of said one or more previous stage results to select among in producing the overall lookup result.

14. The associative memory device of claim 13, wherein the associative memory device is configured to receive a profile ID;

and wherein the output selector is configured to retrieve the indication of the plurality of associative memory blocks to consider from the memory based on the profile ID.

15. The associative memory device of claim 14, wherein the associative memory device is configured to receive one or more previous stage error signals indicating one or more previous stage error conditions, and to generate an error signal including said one or more previous stage error conditions.

16. The associative memory device of claim 15, further configured to identify one or more internal or communications error conditions, and wherein said error signal further identifies said one or more internal or communications error conditions.

17. The associative memory device of claim 11, wherein the associative memory device is configured to receive a profile ID;

and wherein the output selector is configured to retrieve the indication of the plurality of associative memory blocks to consider from the memory based on the profile ID.

18. The associative memory device of claim 11, comprising means to identify an enabled subset of the plurality of associative memory blocks to enable for performing a particular lookup operation;

and means to communicate an enable indication to the enabled subset of the plurality of associative memory blocks.

19. The associative memory device of claim 11, wherein each of the plurality of associative memory blocks includes one or more associative memory banks, each of said one or more associative memory banks including a plurality of associative memory entries.

20. The associative memory device of claim 11, wherein each of the plurality of associative memory blocks includes a plurality of associative memory entries.

21. An apparatus for performing lookup operations, the apparatus comprising:

a first associative memory configured to receive a lookup request and to perform a lookup operation to generate a first set of results, the first associative memory including means for identifying a first set of error conditions and means for relaying indications of the first set of results and one or more indications of the first set of error conditions to a second associative memory; and

the second associative memory, coupled to the first associative memory, configured to receive said indications of the first set of results and said indications of the first set of error conditions, the second associative memory including means for forwarding said one or more indications of the first set of error conditions to a next device.

22. The apparatus of claim 21, wherein the next device includes a third associative memory.

23. The apparatus of claim 21, wherein the first associative memory includes a plurality of associative memory entries, and the first set of error conditions includes a parity error in at least one of the plurality of associative memory entries.

24. The apparatus of claim 21, wherein the first set of error conditions includes a communication error.

25. The apparatus of claim 21, wherein the first set of error conditions includes detection of invalid control information.

26. An apparatus for generating a lookup result, the apparatus comprising:

means for retrieving an indication of a subset of a plurality of associative memory blocks to use in determining the lookup result, each of the subset of the plurality of associative memory blocks indicating an associative memory block lookup result;

means for selecting a highest priority hit result from said associative memory block lookup results from the subset of the plurality of associative memory blocks; and

means for indicating the highest priority hit result as the lookup result.

27. The apparatus of claim 26, comprising means for receiving a profile ID;

and means for identifying, based on the profile ID, the indication of the subset of the plurality of associative memory blocks to use.

28. The apparatus of claim 27, further comprising means for identifying, based on the profile ID,,which of the plurality of associative memory blocks to enable in generating the lookup result.

29. The apparatus of claim 26, wherein said means for selecting the highest priority hit result includes means for selecting from one or more previous stage results.

30. The apparatus of claim 26, wherein each of the plurality of associative memory blocks includes one or more associative memory banks, each of said one or more associative memory banks including a plurality of associative memory entries.

31. The apparatus of claim 26, wherein each of the plurality of associative memory blocks includes a plurality of associative memory entries.

32. The apparatus of claim 26, comprising means for identifying and reacting to an abort condition.

33. The apparatus of claim 26, comprising means for receiving one or more error signals from one or more previous stage results.

34. The apparatus of claim 33, comprising means for identifying and reacting to an abort condition.

35. The apparatus of claim 26, comprising means for communicating a means for indicating one or more error conditions to another device or component.

36. An apparatus for performing lookup operations and to simultaneously produce one or more lookup results, the apparatus comprising:

a plurality of associative memory blocks, each of the associative memory blocks indicating an associative memory block lookup result; and

a plurality of output selectors, each of the plurality of output selectors configured to retrieve from a memory an indication of the plurality of associative memory blocks to select among in producing a selected lookup result, and configured to select among said plurality of associative memory block lookup results based on the indication of the plurality of associative memory blocks to select among in producing the selected lookup result.

37. The apparatus of claim 36, wherein each of the plurality of output selectors is configured to receive one or more previous stage results and to further select among said one or more previous stage results in addition to the plurality of associative memory blocks in producing the selected lookup result.

38. The apparatus of claim 36, comprising means for receiving a profile ID and means for communicating the profile ID to each of the plurality of output selectors;

and wherein each of the plurality of output selectors is configured to retrieve the indication of the plurality of associative memory blocks to select among from the memory based on the profile ID.

39. The apparatus of claim 36, wherein the indication corresponding to a particular one of the plurality output selectors indicates to select none of the plurality of associative memory blocks.

40. The apparatus of claim 36, wherein each of the plurality of output selectors is configured to receive a corresponding enable indication, the enable indication including an enabled or not enabled value, wherein each of the plurality of output selectors is configured not to select among the plurality of associative memory blocks when its said corresponding enable indication includes said not enabled value.

41. The apparatus of claim 36, comprising a plurality of output buses, wherein each of the plurality of output selectors is configured to select a particular output bus of the plurality of output buses, and to signal the selected lookup result over the particular output bus.

42. The apparatus of claim 41, comprising means for receiving a profile ID and means for communicating the profile ID to each of the plurality of output selectors;

wherein each of the plurality of output selectors is configured to retrieve from the memory an indication of the particular output bus.

43. The apparatus of claim 42, wherein the particular output buses selected by at least two of the plurality of output selectors are different output buses of the plurality of output buses.