Predictive cache system

• US 5,305,389 A
• Filed: 08/30/1991
• Issued: 04/19/1994
• Est. Priority Date: 08/30/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Palmer, Mark L.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/753,096
• Time in Patent Office: 963 Days
• Field of Search: 382/1, 382/14, 382/15, 382/41, 395/600, 395/250, 395/425, 395/725, 365/230.01, 365/230.08
• US Class Current: 382/305
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. A data processing system including a predictive cache memory subsystem comprising:

a cache memory for storing objects retrieved from secondary memory;

pattern memory storing object access patterns generated from prior accesses of the data processing system processing in a like context;

a prefetcher responsive to a current access pattern during operation of the data processing system for predicting, from like object access patterns stored in pattern memory, accesses to objects and for prefetching predicted objects to store the predicted objects in cache memory.

2. A data processing system as claimed in claim 1 further comprising a trainer for generating access patterns stored in pattern memory from traces of accesses recorded during processing of the data processing system.

3. A data processing system as claimed in claim 2 wherein the trainer generates statistical information for the stored access patterns which indicates ability of individual patterns to contribute to system speedup.

4. A data processing system as claimed in claim 3 wherein the patterns stored in pattern memory are stored as unit patterns and the trainer deletes or reduces lengths of unit patterns in pattern memory based on accuracy of predictions generated by the unit patterns.

5. A data processing system as claimed in claim 3 wherein the statistics include accuracy of prediction.

6. A data processing system as claimed in claim 2 wherein the trainer adapts to accesses of the data processing system to delete patterns from pattern memory which do not contribute sufficiently to system speedup.

7. A data processing system as claimed in claim 2 wherein the trainer initiates patterns in pattern memory from a single occurrence of a pattern in an access trace.

8. A data processing system as claimed in claim 7 wherein the trainer initiates patterns from overlapping input patterns in an access trace.

9. A data processing system as claimed in claim 1 wherein the patterns are stored in pattern memory as unit patterns ordered by predicted time of access and the prefetcher compares a current access pattern to a sample length of unit patterns to form a prediction from a remaining length of the unit patterns.

10. A data processing system as claimed in claim 9 wherein the prefetcher dynamically controls sample length to balance the efficiency of prediction against accuracy.

11. A data processing system as claimed in claim 1 wherein the prefetcher compares a current access pattern to a sample length of patterns stored in pattern memory and the prefetcher dynamically controls sample length to balance efficiency of prediction against accuracy.

12. A data processing system as claimed in claim 1 wherein the prefetcher controls lengths of predicted object accesses to balance efficiency of prediction against accuracy.

13. A data processing system as claimed in claim 1 wherein the prefetcher controls radius of match of patterns to balance efficiency of prediction against accuracy.

14. A data processing system as claimed in claim 1 wherein the pattern memory stores separate sets of patterns for different contexts of processing.

15. A data processing system as claimed in claim 14 wherein access patterns stored in pattern memory are identified by context including user, application and database.

16. A data processing system as claimed in claim 14 wherein context is specified by a user or application.

17. A data processing system as claimed in claim 1 wherein the prefetcher predicts objects from a combination of access patterns stored in pattern memory.

18. A data processing system as claimed in claim 1 wherein the cache memory subsystem evicts objects from cache memory by order of priority and the prefetcher gives objects which are prefetched priority within the prefetch according to predicted time of access.

19. A data processing system as claimed in claim 18 wherein prefetched objects are initially given high priority to remain in cache memory.

20. A data processing system as claimed in claim 13 wherein the prefetcher predicts and orders predicted objects, with alternatives at predicted times of access.

21. A data processing system as claimed in claim 20 wherein the prefetcher orders alternatives by degree of match of a current access pattern to a stored access pattern.

22. A data processing system as claimed in claim 21 wherein the prefetcher orders alternatives by accuracy of past predictions for the stored access patterns.

23. A data processing system as claimed in claim 20 wherein the prefetcher orders alternatives by accuracy of past predictions for the stored access patterns.

24. A data processing system as claimed in claim 20 wherein, when a prefetched an object is used, the used object is given high priority and alternatives to the used object are given low priority.

25. A data processing system as claimed in claim 18 further comprising a primary cache which receives objects from the predictive cache memory subsystem and which evicts objects to the predictive cache memory subsystem.

26. A data processing system as claimed in claim 18 wherein replacement order is determined by a list of objects residing in cache memory.

27. A data processing system as claimed in claim 1 wherein the prefetcher predicts objects based on the time of access order of objects within a current access pattern relative to a stored access pattern.

28. A data processing system including a predictive cache memory subsystem comprising:

a cache memory for storing objects retrieved from secondary memory;

pattern memory storing separate sets of object access patterns generated from prior accesses of the data processing system processing in different contexts;

a prefetcher responsive to a current access pattern during operation of the data processing system for predicting, from like object access patterns stored in pattern memory, accesses to objects and for prefetching predicted objects to store the predicted objects in cache memory, the prefetcher comparing the time of access order of a current access pattern to a sample length of patterns to form a prediction from a remaining length of selected patterns, the remaining length of the selected patterns being dynamically controlled to increase the efficiency of prediction, predictions being made from combinations of access patterns stored in pattern memory; and

a trainer for generating access patterns stored in pattern memory from traces of accesses recorded during processing of the data processing system, the trainer generating statistical information for the stored accessed patterns including accuracy of prediction and deleting patterns of insufficient accuracy from pattern memory.

29. A data processing system as claimed in claim 28 wherein the cache memory subsystem evicts objects from cache memory by order of priority and objects which are prefetched are given priority within the prefetch by the prefetcher and are initially given high priority to remain in cache memory, predicted objects being ordered by the prefetcher by order of expected time of access, with alternatives at expected times of access, alternatives being ordered by degree of match of the current access pattern to a stored access pattern and by accuracy of past predictions for the stored accessed patterns.

30. A method of cache memory management comprising:

generating access patterns from traces of object accesses recorded during processing of a data processing system in a context;

storing the access patterns;

monitoring a current access pattern during operation of the data processing system and predicting, from stored object access patterns from a like context, accesses to objects; and

prefetching predicted objects and storing the predicted objects in cache memory.

31. A method as recited in claim 30 further comprising generating statistical information for the stored access patterns which indicates ability of pattern to contribute to system speedup.

32. A method as recited in claim 30 wherein the access patterns are stored as unit patterns and predicted objects are predicted by comparing a current access pattern to a sample length of unit patterns ordered by time of access to form a prediction from a remaining length of selected unit patterns.

33. A method as recited in claim 30 further comprising dynamically controlling sample length to balance efficiency of prediction against accuracy.

34. A method as claimed in claim 30 further comprising dynamically controlling lengths of predicted object accesses to balance efficiency against accuracy.

35. A method as recited in claim 30 further comprising storing separate sets of patterns for different contexts of processing.

36. A method as recited in claim 30 further comprising predicting objects from a combination of access patterns stored in pattern memory.

37. A method as recited in claim 30 further comprising evicting objects from cache memory by order of priority, giving order of priority within a prefetch according to predicted time of access, and initially giving prefetched objects high priority to remain in cache memory.

38. A method as recited in claim 37 further comprising predicting and ordering objects with alternatives at predicted times of access.

39. A method as recited in claim 38 wherein alternatives are predicted by degree of match of a current access pattern to a stored access pattern.

40. A method as recited in claim 38 wherein alternatives are ordered by accuracy of past predictions for the stored accessed patterns.

41. A method as recited in claim 30 comprising predicting objects based on the time of access order of objects within a current access pattern relative to a stored access pattern.