System and method for energy efficient data prefetching

• US 20030126232A1
• Filed: 12/27/2001
• Published: 07/03/2003
• Est. Priority Date: 12/27/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ranganathan, Parthasarathy, Mogul, Jeffrey Clifford, Pinheiro, Eduardo S., Farkas, Keith Istvan
• Granted Patent: US 7,437,438 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A computer system uses a prefetch prediction model having energy usage parameters to predict the impact of prefetching specified files on the system'"'"'s energy usage. A prefetch prediction engine utilizes the prefetch prediction model to evaluate the specified files with respect to prefetch criteria, including energy efficiency prefetch criteria, and generates a prefetch decision with respect to each file of the specified files. For each specified file for which the prefetch prediction engine generates an affirmative prefetch decision, an identifying entry is stored in a queue. The computer system fetches files identified by entries in the queue, although some or all of the entries in the queue at any one time may be deleted if it is determined that the identified files are no longer likely to be needed by the computer system.

Claims

1. A computer program product for use in conjunction with a client computer system having at least one application having instructions for specifying files to be fetched from a server, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a prefetch prediction model including energy usage parameters for predicting an impact on energy usage by the client computer system that would result from prefetching specified files;

a prefetch prediction engine coupled to the prefetch prediction model for evaluating the specified files with respect to prefetch criteria, including energy efficiency prefetch criteria, and generating a prefetch decision with respect to each file of the specified files;

instructions for storing in a queue entries identifying each specified file for which the prefetch prediction engine generates an affirmative prefetch decision; and

instructions for fetching files identified by entries in the queue.

2. The computer program product of claim 1, including a model updater, coupled to the prefetch prediction model, for updating the energy usage parameters of the prefetch prediction model in accordance with results of past prefetch decisions.

3. The computer program product of claim 1, including instructions for detecting a current energy supply level of the client computer system, wherein the prefetch criteria include criteria that are a function of the current energy supply level of the client computer system.

4. The computer program product of claim 1, including instructions for detecting fullness of a cache in the client computer system, wherein the prefetch criteria include criteria that are a function of the cache fullness.

5. The computer program product of claim 1, wherein at least one of the specified files is identified in a message received from the server.

6. The computer program product of claim 1, wherein at least one of the specified files is identified by the at least one application in the client computer system.

7. The computer program product of claim 1, wherein the queue comprises a prefetch queue;

the computer program mechanism further comprising;

instructions for storing in a fetch queue entries identifying the files specified by the at least one application program to be fetched; and

a scheduler for scheduling downloading of files identified by entries in the fetch queue and files identified by entries in the prefetch queue, the scheduler giving priority to the files identified by the entries in the fetch queue.

8. The computer program product of claim 7, wherein the scheduler includes instructions for determining whether to download a file identified by an entry in the prefetch queue in accordance with predefined scheduling criteria, the predefined scheduling criteria including at least one criteria selected from the set consisting of client cache status, user behavior and preferences, network congestion, bandwidth availability between the client computer system and the server, round-trip time from client to server, and a current energy supply level of the client computer system.

9. The computer program product of claim 1, including

queue pruning instructions for re-evaluating entries in the queue and flushing from the queue any entries in the queue deselected by the re-evaluating.

10. The computer program product of claim 1, including a model updater, coupled to the prefetch prediction model, for updating the energy usage parameters of the prefetch prediction model in accordance with energy usage statistics.

11. A method for performing energy efficient data prefetching in conjunction with a client computer system, comprising:

predicting, in accordance with a prefetch prediction model having energy usage parameters, an impact on energy usage by the client computer system that would result from prefetching specified files;

evaluating the specified files with respect to prefetch criteria, including energy efficiency prefetch criteria;

generating a prefetch decision with respect to each file of the specified files;

storing in a queue entries identifying each specified file for which an affirmative prefetch decision was generated; and

fetching files identified by entries in the queue.

12. The method of claim 11, updating the energy usage parameters of the prefetch prediction model in accordance with results of past prefetch decisions.

13. The method of claim 11, wherein the prefetch criteria include criteria that are a function of a current energy supply level of the client computer system.

14. The method of claim 11, wherein the prefetch criteria include criteria that are a function of cache fullness of the client computer system.

15. The method of claim 11, including receiving a message from a server that includes information identifying at least one of the specified files.

16. The method of claim 11, including executing at least one application that specifies files to be fetched from a server, the executing of the at least one application including identifying at least one of the specified files.

17. The method of claim 16, wherein the queue comprises a prefetch queue;

the method further comprising;

storing in a fetch queue entries identifying the files specified by the at least one application program to be fetched; and

scheduling downloading of files identified by entries in the fetch queue and files identified by entries in the prefetch queue, giving priority to the files identified by the entries in the fetch queue.

18. The method of claim 17, further comprising:

determining whether to download a file identified by an entry in the prefetch queue in accordance with predefined scheduling criteria, the predefined scheduling criteria including at least one criteria selected from the set consisting of client cache status, user behavior and preferences, network congestion, bandwidth availability between the client computer system and the server, round-trip time from client to server, and a current energy supply level of the client computer system.

19. The method of claim 11, further comprising:

re-evaluating entries in the queue and flushing from the queue any entries in the queue deselected by the re-evaluating.

20. The method of claim 11, updating the energy usage parameters of the prefetch prediction model in accordance with energy usage statistics.

21. A computer system comprising:

at least one processing unit for executing procedures containing executable instructions;

a prefetch prediction model including energy usage parameters for predicting an impact on energy usage by the computer system that would result from prefetching specified files;

a prefetch prediction engine, executable by the at least one processing unit and coupled to the prefetch prediction model, for evaluating the specified files with respect to prefetch criteria, including energy efficiency prefetch criteria, and generating a prefetch decision with respect to each file of the specified files;

memory, including a queue for storing entries identifying each specified file for which the prefetch prediction engine generates an affirmative prefetch decision; and

a download module, executable by the at least one processing unit, having instructions for fetching files identified by entries in the queue.

22. The computer system of claim 21, including a model updater, executable by the at least one processing unit, coupled to the prefetch prediction model, for updating the energy usage parameters of the prefetch prediction model in accordance with results of past prefetch decisions.

23. The computer system of claim 21, including an energy supply detection module, executable by the at least one processing unit, having instructions for detecting a current energy supply level of the computer system, wherein the prefetch criteria include criteria that are a function of the current energy supply level of the computer system.

24. The computer system of claim 21, wherein the memory further includes a cache, the computer system further comprising a cache fullness detection module, executable by the at least one processing unit, having instructions for detecting fullness of the cache, wherein the prefetch criteria include criteria that are a function of the cache fullness.

25. The computer system of claim 21, wherein at least one of the specified files is identified in a message received from a server.

26. The computer system of claim 21, further comprising at least one application, executable by the at least one processing unit, wherein at least one of the specified files is identified by the at least one application.

27. The computer system of claim 21, wherein the queue comprises a prefetch queue;

the computer system further comprising;

at least one application, executable by the at least one processing unit, having instructions for specifying files to be fetched from a server;

a fetch queue queuing module, executable by the at least one processing unit, having instructions for storing in a fetch queue entries identifying the files specified by the at least one application; and

a scheduler for scheduling downloading of files identified by entries in the fetch queue and files identified by entries in the prefetch queue, the scheduler giving priority to the files identified by the entries in the fetch queue.

28. The computer system of claim 27, wherein the scheduler includes instructions for determining whether to download a file identified by an entry in the prefetch queue in accordance with predefined scheduling criteria, the predefined scheduling criteria including at least one criteria selected from the set consisting of cache status, user behavior and preferences, network congestion, bandwidth availability between the computer system and the server, round-trip time between the computer system and the server, and a current energy supply level of the computer system.

29. The computer system of claim 21, including

a queue pruner, executable by the at least one processing unit, including queue pruning instructions for queue pruning instructions for re-evaluating entries in the queue and flushing from the queue any entries in the queue deselected by the re-evaluating.

30. The computer system of claim 21, including

a queue pruner, executable by the at least one processing unit, including queue pruning instructions for prioritizing the entries in the queue and for removing from the queue a first entry identifying a previously specified file for which the prefetch prediction engine generated an affirmative prefetch decision, where said first entry is assigned a lower priority than a second entry in the queue.

31. The computer system of claim 21, including a model updater, executable by the at least one processing unit, coupled to the prefetch prediction model, having instructions for updating the energy usage parameters of the prefetch prediction model in accordance with energy usage statistics.

32. A computer system comprising:

at least one processing unit for executing procedures containing executable instructions;

a server module, executable by the at least one processing unit, for responding to a request from a client computer for a specified file and for generating a reply to the request, the reply including a content portion comprising the specified file; and

a prefetch predictor, executable by the at least one processing unit, for identifying additional files for possible prefetching by the client computer;

the server module including instructions for including in a supplemental portion of the reply to the request from the client computer prefetch hint information identifying at least one of the additional files, wherein the supplemental portion is distinct from the content portion of the reply.

33. The computer system of claim 32, wherein the prefetch hint information includes predicted prefetch probability information for at least one of the identified additional files.

34. The computer system of claim 32, wherein the prefetch hint information includes meta information for at least one of the identified additional files, the meta information selected from the group consisting of file size information, file type information and information indicating a specific relationship to the specified file in the content portion of the reply.

35. The computer system of claim 32, wherein the prefetch hint information includes an initial additional set of files, the computer system further comprising a pruner, executable by the at least one processing unit, including instructions for selectively removing at least one file of the initial additional set of files.

36. The computer system of claim 35, further comprising a prefetch efficiency model, including prefetch efficiency parameters for predicting an impact on energy usage by the client computer that would result from prefetching specified files, coupled to the pruner, the pruner utilizing the prefetch efficiency model to selectively remove the at least one file of the initial additional set of files.

37. A computer program product for use in conjunction with a client computer system having at least one application having instructions for specifying files to be fetched from a server, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a prefetch prediction model including cost parameters for predicting an impact on monetary charges incurred by the client computer system that would result from prefetching specified files;

a prefetch prediction engine coupled to the prefetch prediction model for evaluating the specified files with respect to prefetch criteria, including cost efficiency prefetch criteria, and generating a prefetch decision with respect to each file of the specified files;

instructions for storing in a queue entries identifying each specified file for which the prefetch prediction engine generates an affirmative prefetch decision; and

instructions for fetching files identified by entries in the queue.

38. A method for performing energy efficient data prefetching in conjunction with a client computer system, comprising:

predicting, in accordance with a prefetch prediction model having cost parameters, an impact on monetary charges incurred by the client computer system that would result from prefetching specified files;

evaluating the specified files with respect to prefetch criteria, including cost efficiency prefetch criteria;

generating a prefetch decision with respect to each file of the specified files;

storing in a queue entries identifying each specified file for which an affirmative prefetch decision was generated; and

fetching files identified by entries in the queue.

39. A computer system comprising:

at least one processing unit for executing procedures containing executable instructions;

a prefetch prediction model including cost parameters for predicting an impact on monetary charges incurred by the computer system that would result from prefetching specified files;

a prefetch prediction engine, executable by the at least one processing unit and coupled to the prefetch prediction model, for evaluating the specified files with respect to prefetch criteria, including cost efficiency prefetch criteria, and generating a prefetch decision with respect to each file of the specified files;

memory, including a queue for storing entries identifying each specified file for which the prefetch prediction engine generates an affirmative prefetch decision; and

a download module, executable by the at least one processing unit, having instructions for fetching files identified by entries in the queue.