Method and apparatus for prefetching recursive data structures

Abstract

Computer systems are typically designed with multiple levels of memory hierarchy. Prefetching has been employed to overcome the latency of fetching data or instructions from or to memory. Prefetching works well for data structures with regular memory access patterns, but less so for data structures such as trees, hash tables, and other structures in which the datum that will be used is not known a priori. The present invention significantlyA system and method is provided that increases the cache hit rates of many important data structure traversals, and thereby the potential throughput of the computer system and application in which it is employed. The invention This is applicable to those data structure accesses in which the traversal path is dynamically determined. The invention does this This is done by aggregating traversal requests and then pipelining the traversal of aggregated requests on the data structure. Once enough traversal requests have been accumulated so that most of the memory latency can be hidden by prefetching the accumulated requests, the data structure is traversed by performing software pipelining on some or all of the accumulated requests. As requests are completed and retired from the set of requests that are being traversed, additional accumulated requests are added to that set. This process is repeated until either an upper threshold of processed requests or a lower threshold of residual accumulated requests has been reached. At that point, the traversal results may be processed.

I claim: 
     
       1. A method of scheduling units of work for execution on a computer system including a data cache or data cache hierarchy, the method comprising the steps of:
 buffering a plurality of transactions on a data structure;   scheduling a plurality of said transactions on said data structures in a loop;   issuing prefetch instructions within the body of said loop for the data required to process said transactions.   
     
     
       2. The method of buffering the results of the transactions processed on a computer system in accordance with  claim 1 , wherein the results are buffered as well, thereby allowing multiple results to be processed together at a later time. 
     
     
       3. The method of processing the results of a completed traversal on a data structure on a computer system according to  claim 1  once a traversal of the data structure has completed. 
     
     
       4. The method of associating a request identifier with each transaction on a data structure represented on a computer system according to  claim 1  so as to process requests at a time when the number of buffered transactions has reached a threshold at which software pipelined prefetching across the accumulated set of transactions can be applied in sufficient number so that the cumulative gains outweigh the inherent overhead of the method. 
     
     
       5. The method of associating a prefetch descriptor with each data structure that describes the invariants across buffered requests on a computer system according to  claim 1 , where the invariants include the pipeline depth (D), the startup threshold (K), and the optional completion threshold (Z), optionally the size of the prefetch target at each request, and optionally a small buffer for application specific data. 
     
     
       6. The method of initiating execution of the software pipeline loop on a computer system according to  claim 1  once the number of accumulated requests has reached a startup threshold (K). 
     
     
       7. The method of allowing a computer system according to  claim 6  to proceed with processing any buffered transactions before the startup threshold (K) has been reached. 
     
     
       8. The method of exiting the software pipeline on a computer system according to  claim 1  when the number of unprocessed transactions buffered according to  claim 1  reaches a completion threshold (Z). 
     
     
       9. The method of buffering the transaction results on a computer system according to  claim 1  whereby a completed transaction is swapped with a transaction that has not yet completed, thereby eliminating the need for additional buffer space. 
     
     
       10. The method of buffering the transaction results on a computer system according to  claim 1  whereby the completed transactions are maintained in a FIFO. 
     
     
       11. The method of selecting the next node to prefetch in the software pipeline executing on a computer system according to  claim 1  whereby a transactions is selected from the set of buffered transactions if a transaction on the given data structure has been completed, and the next traversal node in the data structure is prefetched otherwise. 
     
     
       12. The method of forcing the completion of the requests buffered in a computer system according to  claim 1 , thereby ensuring that the time required to complete any buffered transaction can be bounded, and allowing the computer system to complete buffered traversal requests when it might otherwise be idle. 
     
     
       13. A computer system with a cache hierarchy comprising:
 a) at least one main memory, 
 b) at least one cache coupled to the at least one main memory, 
 c) a means for prefetching data into any such of the at least one cache from the at least one main memory, 
 d) a buffer for accumulating configured to accumulate traversal requests, 
 e) a buffer for storing configured to store traversal results, 
 f) a means of for storing the traversal requests once prefetch operations have been initiated, 
 g) a buffer for holding configured to hold an active traversal request, and 
 h) a multiplexor configured to select between the accumulated traversals traversal requests and the active traversal request. 
 
     
     
       14. A cache memory The computer system according to  claim 13  wherein a prefetch control word is maintained which describes the a prefetch target in terms of a software pipeline depth, a completion threshold, a startup threshold, a real-time timeout value, a sequence of control bits that specify the handling of timer events, a prefetch target descriptor, said prefetch target descriptor providing a description to the a prefetch unit of the a number and stride a size of words to be prefetched relative to the prefetch target specified as part of the a traversal request when a plurality of cache lines to be prefetched are associated with each prefetch target address, and a mode field that distinguishes between different interpretations of the prefetch target descriptor fields. 
     
     
       15. A cache memory The computer system according to  claim 13  wherein, further comprising a buffer is used configured to store a representation of traversal requests for which an associated prefetch request has been issued. 
     
     
       16. A cache memory The computer system according to  claim 15  wherein said buffer configured to store a representation of traversal requests for which an associated prefetch request has been issued is implemented as a queue. 
     
     
       17. A cache memory The computer system according to  claim 13  wherein the a traversal request is represented by at least one of an address or identifier, a request identifier, an application supplied value such as a key, and the an address of a node in the a data structure to be traversed. 
     
     
       18. A cache memory The computer system according to  claim 13  wherein a, further comprising an active request buffer holds the configured to hold a traversal request for which a data structure traversal is in progress. 
     
     
       19. A cache memory The computer system according to  claim 18  including further comprising:
 a means of for reading the contents of subfields of said active request buffer,; 
 a means of for storing and extracting the subfields of said active request buffer. 
 
     
     
       20. A cache memory The computer system according to  claim 18  wherein further comprising;
 a next device register (N) is provided whereby, wherein writing to said device register causes the an active traversal request address field to be updated with the a value written to said device register, the active traversal request to be added to the a prefetch issued queue, and a prefetch issued for the device register according to the specifications of the a prefetch control register. 
 
     
     
       21. A cache memory The computer system according to  claim 18  further comprising:
 wherein a result register (R) is provided where, wherein upon to said result register being updated: 
 thean active traversal request address field is updated to thea value written to said deviceresult register; 
 if an active results buffer is employed, the active traversal request is added to the results buffer configured to store the traversal results; 
 a traversal request from the accumulation buffer configured to accumulate the traversal requests is added to the a prefetch issued queue, and 
 a prefetch is issued for the a prefetch address specified by the a prefetch issued buffer. 
 
     
     
       22. A cache memory The computer system according to  claim 18  wherein further comprising a current register (C) is associated with the a prefetch issued queue, wherein reading said current register triggers causes the a head of the prefetch issued queue to be dequeued into the active request buffer. 
     
     
       23. A cache memory The computer system according to  claim 13  wherein, further comprising a completion buffer stores configured to store completed data structure traversal requests. 
     
     
       24. A cache memory The computer system according to  claim 23 , which provides a further comprising means of for removing a traversal request from said completion buffer. 
     
     
       25. A cache memory The computer system according to  claim 13 , wherein access to any of said buffers is provided by means of for memory mapped device interfaces. 
     
     
       26. The method of organizing data within the memory on a computer system, the method comprising the steps of:
 a) determining the cache line boundaries of data structure elements;   b) aligning the base of the data structure on a cache line boundary;   c) homogenizing the data structure;   d) inserting a pad field into data structure elements so that subsequent elements are aligned on cache line boundaries;   e) packing elements so as to maximize the data represented in each cache line by removing pointers to adjacent elements, whereby the program instructions that traverse the data structure are constructed to traverse the adjacent packed elements before traversing non-packed elements,   whereby steps b, c, d, and e may be performed in any order and any proper subset of steps c, d, and e can be employed.   
     
     
       27. The method of creating a homogeneous hash table according to  claim 26  whereby the hash function directly indexes an array of nodes in the hash chain, rather than an array of pointers to hash chain nodes, thereby decreasing the number of memory references required to traverse the hash bucket chain, and therefore potential data cache misses, by one. 
     
     
       28. The method of creating a graph represented as adjacency lists according to  claim 26  whereby the nodes in the adjacency list are aligned on cache line boundaries, padded, and packed. 
     
     
       29. In a data processing system, a method for restructuring data requests, comprising:
 receiving the data requests directed to a data structure having a dynamically determined traversal path between data elements, wherein each data request of the data requests is independent of any other data request of the data requests, and wherein the data requests are temporally scattered;   storing the data requests in an accumulation queue;   searching, in response to satisfaction of a search trigger criterion, the data structure for data requested by the data requests stored in the accumulation queue, wherein the search trigger criterion is satisfied at a time other than a time of the storing the data requests and wherein the searching includes issuing prefetch requests for at least a portion of the data requested by the data requests stored in the accumulation queue;   determining if a results queue of the data processing system is empty, wherein the results queue is configured to store at least a result of a data request of the data requests;   forcing a processing of the data request if the results queue is empty;   storing, in the result queue, results of the prefetch requests; and   deferring a further processing of the stored results, by a requesting process of the data processing system, until a threshold number of stored results is stored in the results queue, wherein the requesting process is configured to issue temporally scattered independent data requests.   
     
     
       30. The method of claim 29, wherein the data structure comprises at least one of a binary tree and a hash table, and wherein receiving the data requests comprises at least one of receiving requests to search for data nodes in the binary tree and receiving requests to search for bucket chains of the hash table. 
     
     
       31. The method of claim 29, further comprising:
 storing, in the result queue, found data if, as a result of the searching the data structure, the requested data are found in the data structure, and   storing, in the result queue, an indication that the requested data are other than present if, as a result of the searching the data structure, the requested data are other than present in the data structure.   
     
     
       32. The method of claim 29, further comprising:
 storing, in the result queue, a request of the prefetch requests; and   storing, in the result queue, a result of the request stored in the result queue, wherein the request stored in the result queue and the result of the requests stored in the result queue are uniquely associated in the result queue, a resulting process of the data processing system is configured to search within the result queue for the request stored in the result queue to obtain the result of the stored result, and the resulting process is configured to issue temporally scattered independent data requests.   
     
     
       33. The method of claim 32, further comprising:
 issuing, via the requesting process, a first data request at a first time, wherein the first data request and a result of the first data request are associated in the results queue;   issuing, via the requesting process, a second data request at a second time, wherein the second time is later than the first time; and   matching the second data request to the first data request stored in the results queue, wherein the stored result of the first data request is returned from the results queue in response to the second data request.   
     
     
       34. The method of claim 33, wherein the second data request comprises a time-deferred processing of the first data request. 
     
     
       35. The method of claim 29, further comprising:
 storing, in the result queue, found data if, as a result of the searching the data structure, the requested data are found in the data structure; and   determining if the stored found data requires a modification.   
     
     
       36. The method of claim 35, further comprising:
 deferring the modification of the stored found data in the data structure until the stored found data are not stored in the result queue.   
     
     
       37. The method of claim 29, further comprising:
 storing the prefetch requests in a prefetch queue; and   tracking pending prefetch requests to ensure that at most one prefetch is stored pertaining to any one unique element of the data structure.   
     
     
       38. The method of claim 29, further comprising forcing a processing of any pending data request in the accumulation queue if the results queue is empty. 
     
     
       39. The method of claim 29, wherein the data structure comprises a binary tree and further comprising:
 determining that a node of the binary tree excludes a data value requested by a data request;   determining that the node has a pointer to a child element; and   queuing a request to search a child node, wherein the request is queued in at least one of the accumulation queue or a prefetch queue.   
     
     
       40. The method of claim 29, wherein the data structure comprises a hash table and further comprising at least one of the homogenizing the hash table and aligning a bucket of the hash table on a cache boundary. 
     
     
       41. The method of claim 29, further comprising implementing the accumulation queue in a hardware register. 
     
     
       42. The method of claim 29, further comprising;
 implementing at least one of the accumulation queue, a prefetch queue, and the results queue in a hardware register.   
     
     
       43. The method of claim 29, wherein the searching comprises searching the data structure for the data requested by the data requests stored in the accumulation queue when a threshold time delay has been exceeded. 
     
     
       44. The method of claim 43, wherein the threshold time delay is set based on a system response time requirement. 
     
     
       45. The method of claim 43, wherein the threshold time delay is based on at least one of:
 a maximum permissible delay time before a search is processed; and   an average frequency at which search requests are received.   
     
     
       46. The method of claim 29, wherein the receiving comprises receiving the data requests issued by a transaction processing system. 
     
     
       47. The method of claim 29, wherein the receiving comprises receiving the data requests issued by an operating system. 
     
     
       48. The method of claim 29, whereon the receiving comprises receiving the data requests issued by a database management system for searches of a database. 
     
     
       49. In a data processing system, a method, comprising:
 receiving the data requests directed to a data structure configured to store, in a memory, data elements which are spatially decoherent, wherein a traversal path to a first data element in the data structure is contingent upon at least one value stored in a second data element of the data structure, wherein each data request of the data requests is independent of any other request of the data requests, and wherein the data requests are spatially scattered in the memory;   storing the data requests in an accumulation queue;   searching, responsive to satisfaction of a search trigger criterion, the data structure for data requested by the data requests stored in the accumulation queue, wherein the search trigger criterion is satisfied at a time other than a time of the storing the data request and wherein the searching includes issuing prefetch requests for at least a portion of the data requested by the data requests stored in the accumulation queue;   determining if a results queue of the data processing system is empty, wherein the results queue is configured to store at least a result of a data request of the data requests;   storing, in the result queue, results of the prefetch requests;   forcing a processing of the data request if the results queue is empty; and   deferring a further processing of the stored results, by a requesting process of the data processing system, until a threshold number of stored results is stored in the results queue, wherein the requesting process is configured to issue temporally scattered independent data requests.