Dynamic online multi-parameter optimization system and method for autonomic computing systems

Abstract

An improved method and system for performing dynamic online multi-parameter optimization for autonomic computing systems are provided. With the method and system of the present invention, a simplex, i.e. a set of points in the parameter space that has been directly sampled, is maintained. The system's performance with regard to a particular utility value is measured for the particular setting of configuration parameters associated with each point in the simplex. A new sample point is determined using the geometric transformations of the simplex. The method and system provide mechanisms for limiting the size of the simplex that is generated through these geometric transformations so that the present invention may be implemented in noisy environments in which the same configuration settings may lead to different results with regard to the utility value. In addition, mechanisms are provided for resampling a current best point in the simplex to determine if the environment has changed. If a sufficiently different utility value is obtained from a previously sampled utility value for the point in the simplex, then rather than contracting, the simplex is expanded. If the difference between utility values is not sufficient enough, then contraction of the simplex is performed. In addition, in order to allow for both real and integer valued parameters in the simplex, a mechanism is provided by which invalid valued parameters that are generated by geometric transformations being performed on the simplex are mapped to a nearest valid value. Similarly, parameter values that violate constraints are mapped to values that satisfy constraints taking care that the dimensionality of the simplex is not reduced.

Description

BACKGROUND OF THE INVENTION 1. Technical Field The present invention is directed to an improved computing system. More specifically, the present invention is directed to an improved method and system for dynamically determining configuration values for improved performance in an autonomic computing system based on geometrical simplex transformations in the underlying multi-dimensional parameter space. 2. Description of Related Art The success of service-oriented Information Technology, such as Autonomic Computing, On-demand eBusiness and eCommerce, depends critically on the ability to provide information, goods, and services in a fast, efficient and cost-effective fashion. Unfortunately, the increasing complexity of the computing systems necessary to provide these services is rapidly outstripping human ability for system operation. This is especially true when it comes to optimization of system parameters for these complex computing systems. The fundamental difficulties in real...

AI Technical Summary

Benefits of technology

The present invention provides mechanisms for limiting the size of the simplex that is generated through these geometric transformations so that the present invention may be implemented in noisy environments in which the same configuration settings may lead to different results with regard to the utility value. In addition, the present invention further includes a mechanism for resampling a current best point in the simplex to determine if the environment has changed. If a sufficiently different utility value is obtained from a previously sampled utility value for the point in the simplex, then rather than contracting, the simplex is expanded. If the difference between utility values is not sufficient enough, then contraction of the simplex is performed.

Problems solved by technology

Unfortunately, the increasing complexity of the computing systems necessary to provide these services is rapidly outstripping human ability for system operation.

The fundamental difficulties in real-time optimization of system parameters in large complex systems arise from a number of sources.

In many situations, a good model of the system and the way the system interacts with the world is not available (or may be too expensive to obtain).

The lack of such a system model prohibits the use of sophisticated analytical and simulation tools for online (i.e., real-time) or offline optimization of the system parameters.

The problem is further compounded by the fact that there may be multiple parameters that have to be optimized simultaneously to improve system performance.

Since a model of the system is not accessible, there is little understanding of the relative importance of the different system parameters (in terms of how each parameter effects the system's performance) and of the potential nonlinear interactions between the different parameters (in terms of their combined effect on the system's performance).

Unfortunately, due to the curse of dimensionality, the number of necessary samples increases exponentially with the number of parameters to be optimized.

Thus, even for a small set of parameters, the cost and time needed for a reasonable sampling of the multidimensional parameter space may be too prohibitive.

Moreover, for these reasons, such sampling and optimization cannot be performed dynamically in real-time.

In addition, a system's behavior may be stochastic in nature and / or it may operate in a noisy and dynamic environment, such that similar system configuration parameters may result in very different overall performance measures or utility values.

Thus, the ability to use historical data to infer a system model is seriously jeopardized, especially in a dynamic environment where demand or the load that is placed on the system is changing continuously over time.

In addition, these methods use a variety of techniques for steep descent (but not necessarily methods of steepest descent) to arrive at near optimal solutions.

Unfortunately, a direct application of the Direct Search method (and its variants) to automatically configure and optimize system parameters in Autonomic Computing systems is likely to fail for a number of reasons.

First, Direct Search methods (and its variants) do not work in dynamic environments, where the demand or the load on the system is changing continuously over time, and where the same parameter settings can provide different performance measures at different times. Direct Search methods were designed for static problems and have no built-in mechanism to handle dynamic environments.

Second, Direct Search methods work only for deterministic problems where there is no noise either in measurements of the system's performance on in the system's dynamics.

In noisy or stochastic environments, where such an assumption is not valid, Direct Search methods can fail dramatically in finding good solution regions quickly.

Third, Direct Search methods make certain assumptions about the nature of the parameters being optimized.

In such scenarios, existing Direct Search methods, and the variants, can fail spectacularly since they fail to take the differences in the underlying granularity of the parameter space into account.

Fourth, Direct Search methods, and the variants, cannot handle relational constraints between the parameters being optimized.

In many problems of system configuration and optimization, there exist constraints that involve one or more parameters.

Direct Search methods, and the variants, were designed for unconstrained problems and are highly inefficient in finding good parameter settings in constrained optimization problems.

Thus they have not been employed in online constrained optimization problems.

Finally, Direct Search methods, and the variants, suffer from a number of pathological failure modes that prevent their direct application in many types of optimization problems.

For example, in problems with real-valued parameters, the size of the simplex can become infinitesimally small; limiting the Direct Search method's ability to track changes in the optimal parameter settings in dynamic environments.

On the other hand, in problems with discrete or integer values, the simplex can easily get stuck in a rut where the Direct Search method is unable to decide on a new point to sample.

This pathological failure mode limits Direct Search method's ability to explore promising regions in parameter space.

Images