Method and system for storing sparse data in memory and accessing stored sparse data
First Claim
1. A method for storing a data entity having an index in a computer within a data structure having multiple node levels, the method comprising:
- providing a hierarchical data structure for indexing stored data entities, the hierarchical data structure having a root level, one or more intermediate levels, and a data level, each level containing at least one node, each node having at least one entry;
storing virtual-memory translations for an address of a lower-level node in each intermediate and root node;
traversing the levels of the hierarchical data structure, starting from a root node, accessing each lower-level node on a traversal path using a virtual-memory translation obtained from a next highest level node; and
storing the data entity in a lowest level node.
4 Assignments
0 Petitions
Accused Products
Abstract
One embodiment of the present invention provides a hierarchical data structure for storing sparse data that can be traversed from root node to data-level node without incurring translation-cache misses. By contrast with currently used hierarchical data structures, the family of hierarchical data structures that represent one embodiment of the present invention employs non-data-level nodes that contain virtual-memory translations rather than memory references. The family of hierarchical data structures that represent one embodiment of the present invention are traversed from root node through successive layers of non-data-level nodes to data-level nodes in a manner similar to traversal of currently used hierarchical data structures. However, in the family of hierarchical data structures that represent one embodiment of the present invention, the address of a next-lower-level node is computed from a base address of the next-lowest level, and the computed address is furnished, along with the virtual-memory translation stored in a higher-level node, in order to access the next-lower-level node.
-
Citations
25 Claims
-
1. A method for storing a data entity having an index in a computer within a data structure having multiple node levels, the method comprising:
-
providing a hierarchical data structure for indexing stored data entities, the hierarchical data structure having a root level, one or more intermediate levels, and a data level, each level containing at least one node, each node having at least one entry;
storing virtual-memory translations for an address of a lower-level node in each intermediate and root node;
traversing the levels of the hierarchical data structure, starting from a root node, accessing each lower-level node on a traversal path using a virtual-memory translation obtained from a next highest level node; and
storing the data entity in a lowest level node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for transforming a hierarchical data structure that includes virtual-memory addresses in a root node and in intermediate level nodes into a computationally efficient hierarchical data structure, the method comprising:
-
arranging nodes of each level within contiguous blocks of virtual memory having base addresses, so that a position of a node within a level can be calculated as the base address for the level added to a node size for the level multiplied by an index for the node within the level;
replacing the virtual-memory addresses within the root node and intermediate-level nodes with translation cache entries corresponding to the virtual-memory addresses; and
when traversing the levels of the computationally efficient hierarchical data structure, starting from a root node, accessing each lower-level node on a traversal path using a virtual-memory translation obtained from a next highest level node. - View Dependent Claims (11, 12, 13, 14, 15, 16, 18, 19)
-
-
17. A method for storing data entities in a computer within a data structure having multiple levels of nodes, the method comprising:
-
allocating memory for a root node;
determining a number of levels for the data structure, including a root level, intermediate non-data-level levels, and a data level;
determining a number of entries for nodes of each level;
reserving contiguous virtual-memory blocks for intermediate levels; and
when storing a next data entity having a next data index, setting a current node as the root node, a current level as a highest level of the data structure, and a remaining data index as the next data index, while the current level is greater than a lowest, data level, calculating a current entry index by an integer division of the remaining data index by a product of the number of entries for nodes of each level of the data structure below the current level, setting the remaining data index to a remainder of the integer division, accessing an entry in the current node indexed by the current entry index to obtain a virtual-memory translation, when the virtual-memory translation has a distinguished value, allocating a new node for the next lowest level from the corresponding contiguous virtual-memory block for the next lowest level, and placing a virtual-memory translation for the new node into the entry in the current node indexed by the current entry index, and updating the current node to the node of a next lowest level node having a node index obtained by setting the current node index to the current entry index added to the sum of the node index of the current node and the number of entries in the current node, and setting the current level to a next lowest level of the data structure;
storing the data value in an entry in the current node indexed by the remaining data index.
-
-
20. A system for storing and retrieving data comprising:
-
a computer system having a virtual memory;
a number of reserved blocks of contiguous virtual memory, each reserved block corresponding to a level, including a highest, root level, one or more intermediate levels, and a lowest, data level;
a computationally efficient hierarchical data structure that includes at least one node in each reserved block corresponding to each level, each node in a level higher than the data level containing translation-cache entries corresponding to the virtual addresses of nodes in the next lowest level, and each node in the lowest level containing data; and
computer routines for traversing the computationally efficient hierarchical data structure to locate an entry in a data-level node corresponding to a data value with a specified index. - View Dependent Claims (21, 22, 23, 24, 25)
-
Specification