Patent ID: 7472133

Claim:
A method for prefetching data by resuming a prefetch after stalling at a missing node in a node structure, the method comprising: identifying a parent node in the node structure that is a parent of the missing node; storing state information for the missing node and at least one ancestor node of the missing node after stalling at the missing node; determining, as a function of the state information, whether the parent node has been changed since stalling at the missing node; and if not, then resuming the prefetch from the missing node; and if so, then selecting a node in the node structure from which to resume the prefetch by determining whether the parent node is still allocated and linked to the node if not, then resuming the prefetch from another node in the node structure; and if so, then searching the parent node and determining whether a target of the prefetch is within the parent node; if not, resuming the prefetch from another node in the node structure; and if so, then resuming the prefetch from the parent node, whereby resuming the prefetch from the missing node or the selected node reduces processing time associated with the prefetch.