Abstract

Prefetches to a cache memory subsystem are made from predictions which are based on access patterns stored by context. An access pattern is generated from prior accesses of a data processing system processing in a like context. During a training sequence, an actual trace of memory accesses is processed to generate unit patterns which serve in making future predictions and to identify statistics such as pattern accuracy for each unit pattern. In a replacement list, prefetched objects are included at the head of the list. Within a prefetch, objects are listed by order of expected time of access, with alternatives at predicted times of access. When an object is used, it is moved to the head of the list and any prefetched alternatives to that object, indicated by like time marks, are moved to the tail of the list. Alternatives may be listed according to degree of match of a current access pattern and a stored access pattern and by prior accuracy of the unit pattern. A server includes a demand access queue which preempts fetches of objects identified by a prefetch queue.

Other References

• "Prefetching Using a Pageable Branch History Table", IBM Technical Disclosure Bulletin, vol. 28, No. 8, Jan. 1986
• "Using a Small Cache to Hedge for a BHT", IBM Technical Disclosure Bulletin, Vo. 28, No. 4, Sep. 1985
• "Using a Branch History Table to Prefetch Cache Lines", IBM Technical Disclosure Bulletin, vol. 22, No. 12, May 1980
• M. E. Ulug et al., "A Database I/O Server with a Learning Expert System", General Electric Company, Corporate Research and Development, Information Sciences 48, 53-74 (1989)
• H. Wedekind et al., "Prefetching In Realtime Database Applications", presented at ACM SIGMOD, Washington, May 1986
• Hong-Tai Chou et al., "An Evaluation of Buffer Management Strategies for Relational Database Systems," Proceedings of VLDB 85, Stockholm, pp. 127-141, Computer Sciences Department University of Wisconsin
• Rajiv Jauhari et al., "Priority-Hints: An Algorithm for Priority-Based Buffer Management," Madison, Wis., 53706, Proceedings of the 16th VLDB Conference, Brisbane, Australia, 1990, pp. 708-721
• Rafael Alonso, "Data Caching Issues in an Information Retrieval System," ACM Transactions on Database Systems, vol. 15, No. 3, Sep. 1990, pp. 359-384
• Klaus Kratzer et al., "Prefetching A Performance Analysis," Information Systems, vol. 15, No. 4, pp. 445-452, Copyright 1990 Pergamon Press plc
• Alan J. Smith, "Sequentiality and Prefetching in Database Systems," University of California-Berkeley, ACM Transactions on Database Systems, vol. 3, No. 3, Sep. 1978, pp. 223-247
• Juan Rodriguez-Rosell, "Empirical Data Reference Behavior in Data Base Systems," Computer, Nov. 1976, pp. 9-13
• Michael Hammer, et al., "Acquisition and Utilization of Access Patterns in Relational Data Base Implementation," MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Mass. 02139, pp. 292-313
• Bahram Niamir, "Attribute Partitioning in a Self-Adaptive Relational Database System," Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, Mass. 02139
• Palmer, Mark & Zdonik, Stanley B., Technical Report, Fido: A Cache That Learns to Fetch, Published by Brown University, Computer Science Dept., Providence, R.