Systems and methods for providing constrained optimization using adaptive regulatory control

• US 20050268063A1
• Filed: 05/25/2004
• Published: 12/01/2005
• Est. Priority Date: 05/25/2004
• Status: Active Grant

• Current Assignee: Workday Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Lightstone, Sam Sampson, Garcia-Arellano, Christian Marcelo, Surendra, Maheswaran, Diao, Yixin, Hellerstein, Joseph L., Parekh, Sujay Sunil, Storm, Adam J.
• Granted Patent: US 7,346,401 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Systems and methods are provided for optimizing the performance and/or allocation of constrained resources in a dynamic computing environment using adaptive regulatory control methods. For example, systems and methods for providing constrained optimization in a dynamic computing system implement model-based adaptive (self-tuning) regulatory control schemes that are designed to handle the system dynamics and which take into consideration control costs (such as the overheads of changing resource allocations and performance degradation due to transient load imbalances) to find an optimal solution. To facilitate practical application, a dual control architecture is disclosed which combines a heuristic fixed step control process that is implemented when there is no valid system model for model-based control. A system model is continually obtained and validated during run-time to adapt control parameters to variations in system dynamics.

Claims

1. A method for managing resources in a dynamic computing system, the method comprising optimizing allocation and/or performance of a constrained resource in the dynamic computing system using an adaptive regulatory control process.

2. The method of claim 1, wherein the constrained resource comprises memory resources.

3. The method of claim 1, wherein using an adaptive regulatory control process comprises:

building a system model of a target system using run-time data comprising system metrics that quantify performance of the target system;

determining controller parameters based on the system model to implement a feedback controller; and

generating control inputs based on the controller parameters to control the target system.

4. The method of claim 3, wherein building a system model of the target system comprises determining a linear MIMO (multiple input multiple output) model by modeling a relationship between data pairs of control inputs and the system metrics.

5. The method of claim 3, wherein determining controller parameters comprises determining controller gain parameters using LQR (linear quadratic regulation) to implement a MIMO controller.

6. The method of claim 3, wherein determining controller parameters comprises determining controller gain parameters using a pole assignment process to implement a MIMO controller.

7. The method of claim 3, wherein determining controller parameters comprises determining controller gain parameters that consider costs of control including a cost of transient load imbalances and a cost of changing resource allocations.

8. The method of claim 3, further comprising:

determining if the built system model is valid; and

if the built system model is deemed not valid, using a heuristic fixed step controller to control the target system or using an adaptive regulatory control process that is based on a previously built valid system model.

9. The method of claim 1, wherein optimizing comprises allocating a system resource among a plurality of resource consumers of the dynamic computing system to maximize performance of the dynamic computing system subject to the constraint that amount of the resource to be allocated is fixed.

10. The method of claim 9, wherein the plurality of resource consumers comprise memory pools of a database server, wherein a total size of the memory pools is fixed, and wherein optimizing comprises adjusting memory resource allocations to the memory pools to maximize a total disk response time over all the memory pools subject to a constraint that a sum of changes in memory resource allocations over all the memory pools is always 0.

11. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing computing resources in a dynamic computing environment, the method steps comprising optimizing allocation and/or performance of a constrained resource in the dynamic computing system using an adaptive regulatory control process.

12. The program storage device of claim 11, wherein the constrained resource comprises memory resources.

13. The program storage device of claim 11, wherein the instructions for using an adaptive regulatory control process comprise instructions for:

building a system model of a target system using run-time data comprising system metrics that quantify performance of the target system;

determining controller parameters based on the system model to implement a feedback controller; and

generating control inputs based on the controller parameters to control the target system.

14. The program storage device of claim 13, wherein the instructions for building a system model of the target system comprise instructions for determining a linear MIMO (multiple input multiple output) model by modeling a relationship between data pairs of control inputs and the system metrics.

15. The program storage device of claim 13, wherein the instructions for determining controller parameters comprise instructions for determining controller gain parameters using LQR (linear quadratic regulation) to implement a MIMO controller.

16. The program storage device of claim 13, wherein the instructions for determining controller parameters comprise instructions for determining controller gain parameters using a pole assignment process to implement a MIMO controller.

17. The program storage device of claim 13, wherein the instructions for determining controller parameters comprise instructions for determining controller gain parameters that consider costs of control including a cost of transient load imbalances and a cost of changing resource allocations.

18. The program storage device of claim 13, further comprising instructions for:

determining if the built system model is valid; and

if the built system model is deemed not valid, using a heuristic fixed step controller to control the target system or using an adaptive regulatory control process that is based on a previously built valid system model.

19. The program storage device of claim 11, wherein the instructions for optimizing comprise instructions for allocating a system resource among a plurality of resource consumers of the dynamic computing system to maximize performance of the dynamic computing system subject to the constraint that amount of the resource to be allocated is fixed.

20. The program storage device of claim 19, wherein the plurality of resource consumers comprise memory pools of a database server, wherein a total size of the memory pools is fixed, and wherein the instructions for optimizing comprise instructions for adjusting memory resource allocations to the memory pools to maximize a total disk response time over all the memory pools subject to a constraint that a sum of changes in memory resource allocations is always 0.

21. A method for managing resources in a dynamic computing system, comprising:

determining a performance metric value for each of a plurality of resource consumers of a target system;

determining a control reference value as an average of the performance metric values of the resource consumers;

determining a control error for each resource consumer as a difference between the performance metric value of the resource consumer and the control reference value; and

controlling the target system using a control method that optimizes resource allocations for the resource consumers by minimizing the control errors subject to a constraint.

22. The method of claim 21, wherein controlling the target system comprises using a model-based feedback controller to generate control inputs for controlling the resource consumers based on control parameters that are determined based on model parameters of a system model of the target system.

23. The method of claim 22, wherein controlling the target system comprises:

determining an optimal resource allocation for each of the resource consumers using the model-based feedback controller; and

adjusting the resource allocation of the resource consumers based on the optimal resource allocations subject to the constraint that a total amount of the resource to be allocated among the resource consumers is fixed.

24. The method of claim 22, wherein the model based-feedback controller comprises a MIMO controller that is based on a linear MIMO model of the target system.

25. The method of claim 22, further comprising building the system model of the target system based on run-time values of control inputs and performance metrics that are collected for the resource consumers.

26. The method of claim 25, wherein building the system model comprises building and validating a system model on a continual basis to adapt the controller parameters to variations in dynamics of the target system.

27. The method of claim 21, wherein the plurality of resource consumers comprise memory pools of a database server, wherein a total size of the memory pools is fixed, and wherein controlling the target system comprises adjusting memory resource allocations to the memory pools to maximize a total disk response time over all the memory pools subject to a constraint that a sum of changes in memory resource allocations over all the memory pools is always 0.

28. The method of claim 22, wherein the controller parameters comprise controller gain parameters that consider costs of control including a cost of transient load imbalances and a cost of changing resource allocations.

29. The method of claim 28, comprising the step of determining the controller gain parameters using LQR.

30. A dynamic computing system, comprising:

a system resource;

a target system comprising a plurality of resource consumers of the system resource; and

a control system to control allocations of the system resource to the resource consumers using an adaptive regulatory controller that optimizes the resource allocations to the resource consumers subject to a constraint.

31. The system of claim 30, wherein the constraint is that the amount of the system resource is fixed.

32. The system of claim 30, further comprising a statistics collection system that determines a performance metric value for each resource consumer of the target system, wherein the control system optimizes the resource allocations to the resource consumers by equalizing the performance metric values of the resource consumers subject to the constraint that a sum of changes in resource allocations to the memory pools is equal to 0.

33. The system of claim 32, wherein the dynamic computing system is a database server comprising disks for storing data, the system resource is memory, and wherein the resource consumers comprise memory pools that cache copies of data stored in the disks.

34. The system of claim 33, wherein the performance metric for a given memory pool is a measure of saved disk response time per unit memory increase of the memory pool.

35. The system of claim 30, wherein the adaptive regulatory controller comprises a model based-feedback controller that is based on a linear MIMO model of the target system.

36. The system of claim 35, wherein the model-based feedback controller is a MIMO LQR controller.

37. The system of claim 31, wherein the control system comprises:

a model building process that continually builds a system model of the target system based on run-time input/output data of the target system for implementation by the adaptive regulatory controller; and

a model validation process that determines if a system model is valid before implementation by the adaptive regulatory controller.

38. The system of claim 37, wherein the control system comprises a heuristic controller that adjusts resource allocations for the resource consumers in fixed increments subject to the constraint, wherein the control system uses the heuristic controller when there is no valid system model for implementation by the adaptive regulatory controller for model-based control.