Hierarchical depth cascading of content addressable memory devices

• US 6,317,350 B1
• Filed: 06/16/2000
• Issued: 11/13/2001
• Est. Priority Date: 06/16/2000
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Srinivasan, Varadarajan, Pereira, Jose Pio
• Primary Examiner(s): MAI, SON LUU
• Application Number:
  US09/595,850
• Time in Patent Office: 515 Days
• Field of Search: 365/49, 365/189.07, 365/189.08, 711/108, 711/3, 711/128
• US Class Current: 365/49.1
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

A method and apparatus hierarchically cascades a number of memory devices to achieve a balance between the number of match flag inputs and the time required to generate the system match flag. In some embodiments, the number of match inputs required for each cascaded device and the time required to generate a system match flag are each logarithmically related to the number of cascaded devices. In one embodiment, an m-level hierarchy of groups are defined for up to n memory devices, where m=log₂n and m is an integer greater than 2. The first hierarchy is defined as including n/2 groups of 2 memory devices, the second hierarchy is defined as including n/4 groups of 4 memory devices, and so on, until a final hierarchy of one group is defined. Each group in a given hierarchical level includes a pair of groups from the preceding hierarchical level. At each hierarchical level, the match flag generated by the first of the group'"'"'s pair may be provided to each of the CAM devices in the second of the group'"'"'s pair. In other embodiments, at each hierarchical level, the match flag(s) generated by devices in the first of the pair defined in the previous hierarchical are selectively provided to devices in the second of the pair defined in the previous hierarchical level.

Claims

1. A method of cascading a plurality of memory devices, each memory device having one or more match flag inputs and a match flag output, the method comprising:

selectively connecting the match flag output of each memory device to the match flag input of one or more next memory devices to generate a system match flag indicative of match conditions in all the devices in a time that is logarithmically related to the number of memory devices.

2. The method of claim 1, further comprising resolving match priority for the memory devices.

3. The method of claim 1, further comprising connecting to a predetermined potential one or match flag inputs of each memory device that do not receive match information from other memory devices.

4. The method of claim 1, wherein the time required to generate the system match flag is t=t_mf+mα

, where t_mf is a time required to generate a match flag indicative of a match condition in one of the memory devices, and α

is a delay associated with logically combining the match flag with match information provided by one or more previous memory devices, and m is the number of match flag inputs for each memory device.

5. The method of claim 1, wherein the time required to generate the system match flag is t=t_mf+(m−

1)α

, where t_mf is a time required to generate a match flag indicative of a match condition in one of the memory devices, and α

is a delay associated with logically combining the match flag with match information provided by one or more previous memory devices, and m is the number of match flag inputs for each memory device.

6. The method of claim 1, wherein the memory devices comprise content addressable memories.

7. The method of claim 1, further comprising:

grouping the plurality of memory devices into first and second groups, the first group including a first number of the memory devices, the second group including a second number of the memory devices;

connecting the match flag output of each memory device in the first group to the match flag input of one or more other memory devices in the first group;

connecting the match flag output of each memory device in the second group to the match flag input of one or more other memory devices in the second group; and

connecting the match flag output of a last memory device in the first group to respective match flag inputs of a first memory device and a last memory device in the second group.

8. The method of claim 7, wherein the first number equals the second number.

9. The method of claim 7, wherein the memory devices comprise content addressable memories.

10. The method of claim 7, further comprising connecting the match flag output of the last memory device in the first group to respective match flag inputs of each memory device in the second group.

11. A method of generating a system match flag indicative of match conditions in a plurality of memory devices, comprising:

grouping the plurality of memory devices into first and second groups;

combining match information in memory devices of the first group to generate a first group match flag;

simultaneously combining match flag information in memory devices of the second group; and

combining the first group flag with the combined match information from the second group to generate the system match flag.

12. The method of claim 11, wherein the first memory device comprises a highest priority-device in the second group and the last memory device comprises a lowest-priority device in the second group.

13. The method of claim 11, wherein generating the first group match flag comprises:

generating, for each memory device, an internal match flag indicative of match conditions therein; and

combining the internal match flags of the memory devices in the first group.

14. The method of claim 13, wherein the first group match flag is provided to a highest-priority memory device in second group to resolve priority therein.

15. The method of claim 14, wherein combining match information in the memory devices of the second group comprises combining internal match flags of the memory devices in the second group.

16. The method of claim 11, wherein the first group match flag is provided to each memory device in the second group.

17. A cascaded configuration of n memory devices each having no more than m=log₂n match flag inputs selectively connected to receive match information from some but not all of the other memory devices, where n≧

4 and m≧

2.

18. The configuration of claim 17, wherein the memory devices are grouped into first and second groups, the configuration further comprising:

means for connecting a match flag output of each memory device in the first group to the match flag input of one or more devices in the first group;

means for connecting a match flag output of each memory device in the second group to the match flag input of one or more devices in the second group; and

means for connecting the match flag output of a last device in the first group to respective match flag inputs of a first and a last memory device of the second group.

19. The configuration of claim 18, wherein the first memory device comprises a highest priority-device in the second group and the last memory device comprises a lowest-priority device in the second group.

20. The configuration of claim 18, wherein the match flag output of the last device in the first group is connected to respective match flag inputs of each memory device in the second group.

21. The configuration of claim 18, wherein the memory devices comprise content addressable memories.

22. The configuration of claim 17, comprising:

a first group including a first number of the memory devices, each having one or more match flag inputs connected only to one or more other corresponding memory devices in the first group; and

a second group including a second number of the memory devices, each having a match flag output connected only to a match flag input of one or more other memory devices in the second group;

wherein the match flag output of a last memory device in the first group is connected to respective match flag inputs of a first memory device and a last memory device in the second group.

23. The configuration of claim 22, wherein the match flag output of the last memory device in the first group is connected to respective match flag inputs of all memory devices in the second group.

24. The configuration of claim 22, wherein the match flag output of the last memory device in the first group provides a first group match flag indicative of match conditions in the first group of memory device.

25. The configuration of claim 24, wherein the match flag output of the last memory device in the second group provides a system match flag indicative of match conditions in all the memory devices.

26. The configuration of claim 24, wherein the first memory device in the second group comprises a highest-priority device in the second group, and the last memory device in the second group comprises a lowest-priority device in the second group.

27. The configuration of claim 22, wherein a time required to generate the system match flag is logarithmically related to the number of cascaded memory devices.

28. The configuration of claim 22, wherein a time required to resolve priority in all the memory devices is logarithmically related to the number of cascaded memory devices.

29. The configuration of claim 22, wherein the memory devices comprise content addressable memories.

30. The configuration of claim 28, wherein the first and second groups comprise equal numbers of the memory devices.

31. A cascaded configuration of memory devices, comprising:

a first memory device having a match flag output;

a second memory device having a match flag input connected to the match flag output of the first memory device, and having a match flag output;

a third memory device having a match flag input connected to the match flag output of the second memory device, and having a match flag output; and

a fourth memory device having a first match flag input connected to the match flag output of the second memory device, and having a second match flag input connected to the match flag output of the third memory device.

32. The configuration of claim 31, wherein a match flag output of the fourth memory device provides a system match flag indicative of match conditions in all the memory devices.

33. The configuration of claim 31, wherein the match flag output of the first memory device is connected to a third match flag input of the fourth memory device.

34. The configuration of claim 31, wherein the memory devices comprise content addressable memories.

35. The configuration of claim 31, wherein the number of match flag inputs is a logarithmic function of the number of memory devices.

36. The configuration of claim 31, wherein the memory devices have no more than two match flag inputs.

37. The cascaded configuration of claim 31, wherein a time required to generate a system match flag indicative of match conditions in all the memory devices is a logarithmic function of the number of memory devices.

38. The cascaded configuration of claim 31, further comprising:

a fifth memory device having a match flag input connected to the match flag output of the fourth memory device, and having a match flag output;

a sixth memory device having a first match flag input connected to the match flag output of the fifth memory device, and having a match flag output;

a seventh memory device having a match flag input connected to the output match flag of the sixth memory device, and having a match flag output; and

an eighth memory device having a first match flag input connected to the match flag output of the fourth memory device, having a second match flag input connected to the output match flag of the sixth memory device, and having a third match flag input connected to the match flag output of the seventh memory device.

39. The cascaded configuration of claim 38, wherein a match flag output of the eighth memory device provides a system match flag indicative of match conditions in all the memory devices.

40. The cascaded configuration of claim 38, wherein:

the match flag output of the fourth memory device is connected to a second match flag input of the sixth memory device and to a second match flag input of the seventh memory device.

41. The cascaded configuration of claim 33, further comprising:

a fifth memory device having a match flag input connected to the match flag output of the fourth memory device, and having a match flag output;

a sixth memory device having a first match flag input connected to the match flag output of the fourth memory device, and having a match flag output;

a seventh memory device having a first match flag input connected to the match flag output of the fourth memory device, having a second match flag input connected to the output match flag of the sixth memory device, and having a match flag output; and

an eighth memory device having a first match flag input connected to the match flag output of the fourth memory device, having a second match flag input connected to the output match flag of the fifth memory device, and having a third match flag input connected to the output match flag of the seventh memory device.

42. A method of cascading a number n of memory devices each having one or more match flag inputs and a match flag output, the method comprising:

defining a first number of first groups at a first hierarchical level to each include first and second memory devices;

connecting, within each of the first groups, the match flag output of the first memory device to the match flag input of the second memory device;

defining a second number of second groups at a second hierarchical level to each include a pair of the first groups defined at the first hierarchical level; and

connecting, within at least one of the second groups, the match flag output of a last memory device of a first of the corresponding pair of first groups to respective match flag inputs of a first and of a last of the second of the pair of first groups.

43. The method of claim 42, wherein the match flag output of the last memory device in the first of the pair of first groups is connected to respective match flag inputs of each memory device in the second of the pair of first groups.

44. The method of claim 42, wherein the first memory device of the second of the pair of first groups comprises a highest priority-device therein, and the last memory device of the second of the pair of first groups comprises a lowest-priority device therein.

45. The method of claim 42, wherein the memory devices comprises content addressable memories.

46. The method of claim 42, further comprising:

defining a third number of third groups at a third hierarchical level to each include a pair of the second groups defined at the second hierarchical level; and

connecting, within at least one of the third groups, the match flag output of a last memory device of a first of the corresponding pair of second groups to respective match flag inputs of a first and of a last of the second of the pair of second groups.

47. The method of claim 46, further comprising repeating the defining and connecting steps until a final group including all the memory devices is defined at an m^th hierarchical level, where m=log₂n.

48. A method of cascading up to n memory devices, the method comprising:

defining first groups at a first hierarchical level to each include first and second memory devices;

providing, within each of the first groups, a match flag indicative of match conditions in the first memory device to the second memory device;

defining second groups at a second hierarchical level to each include a pair of the first groups defined at the first hierarchical level; and

providing, within at least one of the second groups, a match flag indicative of match conditions in a first of the pair of first groups to at least a first and a last memory device of a second of the pair of the first groups.

49. The method of claim 48, wherein the match flag indicative of match conditions in the first of the pair of first groups is providing to each memory device in the second of the pair of the first groups.

50. The method of claim 48, wherein the first memory device of a group comprises a highest priority-device therein, and the last memory device of the group comprises a lowest-priority device therein.

51. The method of claim 48, wherein the memory devices comprises content addressable memories.

52. The method of claim 48, further comprising:

defining a number of third groups at a third hierarchical level to each include a pair of the second groups defined at the second hierarchical level; and

connecting, within at least one of the third groups, the match flag output of a last memory device of a first of the corresponding pair of second groups to respective match flag inputs of a first and of a last of the second of the pair of second groups.

53. The method of claim 52, further comprising repeating the defining and connecting steps until a final group is defined at an m^th hierarchical level, where m=log₂n.