Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-07-06
2003-10-21
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S169000, C711S167000
Reexamination Certificate
active
06636956
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to memory management of data structures in a striped pipelined set of memories.
2. Related Art
In a pipelined data structure such as described in the incorporated disclosures, a sequence of memories are used for pipelined lookup and update operations on a compact data structure in a pipelined architecture. As described in the incorporated disclosures, the data structure is maintained in a sequence of memories. It is desirable to manage use of those memories so that update operations can be performed for those data structures while simultaneously maintaining (a) low worst-case memory requirement, that is, relatively good worst-case memory utilization, (b) low update complexity, that is low complexity of hardware and software for update operations, and (c) low worst-case time requirement, that is, relatively good worst-case speed.
Accordingly it would be desirable to have a technique for update operations performed on a compact data structure in a pipelined architecture, in which the data structure includes stripe for a set of nodes in a hybrid trie, and that simultaneously maintains the desirable features noted above. It would be advantageous if that technique were well adapted to pipelined operation, such as further described in the incorporated disclosures. The following features would be advantageous:
It would be advantageous if that technique were capable of relatively rapid insertion of new data elements while minimizing time requirements.
It would be advantageous if that technique were capable of relatively rapid removal of old data elements while minimizing time requirements.
These advantages and others are provided in an embodiment of the invention, described herein, including a memory management technique in which individual nodes in a hybrid trie are striped across a set of pipelined memories.
SUMMARY OF THE INVENTION
The invention provides a method and system for memory management, in which at least some individual nodes in a hybrid trie are striped across a set of pipelined memories. Memory management is performed for a hybrid trie including both branch-search nodes and leaf-search nodes and maintained in a sequence of pipelined memories. The method of memory management provides for insertion and removal of data elements within the hybrid trie and for storing at least some of the nodes (the leaf-search nodes) in stripes across a sequence of the memories. Memory management is performed for the leaf-search nodes (those nodes that are stored in stripes across a sequence of the memories), by selecting stripes from the possible subsequences of those memories, that are suited to pipelined operations performed on the memories. In a preferred embodiment, an invariant condition is maintained for families of those stripes, in which exactly one cell block in each family is labeled “sparse” and that cell block is used in techniques for allocation and de-allocation of entries.
The invention has general applicability to memory management in which data structures are distributed across a set of distinct memories. None of the e applications are limited specifically to update operations for hybrid tries, or to data strictures for lookup of message header information, nor are they necessarily related to the specific applications disclosed herein.
REFERENCES:
patent: 5652581 (1997-07-01), Furlan et al.
patent: 5956340 (1999-09-01), Afek et al.
patent: 6008820 (1999-12-01), Chauvin et al.
patent: 6209020 (2001-03-01), Angle et al.
patent: 6343072 (2002-01-01), Bechtolsheim et al.
Gupta Pankaj
Rangarajan Anand
Venkatachary Srinivasan
Conley & Rose, P.C.
Cypress Semiconductor Corp.
Daffer Kevin L.
Elmore Reba I.
LandOfFree
Memory management of striped pipelined data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management of striped pipelined data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management of striped pipelined data structures will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159131