REDUCING LATENCIES IN COMPUTING SYSTEMS USING PROBABILISTIC AND/OR DECISION-THEORETIC REASONING UNDER SCARCE MEMORY RESOURCES

• US 20080005736A1
• Filed: 06/30/2006
• Published: 01/03/2008
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Iyigun, Mehmet, Horvitz, Eric J., Apacible, Johnson T.
• Granted Patent: US 8,112,755 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2209/482 Application
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Architecture that employs probabilistic and/or decision-theoretic model(s) of application usage to predict application use and in view of bounded or limited-availability memory. The model(s) is applied with cost-benefit analysis to guide memory management in an operating system, in particular, for both decisions about prefetching and memory retention versus deletion or “paging out” of memory of lower priority items, to free up space for higher value items. Contextual information is employed in addition to computer action monitoring for predicting next applications to be launched. Prefetching is optimized so as to minimize user perceived latencies.

Claims

1. A computer-implemented system that facilitates management of system resources, comprising:

a bounded memory resource of a system for utilization by a system process;

a probabilistic learning and reasoning method for providing models that predict a next system process launch and/or shift of focus; and

a management component that manages the bounded memory resource to reduce latency associated with the system process based on the learning and reasoning process.

2. The system of claim 1, wherein the management component manages processing of a second model in combination with a decision-theoretic model to reduce the latency associated with the system process.

3. The system of claim 1, further comprising an application launch component for monitoring data of the system process to predict launch and/or usage of a next application.

4. The system of claim 3, wherein the data monitored by the application launch component is associated with foreground launch activity of the system process.

5. The system of claim 3, wherein the application launch component distinguishes between a foreground launch and a background launch of the system process, which is an application.

6. The system of claim 1, further comprising an application launch component that monitors launch data associated with an application, stores a record of the launch data, generates a transition model based on the launch record, and updates the model based on new launch data.

7. The system of claim 1, further comprising an application launch component that utilizes a Markov model for computing probability data associated with inferring when a next system process will be launched.

8. The system of claim 1, further comprising a prefetch component that prefetches data into the bounded memory resource based on a decision data of a probabilistic and/or decision-theoretic model.

9. The system of claim 1, further comprising a retention component that maintains data in the bounded memory resource based on decision data of a probabilistic and/or decision-theoretic model.

10. A computer-implemented method of managing system resources, comprising:

receiving a limited-availability memory resource of a device for utilization by device processes;

processing a probabilistic and/or decision-theoretic model for predicting execution of the device processes; and

managing processing of the probabilistic and/or decision-theoretic model based on the limited-availability memory resource to reduce latency associated with the device processes.

11. The method of claim 10, further comprising dynamically changing a size of the limited-availability memory resource based on insufficient data for modeling.

12. The method of claim 10, further comprising:

separating the device processes related to applications into a group of applications the user cares about and a group of applications the user does not care about using a classification mechanism; and

predicting when a next application will launch as part of the device processes based on the groups.

13. The method of claim 12, further comprising inferring probability data associated with determining when the next application will launch, using a Markov model.

14. The method of claim 10, further comprising computing an optimization based on a representation of user perceptions of a cost of the latency.

15. The method of claim 14, wherein the optimization is based on a value-density approximation to a knapsack representation associated with minimizing actual and/or perceived latencies.

16. The method of claim 10, further comprising optimizing a prefetch process to minimize user perception of latency associated with one of the device processes.

17. The method of claim 10, further comprising predicting when an application will launch based on contextual information and at least one of the device processes.

18. The method of claim 10, further comprising performing a prefetch operation based on a cost-benefit analysis.

19. The method of claim 10, further comprising employing another probabilistic model in combination with the probabilistic and/or decision-theoretic model to make a decision related to prefetching data in the limited-availability memory resource.

20. A computer-implemented method of managing resources in a portable wireless device, comprising:

determining available device memory for processing programs and data;

developing and processing probabilistic and decision-theoretic models in the portable wireless device for predicting application and data actions; and

managing processing of the programs and data based on the available memory to reduce latency associated with the device programs and data.