Granted Patent B1

US 7,451,267 · App. 10/948,050 · Granted Nov 11, 2008

Abstract

Claims (82)

1. A search engine device, comprising:

a content addressable memory (CAM) cell array arranged into a plurality of CAM entries that each store data values for comparison with search key values; and

a status memory block separate from the CAM cell array that includes

a leaf section having a plurality of rows that each include a plurality of bits, each such bit representing the free/not-free status of one CAM entry, and

an intermediate section having a plurality of rows that each includes a plurality of intermediate bits, each such intermediate bit indicating whether all of the CAM entries of a corresponding leaf section row have a not-free status or at least one CAM entry of the corresponding leaf section row has a free status.

2. The search engine device of claim 1 , wherein:

the status memory block comprises an array of static random access memory (SRAM) cells.

3. The search engine device of claim 1 , further including:

at least one priority encoder for receiving and encoding a highest priority bit from a selected row of the leaf section into an index value.

4. The search engine device of claim 3 , wherein:

the status memory block further includes

a next free address register that stores the address of an available CAM entry available having a free status, at least a portion of the address of the available CAM entry being generated by the at least one priority encoder.

5. The search engine device of claim 1 , further including:

an input control section for receiving at least a write address in a write operation; and

an address multiplexer having a first input coupled to the status memory block for receiving at least a next free address value, a second input coupled the input control section for receiving at least a write address, and an output coupled to the CAM cell array.

6. The search engine device of claim 1 , wherein:

the status memory block includes

the leaf section having x*y*z bits, each such bit storing a free/not-free status of one CAM entry,

an initial search section of x bits, each such bit representing a write status for a different set of y*z CAM entries, and

a priority encoder for encoding a highest priority bit from the x bits.

7. The search engine device of claim 1 , wherein:

the status memory block further includes

a priority encoder for receiving and encoding a highest priority bit from a selected row of the intermediate section.

8. The search engine device of claim 1 , wherein:

the status memory block includes

the leaf section having x*y*z bit storage locations, each of which indicates the free/not-free status of a CAM entry,

an intermediate section having x*y bit storage locations, each corresponding to a different z bits of the leaf section and indicating if any one of the corresponding z bits has a free status, and

an initial search section having x bit storage locations, each corresponding to a different y*z bits of the leaf section and indicating if any one of the corresponding y*z bits has a free status.

9. The search engine device of claim 8 , further including:

a next free address register that stores the address of an available CAM entry available for a learn operation, said available CAM entry address being a combination of binary values i, j and k, where i is an encoded value in the range of 0 to x−1, j is an encoded value in the range of 0 to y−1, and k is an encoded value from 0 to z−1.

10. An apparatus that includes a content addressable memory (CAM) for performing a learn operation, comprising:

a circuit block external to and independent from any CAM array of the apparatus, the circuit block comprising a plurality of sub-blocks;

each sub-block including a plurality of memory elements storing a free/not-free status for at least one entry of the CAM array; and

each sub-block includes a corresponding selection circuit for encoding the location of one bit from a plurality of bits provided by memory elements of the corresponding sub-block; wherein

the sub-blocks have a hierarchy with respect to one another, and

the memory elements of each sub-block store the free/not-free status of a larger number of entries of the CAM array than the memory elements of sub-blocks that are lower in the hierarchy.

11. The apparatus of claim 10 , wherein:

a lowest sub-block of the hierarchy has memory elements that each store the free/not-free status of one entry of the CAM array.

12. The apparatus of claim 11 , wherein:

each sub-block except the lowest hierarchy sub-block includes

memory elements that each store the status of an aggregation of memory element values of the next lower sub-block in the hierarchy, and

status aggregation logic that logically combines multiple memory element values of the next lower sub-block in the hierarchy to form an aggregated status value.

13. A method for tracking a free/not-free status of entries in search engine device, where such entries are compared to a search key, the method comprising the steps of:

storing free/not-free status data for each entry in a status memory that is a physically separate circuit block from the entries;

storing a free/not-free status of each entry as one bit in a lowest hierarchy level;

storing aggregation bits in at least one higher hierarchy level, each aggregation bit representing the free/not-free status for different groups of bits in the lowest hierarchy level; and

determining at least a portion of next free address by prioritizing and encoding selected bits from the lowest hierarchy level and prioritizing and encoding selected bits from the at least one higher hierarchy level.

14. The method of claim 13 , wherein:

in a find next free address operation

prioritizing aggregation bits of the at least one higher hierarchy level to determine a group of bits in the lowest hierarchy level that includes at least one bit having a free status, and encoding a storage location including such an aggregation bit to form a first part of a next free address;

prioritizing the group of bits in the lowest hierarchy level to determine a bit corresponding to a highest priority entry having a free status, and encoding a storage location including such a bit to form a second part of the next free address; and

storing the next free address in a next free address register.

15. The method of claim 14 , wherein:

each entry of the search engine has a unique address and each bit of the lowest hierarchy level corresponds to a unique address; and

in a learn operation

writing learn data to an entry corresponding to a learn address,

setting the status of the bit in the lowest hierarchy level corresponding to the learn address to not-free,

updating the status of all aggregation bits corresponding to the updated bit in the lowest hierarchy level; and

performing the find next free address operation.

16. The method of claim 14 , wherein:

in an initialization operation,

setting all bits in all hierarchy levels to a free status, and

performing a find next free address operation.

17. The method of claim 16 , wherein:

the find next free address operation further includes

reading a single row of bit values of a highest hierarchy level, and

prioritizing and encoding the bit values from the row of the highest hierarchy level to generate one portion of a next free address.

18. The method of claim 17 , wherein:

the find next free address operation further includes

reading a row of bit values in the next lower hierarchy level according to the first index value, and

prioritizing and encoding the bit values from the row of next lower hierarchy level to find a second portion of the next free address.

19. The method of claim 17 , wherein:

the find next free address operation further includes

reading a row of bit values in the lowest hierarchy level according to an index value provided from a second lowest hierarchy level,

prioritizing and encoding the bit values from the row of lowest hierarchy level to find a last index of a bit that has a free status,

combining address portions all hierarchy levels to generate the next free address value.

20. The method of claim 14 , wherein:

each entry of the search engine has a unique address and each bit of the lowest hierarchy level corresponds to a unique address; and

in an unlearn operation

setting the status of the bit in the lowest hierarchy level corresponding to an unlearn address to free,

updating the status of all aggregation bits corresponding to the updated bit in the lowest hierarchy level; and

performing the find next free address operation.

Assignments (13)