Handle allocation managers and methods for integated circuit search engine devices
View Patent ↗A handle allocation manager is provided for an integrated circuit search engine device that includes multiple stages of a multilevel tree of search keys and a handle memory. The handle allocation manager includes a handle availability memory that stores handle availability indicators to provide an indication of whether a handle is available for association with a key. A handle availability summary memory stores indicators for groups of handles and a block availability summary memory stores indicators for multiple groups of handle availability summary memories. The handle allocation manager can use these memories to search for a next available handle. Related methods are also provided.
1. An integrated circuit search engine device, comprising:
a plurality of serially connected stages, a respective one of which is configured to store therein a respective level of search keys in a multilevel tree of search keys, the plurality of serially connected stages including a first level stage that is responsive to an input search key and a last level stage that is configured to identify a best match key for the input search key;
a handle memory including a plurality of handle memory locations, a respective one of which is configured to store a search result handle, the handle memory being responsive to the last level stage to retrieve a search result handle that corresponds to the best match key; and
a handle allocation manager including a handle availability memory that is configured to store therein a plurality of handle availability indicators, a respective one of which provides an indication of whether a respective handle is available for association with a corresponding key.
2. A device according to claim 1 wherein the handle allocation manager further comprises a handle availability summary memory that is configured to store therein a plurality of handle memory group availability indicators, a respective one of which provides an indication of whether a respective group of handle memory locations contains at least one handle availability indicator.
3. A device according to claim 2 wherein the handle allocation manager further comprises a block availability summary memory that is configured to store therein a plurality of handle memory block availability indicators, a respective one of which provides an indication of whether a respective plurality of groups of handle availability summary memory locations contain at least one handle memory group availability indicator.
4. A device according to claim 3 wherein the handle allocation manager is further configured to search the handle availability memory, the handle availability summary memory and the block availability summary memory to identify a next available handle.
5. A device according to claim 4 wherein the handle allocation manager is further configured to search the handle availability memory, the handle availability summary memory and the block availability summary memory to identify a next available handle by searching the block availability summary memory in a given sequence to identify a first handle block availability indicator and a corresponding handle block, then searching the handle availability summary memory corresponding the handle block in a given sequence to identify a first handle group availability indicator and a corresponding group of handles, and then searching the handle availability memory for the corresponding group of handles in a given sequence to identify a first handle availability indicator and a corresponding next available handle.
6. A device according to claim 4 wherein the handle allocation manager is further configured to mark the next available handle as not available in response to associating the next available handle with a key, to mark the handle memory summary location that includes the next available handle as not available if no more available handles are present in the corresponding handle group and to mark the block availability summary memory location that includes the handle memory summary location as not available if no more available handles are present in the corresponding block.
7. A device according to claim 3 wherein the handle allocation manager is further configured to mark a given available handle as not available in response to associating the given available handle with a key, to mark the handle memory summary location that includes the given available handle as not available if no more available handles are present in the corresponding handle group and to mark the block availability summary memory that includes the given handle memory summary location as not available if no more available handles are present in the corresponding block.
8. A device according to claim 2 wherein the handle allocation manager is further configured to search the handle availability memory and the handle availability summary memory to identify a next available handle.
9. A device according to claim 8 wherein the handle allocation manager is further configured to search the handle availability memory and the handle availability summary memory to identify a next available handle by searching the handle availability summary memory in a given sequence to identify a first handle memory group availability indicator and a corresponding group of handles, and then searching the handle availability memory for the corresponding group of handles in a given sequence to identify a first handle availability indicator and a corresponding next available handle.
10. A device according to claim 8 wherein the handle allocation manager is further configured to mark the next available handle as not available in response to associating the next available handle with a key, and to mark the handle memory summary location that includes the next available handle as not available if no more available handles are present in the corresponding handle group.
11. A device according to claim 2 wherein the handle allocation manager is further configured to mark a given available handle as not available in response to associating the given available handle with a key, and to mark the handle memory summary location that includes the given available handle as not available if no more available handle memory locations are present in the corresponding handle group.
12. A device according to claim 1 wherein the handle allocation manager is further configured to search the handle availability memory to identify a next available handle.
13. A device according to claim 12 wherein the handle allocation manager is further configured to mark the next available handle as not available in response to associating the next available handle with a key.
14. A device according to claim 12 wherein the handle allocation manager is further configured to search the handle availability memory to identify a next available handle by indexing into the handle availability memory using the search result handle that is retrieved.
15. A device according to claim 1 wherein the handle allocation manager is configured to mark a given available handle as not available in response to associating the given available handle with a key.
16. A device according to claim 1 :
wherein each of the serially connected stages is configured to store therein a respective level of search keys in a plurality of multilevel trees of search keys for a plurality of databases;
wherein the handle memory is configured to store search result handles for the plurality of databases; and
wherein the handle allocation memory is configured to store therein a plurality of handle availability indicators for the plurality of handles for the plurality of databases.
17. A device according to claim 16 wherein the handle availability memory includes at least one group block that is configured to store therein handle availability indicators for at least two of the databases.
18. A device according to claim 17 wherein the handle availability memory includes at least one common block that is configured to store therein handle availability indicators for all of the databases.
19. A device according to claim 18 wherein the handle availability memory includes at least one exclusive block that is configured to store therein handle availability indicators for a predetermined one of the databases.