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 7,065,609 B2
• Filed: 08/10/2002
• Issued: 06/20/2006
• Est. Priority Date: 08/10/2002
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Farrokh, Hashem
• Application Number:
  US10/215,700
• Publication Number:
  US 20040030802A1
• Time in Patent Office: 1,410 Days
• Field of Search: 711/105, 711/125, 711/143, 711/158, 711205-208, 711/108, 711/212, 709/238, 709/245, 370401-402, 370/453
• US Class Current: 711/108
• 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 performed by an associative memory for generating a lookup result in the associative memory, the associative memory including a plurality of associative memory blocks, the method comprising:

receiving a profile ID;

retrieving an indication of a subset of the plurality of associative memory blocks to use in determining the lookup result from a memory based on the profile ID, 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, further comprising identifying, based on the profile ID, which of the plurality of associative memory blocks to enable in generating the lookup result.

3. 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.

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

5. 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 a particular one of the plurality of output buses.

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

wherein said selecting is performed based on the indication.

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

wherein said selecting the particular one of the plurality of output buses is performed based on the indication of the particular one of the output buses.

8. The method of claim 7, wherein said retrieving from the memory the indication of the particular one of the output buses is performed based on the profile ID.

9. The method of claim 5, wherein each of the plurality of output buses is configured to communicate the selected lookup result to a different set of one or more pins of an associative memory.

10. 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;

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.

11. The associative memory device of claim 10, 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.

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

13. The associative memory device of claim 10, 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.

14. The associative memory device of claim 13, 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.

15. The associative memory device of claim 10, 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.

16. The associative memory device of claim 10, 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.

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

18. 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.

19. The apparatus of claim 18, wherein the next device includes a third associative memory.

20. The apparatus of claim 18, 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.

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

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

23. An associative memory for generating a lookup result, the associative memory including a plurality of associative memory blocks, the associative memory comprising:

means for retrieving an indication of a subset of the 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; and

means for identifying and reacting to an abort condition.

24. The associative memory of claim 23, 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.

25. The associative memory of claim 23, wherein each of the plurality of associative memory blocks includes a plurality of associative memory entries.

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

27. An associative memory for generating a lookup result, the associative memory including a plurality of associative memory blocks, the associative memory comprising:

means for receiving a profile ID;

means for identifying, based on the profile ID an indication of a subset of the 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.

28. The associative memory 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. An associative memory for generating a lookup result, the associative memory including a plurality of associative memory blocks, the associative memory comprising:

means for retrieving an indication of a subset of the 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;

means for indicating the highest priority hit result as the lookup result; and

means for receiving and reacting to one or more error signals from one or more previous stage results.

30. The associative memory of claim 29, comprising means for identifying and reacting to an abort condition.

31. 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 are coupled to each of the plurality of associative memory blocks and 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.

32. The apparatus of claim 31, 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.

33. The apparatus of claim 31, 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.

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

35. The apparatus of claim 31, 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.

36. The apparatus of claim 31, 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.

37. 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;

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

38. The apparatus of claim 37, 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.