Methods for prefetching data in a memory storage structure
A method includes detecting a cache miss. The method further includes, in response to detecting the cache miss, traversing a plurality of linked memory nodes in a memory storage structure being used to store data to determine if the memory storage structure is a binary tree. The method further includes, in response to determining that the memory storage structure is a binary tree, prefetching data from the memory storage structure. An associated machine readable medium is also disclosed.
1. A method comprising:
detecting a cache miss,
in response to detecting the cache miss, traversing a plurality of linked memory nodes in a memory storage structure being used to store data to determine if the memory storage structure is a binary tree, and
in response to determining that the memory storage structure is a binary tree, prefetching data from the memory storage structure.
2. The method of claim 1 , wherein the detecting a cache miss comprises determining that a predetermined number of cache misses have occurred for a load operation.
3. The method of claim 1 , wherein the prefetching data from the memory storage structure comprises prefetching data from a sibling node of at least one of the plurality of memory nodes traversed.
4. The method of claim 1 , wherein the traversing a plurality of linked memory nodes in a memory storage structure to determining if the memory structure is a binary tree comprises traversing a plurality of linked memory nodes in the memory storage structure to determine if the plurality of linked memory nodes form a subtree of a binary tree.
5. A method comprising:
detecting a cache miss,
in response to detecting the cache miss, determining if a plurality of linked memory nodes in a memory storage structure form a binary tree, and
in response to the determining, prefetching data from a portion of the plurality of linked memory nodes.
6. The method of claim 5 , wherein the determining if a plurality of linked memory nodes in a memory storage structure form a binary tree comprises traversing the plurality of linked memory nodes to determine if the plurality of linked memory nodes form a subtree of a binary tree.
7. The method of claim 5 , wherein the prefetching data from a portion of the plurality of linked memory nodes comprises prefetching data from at least one sibling node of the plurality of linked memory nodes.
8. The method of claim 5 , wherein the prefetching data from a portion of the plurality of linked memory nodes comprises prefetching data from a sibling node of at least one leaf node of the plurality of linked memory nodes.
9. A machine readable medium comprising a plurality of instructions, that in response to being executed, result in a computing device
detecting a data transfer miss from a memory device,
in response to detecting the data transfer miss, determining a type of memory storage structure being used to store data, wherein the memory storage structure is evaluated to determine whether the structure is a binary tree structure, and
in response to determining the type of memory storage structure, prefetching data from the memory storage structure.
10. The machine readable medium of claim 9 , wherein the plurality of instructions further result in a computing device determining that a predetermined number of data transfer misses have occurred for a load operation.
11. The machine readable medium of claim 9 , wherein the plurality of instructions further result in a computing device traversing a plurality of linked memory nodes in the memory storage structure to determine the type of memory storage structure.
12. The machine readable medium of claim 9 , wherein the plurality of instructions further result in a computing device traversing a plurality of linked memory nodes in the memory storage structure to determine if the memory storage structure is a binary tree.
13. The machine readable medium of claim 12 , wherein the plurality of instructions further result in a computing device prefetching data from a sibling node of at least one of the plurality of memory nodes traversed.
14. The machine readable medium of claim 9 , wherein the plurality of instructions further result in a computing device traversing a plurality of linked memory nodes in the memory storage structure to determine if the plurality of linked memory nodes form a subtree of a binary tree.
15. The method as recited in claim 1 , wherein the determining that the memory storage structure is a binary tree further comprises evaluating the memory storage structure using pattern recognition.
16. The method as recited in claim 5 , wherein the determining if a plurality of linked memory nodes in a memory storage structure form a binary tree further comprises evaluating the memory storage structure using pattern recognition.
17. The medium as recited in claim 9 , wherein the evaluation to determine whether the structure is a binary tree structure further comprises instructions to evaluate the memory storage structure using pattern recognition.