Mechanism for on-line prediction of future performance measurements in a computer system

• US 20050086029A1
• Filed: 10/17/2003
• Published: 04/21/2005
• Est. Priority Date: 10/17/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Duesterwald, Evelyn, Dwarkadas, Sandhya, Cascaval, Gheorghe C.
• Granted Patent: US 7,072,805 B2
• Time in Patent Office: Days
• US Class Current: 702/196
• CPC Class Codes: G06F 1/206 comprising thermal management
• CPC Class Codes: G06F 1/3203 Power management, i.e. event-based initiation of a power-saving mode
• CPC Class Codes: G06F 1/329 by task scheduling
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Disclosed are a method and system for predicting future values of a target metric associated with a task executed on a computer system. The method comprises the steps of, over a given period of time, measuring at least one defined metric, transforming that measurement into a value for a predictor source metric, and using the value for the predictor source metric to obtain a predicted future value for said target metric. The preferred embodiment of this invention provides a flexible performance multi-predictor to solve the problem of providing accurate future behavior predictions for adaptive reconfiguration systems. The multi-predictor makes predictions about future workload characteristic by periodically reading available hardware counters. Also disclosed is a method and system for periodically reconfiguring an adaptive computer system by rescheduling tasks based on future behavior predictions.

Claims

1. A method of predicting future values of a target metric associated with a task executed on a computer system, comprising the steps:

over a given period of time, measuring at least one defined metric;

transforming said measurement into a value for a predictor source metric; and

using the value for the predictor source metric to obtain a predicted future value for said target metric.

2. A method according to claim 1, wherein the using step includes the steps of:

providing a table of values for the target metric;

using the value for the predictor source metric as an index to said table to obtain one of the values from said table; and

using the obtained value as the predicted future value for the target metric.

3. A method according to claim 1, wherein:

the measuring step includes the step of obtaining a count of said at least one metric; and

the transforming step includes the step of using said count to help obtain the predictor source metric.

4. A method according to claim 1, wherein:

the measuring step includes the step of measuring at least two defined metrics; and

the transforming step includes the step of transforming the measurements of said metrics into the value for the predictor source metric.

5. A method according to claim 1, wherein the computer system includes a hardware counter, and the measuring step includes the step of using the hardware counter of the computer system to obtain a count of the at least one metric.

6. A method according to claim 1, wherein the using step includes the step of providing a set of possible future values.

7. A method according to claim 6, wherein the step of providing a set of possible future values includes the steps of:

identifying values that the target metric had at different times;

for each of said identified values of the target metric, determining the value that the source metric had before the time at which the target metric had the identified value; and

using said identified values of the target metric as the possible future values.

8. A system for predicting future values of a target metric associated with a task executed on a computer system, comprising:

a measuring instrument to measure at least one defined metric over a given period of time;

a metric model for transforming said measurement into a value for a predictor source metric; and

a predictor for using the value for the predictor source metric to obtain a predicted future value for said target metric.

9. A system according to claim 8, wherein the predictor includes:

a table of values for the target metric; and

means for using the value for the predictor source metric as an index to said table to obtain one of the values from said table, wherein said obtained value is used as the predicted future value for the target metric.

10. A system according to claim 8, wherein:

the measuring instrument includes a counter for obtaining a count of said at least one metric; and

the metric model uses said count to help obtain the predictor source metric.

11. A system according to claim 8, wherein:

the measuring instrument includes one or more counters for obtaining counts of the defined metrics; and

the metric model transforms the counts from the one or more counters into the value for a single predictor source metric.

12. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for predicting future values of a target metric associated with a task executed on a computer system, said method steps comprising:

over a given period of time, measuring at least one defined metric;

transforming said measurement into a value for a predictor source metric; and

using the value for the predictor source metric to obtain a predicted future value for said target metric.

13. A program storage device according to claim 12, wherein the using step includes the steps of

providing a table of values for the target metric;

using the value for the predictor source metric as an index to said table to obtain one of the values from said table; and

using the obtained value as the predicted future value for the target metric.

14. A program storage device according to claim 12, wherein:

the measuring step includes the step of obtaining a count of said at least one metric; and

the transforming step includes the step of using said count to help obtain the predictor source metric.

15. A method of periodically reconfiguring an adaptive computer system based on future behavior predictions, comprising the steps:

for each of a group of tasks, assigning a dynamic priority to the task based on a history table based prediction of a future value for a characteristic associated with the task; and

at defined times, selecting from said group the task having the highest dynamic priority to be executed by the computer system.

16. A method according to claim 15, further comprising the step of recalculating at determined times the dynamic priority assigned to each of at least some of the tasks.

17. A method according to claim 16, further comprising the step of the computer system executing the selected task, and wherein the recalculating step includes the step of, for each task executed by the computer system, recalculating the dynamic priority assigned to the task after the computer system has executed the task.

18. Apparatus for periodically reconfiguring an adaptive computer system based on future behavior predictions, comprising:

a predictor for assigning a dynamic priority to each of a group of tasks based on a history table based prediction of a future value for a characteristic associated with the task; and

a scheduler for selecting, at defined times, from said group the task having the highest dynamic priority to be executed by the computer system.

19. Apparatus according to claim 18, wherein the predictor recalculates at given times the dynamic priority assigned to each of at least some of the tasks.

20. Apparatus according to claim 18, wherein each time the computer system executes one of the tasks, the predictor recalculates the dynamic priority assigned to said one of the tasks.

21. Apparatus according to claim 20, wherein:

each time the computer system executes one of the tasks, the scheduler sends a signal to the predictor; and

in response to receiving said signal, the predictor recalculates the dynamic priority assigned to said one of the tasks.

22. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for periodically reconfiguring an adaptive computer system based on future behavior predictions, said method steps comprising:

for each of a group of tasks, assigning a dynamic priority to the task based on a history table based prediction of a future value for a characteristic associated with the task; and

at defined times, selecting from said group the task having the highest dynamic priority to be executed by the computer system.

23. A program storage device according to claim 22, wherein said method steps further comprise the step of recalculating at determined times the dynamic priority assigned to each of at least some of the tasks.

24. A program storage device according to claim 23, wherein said method steps further comprise the step of the computer system executing the selected task;

and the recalculating step includes the step of, for each task executed by the computer system, recalculating the dynamic priority assigned to the task after the computer system has executed the task.