Process demand prediction for distributed power and resource management

• US 8,046,468 B2
• Filed: 01/26/2009
• Issued: 10/25/2011
• Est. Priority Date: 01/26/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Isci, Canturk, Wang, Chengwei, Shanmuganathan, Ganesha, Holler, Anne, Bhatt, Chirag
• Primary Examiner(s): Avellino; Joseph
• Assistant Examiner(s): Conaway; James
• Application Number:
  US12/359,473
• Publication Number:
  US 20100191854A1
• Time in Patent Office: 1,002 Days
• Field of Search: 709/226, 718/104, 718/105
• US Class Current: 709/226
• CPC Class Codes: G06F 1/3203 Power management, i.e. event-based initiation of a power-saving mode
• CPC Class Codes: G06F 11/302 where the computing system component is a software system
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: G06F 2201/815 Virtual
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/4893 taking into account power or heat criteria power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Methods and systems for allocating resources in a virtual desktop resource environment are provided. A method includes making a prediction on the future demand for processes running on a distributed environment with several hosts. The prediction is based on the process demand history and includes the removal of historic process demand glitches. Further, the prediction is used to perform a cost and benefit analysis for moving a candidate process from one host to another, and the candidate process is moved to a different host when the cost and benefit analysis recommends such move. In another embodiment, the predictions on future process demand are used for distributed power management by putting hosts in stand-by mode when the overall demand decreases or by adding hosts to the distributed environment when the load increases.

Claims

1. A method for allocating resources in a virtual desktop environment, the method comprising:

making a prediction for future demand by a plurality of processes running on a first host and a second host, the prediction being based on each process demand history and on removing past process demand glitches, including defining the process demand history on which the prediction is based by identifying any past process demand glitch and by including stable periods while excluding any identified past process demand glitch between the stable periods;

selecting a candidate process for movement, the candidate process being one of the plurality of processes;

performing a cost and benefit analysis for moving the candidate process from the plurality of processes from the first host to the second host based on the prediction, the cost and benefit analysis being specific to the candidate process; and

executing a move of the candidate process when the cost and benefit analysis recommends the move;

wherein removing past process demand glitches further includes,

finding a glitch in process demand as an unstable period between first and second stable periods, including identifying the glitch by comparing adjacent samples of process demands to identify unstable samples and then grouping the unstable samples for determining whether a group of the unstable samples is a glitch, and

removing the glitch in process demand when a load of the second stable period is within a demand variation threshold from a load of the first stable period, such that the prediction is based on a combination of the first and second stable periods after removal of the glitch.

2. The method as recited in claim 1, wherein making a prediction further includes,

determining the stable periods in the process demand history, a stable period being a time span during which a demand of the corresponding process stays under a demand variation threshold.

3. The method as recited in claim 2, wherein the demand variation threshold is a predetermined percentage of the sum load capacity of the first host and the second host.

4. The method as recited in claim 2, wherein the demand variation threshold is based on the coefficient of variance of the corresponding process demand history.

5. The method as recited in claim 1, wherein the plurality of processes are a plurality of virtual machines.

6. The method as recited in claim 1 further including,

performing a power cost and benefit analysis for putting the first host in stand-by mode, and

moving processes running in the first host to other hosts and putting the first host in stand-by mode when the cost and benefit analysis recommends putting the first host in stand-by mode.

7. The method as recited in claim 1 further including,

performing a power cost and benefit analysis for starting up a third host, and

starting up the third host and moving processes from at least one of the first host and the second host to the third host when the power cost and benefit analysis recommends starting up the third host.

8. A virtual desktop resource allocation system, the system comprising:

a plurality of hosts in a virtual center;

a process running in a first host from the plurality of hosts; and

a distributed resource manager in the virtual center, wherein the distributed resource manager,

predicts a future demand for the process based on an extended history of process demand and on removing past process demand glitches from determinations of the process demand in order to define the extended history, including defining the process demand history on which the prediction is based by including stable periods while excluding any identified past process demand glitch between the stable periods;

performs a cost and benefit analysis for moving the process to a second host from the plurality of hosts based on the prediction, and

moves the process to the second host when the cost and benefit analysis recommends the move

wherein removing past process demand glitches further includes,

finding a glitch in process demand as an unstable period between first and second stable periods, including identifying the glitch by comparing adjacent samples of process demands to identify unstable samples and then grouping the unstable samples for determining whether a group of the unstable samples is a glitch, and

removing the glitch in process demand when a load of the second stable period is within a demand variation threshold from a load of the first stable period, such that the prediction is based on a combination of the first and second stable periods after removal of the glitch.

9. The system as recited in claim 8, wherein the prediction includes a time span for a future stable load period and a future change in the demand at the end of the future stable load period.

10. The system as recited in claim 9, wherein the future stable load period is calculated as an exponential weighted average of durations of previous stable load periods within a predetermined amount of time.

11. The system as recited in claim 9, wherein the future change in the demand is a maximum change in demand throughout the predetermined amount of time.

12. The system as recited in claim 11, wherein the predetermined amount of time is 60 minutes.

13. The system as recited in claim 9, wherein moving the process to the second host further includes,

copying the memory used by the process from the first host to the second host,

copying the processor state from the first host to the second host, and

running the process in the second host and stop the process in the first host.

14. A computer program embedded in a non-transitory computer-readable medium, when executed by one or more processors, for distributed power management, the computer program comprising:

program instructions for making a prediction for future demand by a plurality of processes running on a plurality of hosts, the prediction being based on each process demand history and on removing past process demand glitches, the process demand history being over a period of time that includes at least one stable period and that excludes any past process demand glitches that are identified as being between two stable periods which are included for making the prediction;

program instructions for performing a first cost and benefit analysis for changing a number of hosts running;

program instructions for shutting down a host when the first cost and benefit analysis recommends reducing a number of running hosts; and

program instructions for starting up a stand-by host when the first cost and benefit analysis recommends incrementing the number of running hosts

wherein removing past process demand glitches further includes,

finding a glitch in process demand as an unstable period between first and second stable periods, including identifying the glitch by comparing adjacent samples of process demands to identify unstable samples and then grouping the unstable samples for determining whether a group of the unstable samples is a glitch, and

removing the glitch in process demand when a load of the second stable period is within a demand variation threshold from a load of the first stable period, such that the prediction is based on a combination of the first and second stable periods after removal of the glitch.

15. The computer program as recited in claim 14, wherein the demand corresponds to Central Processing Unit (CPU) demand.

16. The computer program as recited in claim 14, wherein the demand corresponds to memory usage demand.

17. The computer program as recited in claim 14, further including,

program instructions for performing a second cost and benefit analysis based on a second demand for a second resource type,

program instructions for performing an overall cost and benefit analysis as a function of the first and second cost and benefit analysis, and

program instructions for recommending shutting down or starting up a host based on the overall cost and benefit analysis.

18. The computer program as recited in claim 14, further including,

program instructions for measuring a first error associated with the prediction, and

program instructions for measuring a second error associated with a post-event prediction based on actual demand, and

program instructions for rating the prediction by comparing the first and the second error.

19. The computer program as recited in claim 14, wherein the program instructions for removing past process demand glitches further includes,

program instructions for finding a glitch in process demand as an unstable period between a first and a second stable periods, and

program instructions for removing the glitch in process demand when a load of the second stable period is within a demand variation threshold from a load of the first stable period.