Controlling state transitions in a system

• US 8,812,674 B2
• Filed: 03/03/2010
• Issued: 08/19/2014
• Est. Priority Date: 03/03/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Guenter, Brian K.
• Primary Examiner(s): Wang, Liangche A
• Assistant Examiner(s): ISOM, JOHN W
• Application Number:
  US12/716,274
• Publication Number:
  US 20110218653A1
• Time in Patent Office: 1,630 Days
• Field of Search: 709/203, 709/226, 713/300, 713320-323, 700 28- 29, 700/37, 700/286, 700/291, 700/297
• US Class Current: 709/226
• CPC Class Codes: G05B 13/02 electric
• CPC Class Codes: G05B 13/048 using a predictor
• CPC Class Codes: G06F 1/3203 Power management, i.e. event-based initiation of a power-saving mode

Abstract

A control system is described for controlling the operation of a target system, such as a data center. The control system uses a prediction module to predict demand for resources of the target system for future time steps. The control system then uses a transition determination module to determine state transitions within the target system to address the predicted demand. Each state transition describes a number of units to be advanced from a first state, at a first time step, to a second state, at a second time step. The control system then commences those state transitions which begin in the current step, and then repeats the predicting and determining for a next time step. The transition determination module can determine the state transitions by operating on an objective function that includes a demand difference component and a cost component, as subject to a set of conservation equations.

Claims

1. A computer-implemented method for controlling operation of a target system, the target system having a plurality of units to be controlled, the method comprising:

for a current time step, predicting demand for resources of the target system, to provide predicted demand for a plurality of future time steps;

for the current time step, determining state transitions within the target system to address the predicted demand, to provide a plurality of state transitions;

for the current time step, commencing state transitions which begin in the current time step, each of the plurality of state transitions taking a respective time interval to perform;

and repeating the predicting, determining, and commencing for a next current time step;

said determining state transitions comprising;

determining a sum of demand differences, each demand difference representing a difference, for a particular time step, between a unit demand and an ability to meet the unit demand, at the particular time step.

2. The computer-implemented method of claim 1, wherein the target system being controlled is a data center, and wherein the units comprise computing units that perform computing functions.

3. The computer-implemented method of claim 1, wherein said predicting comprises:

receiving a set of demand measurements associated with past demand experienced by the target system;

and using the set of demand measurements to provide the predicted demand.

4. The computer-implemented method of claim 1, wherein said predicting comprises using a linear prediction technique to predict demand.

5. The computer-implemented method of claim 1, wherein each state transition describes a number of units to be advanced from a first state, at a first time step, to a second state, at a second time step.

6. The computer-implemented method of claim 1, wherein said determining state transitions further comprises:

formulating an objective function that expresses a control objective to be achieved in the target system;

and operating on the objective function using a solving technique to achieve the control objective and provide the plurality of state transitions.

7. The computer-implemented method of claim 6, wherein the objective function has a demand difference component, wherein the demand difference component expresses the sum of demand differences, and wherein the ability to meet the unit demand represents a number of units operating in a specified state for satisfying the unit demand.

8. The computer-implemented method of claim 7, wherein the objective function also has a cost component, wherein the cost component expresses a cost associated with making the state transitions.

9. The computer-implemented method of claim 8, wherein the cost pertains to energy consumption.

10. The computer-implemented method of claim 8, wherein the cost pertains to reliability.

11. The computer-implemented method of claim 8, wherein said operating comprises operating on the demand difference component and the cost component in series.

12. The computer-implemented method of claim 8, wherein said operating comprises operating on a weighted combination of the demand difference component and the cost component.

13. The computer-implemented method of claim 6, wherein said operating is subject to a set of conservation equations, the conservation equations expressing flow constraints associated with the state transitions over a span of time.

14. The computer-implemented method of claim 6, wherein said solving technique comprises a linear programming technique.

15. The computer-implemented method of claim 6, wherein the units in the target system have common behavior, and wherein the objective function is based on a modeling of this common behavior.

16. The computer-implemented method of claim 6, wherein the units in the target system include at least two types of units with different respective behaviors, and wherein the objective function is based on separate modeling of said at least two different respective behaviors.

17. A control system that includes at least one processing device, the at least one processing device including at least one memory storing instructions executable by the at least one processing device for controlling operation of a target system, the target system having a plurality of units to be controlled, the control system further comprising:

a prediction module configured to predict, at a current time step, demand for resources of the target system, to provide predicted demand for a plurality of future time steps;

and a transition determination module configured to determine, at the current time step, state transitions within the target system to address the predicted demand, to provide a plurality of state transitions, each state transition describing a number of units to be advanced from a first state, at a first time step, to a second state, at a second time step, the prediction module comprising;

logic configured to receive a set of demand measurements associated with past demand experienced by the target system;

and logic configured to use the set of demand measurements to provide the predicted demand, and the transition determination module comprising;

logic configured to formulate an objective function that expresses a control objective to be achieved in the target system, the objective function including a demand difference component that expresses a sum of demand differences, each demand difference representing a difference, for a particular time step, between a unit demand and an ability to meet the unit demand, at the particular time step;

and logic configured to operate on the objective function using a solving technique to achieve the control objective and provide the state transitions.

18. The control system of claim 17, wherein the target system being controlled is a data center, and wherein the units comprise computing units that perform computing functions.

19. A memory for storing computer readable instructions, the computer readable instructions providing a transition determination module when executed by one or more processing devices, the computer readable instructions comprising:

logic configured to, at a current time step, determine state transitions within a target system to address predicted demand, to provide a plurality of state transitions by;

formulating an objective function that expresses a control objective to be achieved in the target system, the objective function including a demand difference component that expresses a sum of demand differences, each demand difference representing a difference, for a particular time step, between a unit demand and an ability to meet the unit demand, at the particular time step,

the objective function further including a cost component, wherein the cost component expresses a cost associated with making the state transitions, wherein said logic configured to determine state transitions is subject to a set of conservation equations, the conservation equations expressing flow constraints associated with the state transitions over a span of time; and

operating on the objective function using a solving technique to achieve the control objective and provide the state transitions.

20. The memory of claim 19, wherein the ability to meet the unit demand represents a number of units operating in a specified state for satisfying the unit demand.