Content addressable memory with programmable word width and programmable priority

• US 7,246,198 B2
• Filed: 06/15/2005
• Issued: 07/17/2007
• Est. Priority Date: 09/23/1999
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan, Gharia, Nilesh A., Pereira, Jose P., Wong, Hok F., Roy, Rupesh R.
• Primary Examiner(s): Elmore; Reba I.
• Application Number:
  US11/154,066
• Publication Number:
  US 20050262295A1
• Time in Patent Office: 762 Days
• Field of Search: 711/108
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• 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
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: G11C 8/04 using a sequential addressing device, e.g. shift register, counter
• CPC Class Codes: H03K 23/56 Reversible counters H03K23/52 and H03K23/548 take precedence
• CPC Class Codes: H03K 3/356139 with synchronous operation

Abstract

A content addressable memory (CAM) device including a CAM array and a priority index table. The CAM array has a plurality of rows of CAM cells, each row including a plurality of row segments and being adapted to store a data word that spans a selectable number of the row segments. The priority index table is coupled to the plurality of rows of CAM cells and is adapted to store a plurality of priority numbers, each priority number being indicative of a priority of a corresponding data word stored in the CAM array.

Claims

1. A content addressable memory (CAM) device comprising:

a plurality of CAM arrays;

a plurality of configuration registers to store respective configuration values that control a logical storage depth and width of each of the plurality of CAM arrays; and

a plurality of priority tables coupled respectively to the plurality of CAM arrays, each of the priority tables including circuitry to store a plurality of priority numbers that indicate relative priorities of entries within the corresponding CAM array.

2. The CAM device of claim 1 wherein each of the plurality of CAM arrays includes a plurality of rows of CAM cells, each of the rows of CAM cells including a plurality of row segments that include a respective portion of the CAM cells for the row, and wherein each of the configuration values indicates, for a corresponding one of the CAM arrays, a number N of the row segments that are applied to store a data word.

3. The CAM device of claim 1 wherein at least one of the CAM arrays comprises Y rows of CAM cells each segmented into Z row segments with W CAM cells per row segment, and wherein one of the configuration values that corresponds to the at least one of the CAM arrays indicates a logical storage depth and width that ranges at least from a depth of Y logical rows by a width of W×

Z CAM cells to a depth of Y×

Z logical rows by a width of W CAM cells, where ‘

×

’

denotes multiplication.

4. The CAM device of claim 1 wherein each of the configuration values further controls a logical storage depth of each of the priority tables such that the logical storage depth of each priority table matches the logical storage depth of the corresponding CAM array.

5. The CAM device of claim 1 further comprising a plurality of priority encoders coupled to the plurality of priority tables, each to output a respective block index value during a search operation within the CAM device.

6. The CAM device of claim 5 wherein each of the priority encoders is coupled to receive match signals from a corresponding one of the priority tables and the configuration value from a respective one of the configuration registers, each of the priority encoders including circuitry to combine groups of two or more of the match signals if the configuration value indicates a logical CAM array depth less than a maximum CAM array depth.

7. The CAM device of claim 5 wherein each of the priority tables further includes circuitry to compare the priority numbers stored within the priority table during a search operation to output, as a block priority number, a highest-priority priority number associated with an comparand-matching entry within the corresponding CAM array.

8. The CAM device of claim 7 further comprising a global priority encoder coupled to receive, during a search operation, the block priority numbers output from the plurality of priority tables and the block index values output from the plurality of priority encoders.

9. The CAM device of claim 8 wherein the global priority encoder includes circuitry to determine a highest-priority one of the block priority numbers and to output, as a match address, one of the block index values that corresponds to the highest-priority one of the block priority numbers and a value that indicates which of the CAM arrays sourced the one of the block index values.

10. The CAM device of claim 2 wherein each of the configuration registers includes storage circuitry to store a search-mode value that indicates a type of search to be performed within a corresponding one of the CAM arrays.

11. The CAM device of claim 10 wherein at least one of the types of search that may be indicated by the search-mode value is a longest-prefix match search.

12. The CAM device of claim 10 wherein at least one of the types of search that may be indicated by the search-mode value is a packet classification search.

13. The CAM device of claim 1 wherein each of the configuration registers includes storage circuitry to store a data-type value that indicates a type of data to be stored within a corresponding one of the CAM arrays.

14. A method of operation within a CAM device, the method comprising:

storing configuration values within a plurality of configuration registers to define logical storage depths and widths for each of a plurality of CAM arrays; and

storing priority numbers within a plurality of priority tables that correspond respectively to the plurality of CAM arrays, the priority numbers within each of the priority tables indicating relative priorities of entries within the corresponding CAM array.

15. The method of claim 14 wherein each of the plurality of CAM arrays includes a plurality of rows of CAM cells, each of the rows of CAM cells including a plurality of row segments that include a respective portion of the CAM cells for the row, and wherein storing configuration values within a plurality of configuration registers to define logical storage depths and widths for each of a plurality of CAM arrays comprises storing at least one configuration value that indicates, for a corresponding one of the CAM arrays, a number N of the row segments that are applied to store a data word.

16. The method of claim 14 wherein at least one of the CAM arrays comprises Y rows of CAM cells each segmented into Z row segments with W CAM cells per row segment, and wherein storing configuration values within a plurality of configuration registers to define logical storage depths and widths for each of a plurality of CAM arrays comprises storing at least one configuration value that indicates, for a corresponding one of the CAM arrays, a logical storage depth and width that ranges at least from a depth of Y logical rows by a width of W×

Z CAM cells to a depth of Y×

Z logical rows by a width of W CAM cells, where ‘

×

’

denotes multiplication.

17. The method of claim 14 wherein each of the configuration values further controls a logical storage depth of each of the priority tables such that the logical storage depth of each priority table matches the logical storage depth of the corresponding CAM array.

18. The method of claim 14 further comprising:

performing a search operation within a first CAM array of the CAM arrays to generate a plurality of match signals that correspond respectively to the priority numbers stored within the priority table that corresponds to the first CAM array;

determining a highest-priority priority number from among the priority numbers for which the corresponding to match signals indicate a match detection; and

generating a block index that indicates a location within the first CAM array of an entry that corresponds to the highest-priority priority number.

19. The method of claim 18 further comprising outputting the highest-priority priority number from the priority table that corresponds to the first CAM array and comparing the highest-priority priority number with one or more highest-priority priority numbers output from other CAM arrays of the plurality of CAM arrays to determine a device priority number.

20. The method of claim 19 further comprising outputting, as a device index, a value that indicates which of the priority tables sourced the device priority number and one of a plurality of block indices selected according to the value that indicates which of the priority tables sourced the device priority number, the plurality of block indices including the block index that indicates the location within the first CAM array of the entry that corresponds to the highest-priority priority number.

21. The method of claim 14 further comprising storing in each of the configuration registers a value that indicates a type of search to be performed within a corresponding one of the CAM arrays.

22. The method of claim 14 further comprising storing in each of the configuration registers a value that indicates a type of data to be stored within a corresponding one of the CAM arrays.

23. A content addressable memory (CAM) device comprising:

a plurality of CAM arrays;

means for storing configuration values within a plurality of configuration registers to define logical storage depths and widths for each of the plurality of CAM arrays; and

means for storing a plurality of sets of priority numbers, each set of priority numbers to indicate relative priorities of entries within a respective one of the CAM arrays.