PREDICTING CPU AVAILABILITY FOR SHORT TO MEDIUM TIME FRAMES ON TIME SHARED SYSTEMS

• US 20090217282A1
• Filed: 02/26/2008
• Published: 08/27/2009
• Est. Priority Date: 02/26/2008
• Status: Abandoned Application

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: RAI, Vikram, Sankaran, Sriram, Srivastava, Alok, Kumar, Sunil, Pruscino, Angelo, Joshi, Sameer, Mukherjee, Joy
• Application Number:
  US12/037,233
• Publication Number:
  US 20090217282A1
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis

Abstract

A computer implemented CPU utilization prediction technique is provided. CPU utilization prediction is implemented described in continuous time as an auto-regressive process of the first order. The technique used the inherent autocorrelation between successive CPU measurements. A specific auto-regression equation for predicting CPU utilization is provided. CPU utilization prediction is used in a computer cluster environment. In an implementation, CPU utilization percentage values are used by a scheduler service to manage workload or the distribution of requests over a vast number of CPUs.

Claims

1. A computer implemented method comprising:

determining an auto-regression process for predicting utilization percentages of a computer processing unit (CPU);

obtaining a set of measurements of utilization percentages of the CPU wherein the each measurement is taken at a time interval of a first series of time intervals;

calculating one or more coefficient values of the auto-regression process by using the set of measurements of utilization percentages;

obtaining a known utilization percentage of the CPU, C_k, at a time k; and

calculating a predicted utilization percentage of the CPU, C_k+dk, at a time that is dk amount of time added to time k, by inputting the known utilization percentage of the CPU, C_k, into the auto-regression process and by using the calculated one or more coefficient values.

2. The computer implemented method of claim 1, wherein CPU availability at time k is determined from the relationship, 1−

C_k+dk.

3. The computer implemented method of claim 1, wherein:

determining the auto-regression process comprises using auto-regressing equation,

C_t+dt=α

+β

*C_t+ε

_t3 N(0, σ

²) wherein ε

is the error term;

the obtained set of measurements of utilization percentages of the CPU contains n ordered measurements;

calculating the coefficient values, α and

β

, of the auto-regression equation comprises using ordinary least squares on the set of n measurements, as follows;

β

=Σ

(C_t−

C_mean)(C_t+dt−

C_t+dt(mean))/Σ

(C_t−

C_mean)²; and

α

=C_t+dt(mean)−

β

*C_mean,

where;

C_mean=1/n*Σ

C_t, and

C_{t+dt mean}=1/n*Σ

C_t+dt,

ε

_t=C_t+dt−

α

−

β

*C_t, and

σ

=(1/(n−

2)Σ

ε

_t²)^1/2.

4. The computer implemented method of claim 1, further comprising:

recalculating α

, β

, ε

_t, and σ

using the obtained set of measurements of utilization percentages of the CPU plus additional CPU measurements that were measured over a second series of time intervals that occurred after the first series of time intervals.

5. The computer implemented method of claim 1, wherein obtaining the set of measurements of utilization percentages of the CPU further comprises using a load average measurement utility.

6. The computer implemented method of claim 1, wherein the CPU is one of a plurality of CPUs in a computer cluster.

7. The computer implemented method of claim 6, further comprising:

receiving a request to use the CPU;

wherein the predicted utilization percentage of the CPU indicates that the CPU is not available to handle the request; and

finding a second CPU of the plurality of CPUs that has a predicted utilization percentage indicating that the second CPU is available to handle the request;

sending the request to the second CPU; and

said second CPU handling the request.

8. The computer implemented method of claim 4, wherein the intervals of the first series of time intervals are uniformly distributed or the intervals of the second series of time intervals are uniformly distributed.

9. The computer implemented method of claim 3, wherein

creating a first dataset from the n ordered measurements by populating the first dataset with the first element of the n ordered measurements through the (n−

1)^th element of the n ordered measurements;

creating a second dataset from the n ordered measurements by populating the second dataset with the second element of the n ordered measurements through the n^th element of the n ordered measurements; and

assigning the elements of the first dataset to be independent variables (C_t) and assigning the elements of the second dataset to be dependent variables (C_t+dt), where t=1,n and dt is a next interval occurring after the last interval in the first series of time intervals.

10. A computer-readable storage medium bearing instructions for performing the steps of:

determining an auto-regression process for predicting utilization percentages of a computer processing unit (CPU);

obtaining a set of measurements of utilization percentages of the CPU wherein the each measurement is taken at a time interval of a first series of time intervals;

calculating one or more coefficient values of the auto-regression process by using the set of measurements of utilization percentages;

obtaining a known utilization percentage of the CPU, C_k, at a time k; and

calculating a predicted utilization percentage of the CPU, C_k+dk, at a time that is dk amount of time added to time k, by inputting the known utilization percentage of the CPU, C_k, into the auto-regression process and by using the calculated one or more coefficient values.

11. The computer-readable storage medium of claim 10, wherein CPU availability at time k is determined from the relationship, 1−

C_k+dk.

12. The computer-readable storage medium of claim 10, wherein:

determining the auto-regression process comprises using auto-regressing equation,

C_t+dt=α

+β

*C_t+ε

_t3 N(0, σ

²) wherein σ

is the error term;

the obtained set of measurements of utilization percentages of the CPU contains n ordered measurements;

calculating the coefficient values, α and

β

, of the auto-regression equation comprises using ordinary least squares on the set of n measurements, as follows;

β

=Σ

(C_t−

C_mean)(C_t+dt−

C_t+dt(mean))/Σ

(C_t−

C_mean)²; and

α

=C_t+dt(mean)−

β

*C_mean,

where;

C_mean=1/n*Σ

C_t, and

C_{t+dt mean}=1/n*Σ

C_t+dt, and where;

ε

_t=C_t+dt−

α

−

β

*C_t, and

σ

=(1/(n−

2)Σ

ε

_t²)^1/2.

13. The computer-readable storage medium of claim 10, further comprising the step of:

recalculating α

, β

, ε

_t, and σ

using the obtained set of measurements of utilization percentages of the CPU plus additional CPU measurements that were measured over a second series of time intervals that occurred after the first series of time intervals.

14. The computer-readable storage medium of claim 10, wherein obtaining the set of measurements of utilization percentages of the CPU further comprises using a load average measurement utility.

15. The computer-readable storage medium of claim 10, wherein the CPU is one of a plurality of CPUs in a computer cluster.

16. The computer-readable storage medium of claim 15, further comprising the steps of:

receiving a request to use the CPU;

wherein the predicted utilization percentage of the CPU indicates that the CPU is not available to handle the request; and

finding a second CPU of the plurality of CPUs that has a predicted utilization percentage indicating that the second CPU is available to handle the request;

sending the request to the second CPU; and

said second CPU handling the request.

17. The computer-readable storage medium of claim 13, wherein the intervals of the first series of time intervals are uniformly distributed or the intervals of the second series of time intervals are uniformly distributed.

18. The computer-readable storage medium of claim 12, wherein

creating a first dataset from the n ordered measurements by populating the first dataset with the first element of the n ordered measurements through the (n−

1)^th element of the n ordered measurements;

creating a second dataset from the n ordered measurements by populating the second dataset with the second element of the n ordered measurements through the n^th element of the n ordered measurements; and

assigning the elements of the first dataset to be independent variables (C_t) and assigning the elements of the second dataset to be dependent variables (C_t+dt), where t=1,n and dt is a next interval occurring after the last interval in the first series of time intervals.