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.

1 . A method, in a data processing system, for determining configuration parameter value settings for a computing device to optimize an operational characteristic of the computing device, comprising: 
 obtaining a simplex of points, wherein each point in the simplex represents a set of configuration parameters for the computing device;    performing a geometric transformation on the simplex of points to identify a new point to investigate;    sampling the operational characteristic at the new point;    determining if the operational characteristic associated with the new point is worse than a value of the operational characteristic for each point in the simplex of points;    determining a set of points in the simplex that need to be resampled if the new point is worse than a value of the operational characteristic for each point int he simplex of points;    resampling the operational characteristic at each of the points in the set of points; and    determining a new simplex based on the resampled operational characteristic of points in the set of points.    
   
   
       2 . The method of  claim 1 , wherein the set of points comprises a best point in the simplex of points, and wherein determining a new simplex based on the resampled operational characteristic of points in the set of points includes determining whether to expand or contract the simplex based on the resampling of the operational characteristic at the best point in the simplex of points to obtain the new simplex.  
   
   
       3 . The method of  claim 1 , further comprising: 
 extending the simplex in a direction of the new point if the operational characteristic of the new point is better than values of the operational characteristic for each point in the simplex of points.    
   
   
       4 . The method of  claim 1 , further comprising: 
 assigning an upper threshold and a lower threshold to a size of the simplex; and    limiting expansion or contraction of the simplex based on the assigned upper and lower thresholds.    
   
   
       5 . The method of  claim 4 , wherein the lower threshold on the size of the simplex represents a lowest resolution of significance for each of the parameters of the simplex.  
   
   
       6 . The method of  claim 4 , wherein if one or more of the configuration parameter values associated with the new point violates one of the upper threshold and lower threshold, the new point is mapped to a point closest to the new point whose associated configuration parameter values satisfy the upper threshold or lower threshold.  
   
   
       7 . The method of  claim 2 , wherein determining whether to expand or contract the simplex based on the resampling of the operational characteristic at the best point in the simplex of points includes: 
 comparing a resampled operational characteristic value for the best point to a previous operational characteristic value for the best point; and    determining whether to expand or contract the simplex based on a difference between the resampled operational characteristic value and the previous operational characteristic value.    
   
   
       8 . The method of  claim 7 , wherein if the difference is greater than a threshold, the simplex is expanded.  
   
   
       9 . The method of  claim 7 , wherein if the difference is not greater than a threshold, then the simplex is contracted.  
   
   
       10 . The method of  claim 1 , wherein configuration parameter values for points in the simplex may include both real and integer configuration parameter values.  
   
   
       11 . The method of  claim 10 , further comprising: 
 checking the dimensionality of the modified simplex obtained by expanding or contracting the simplex; and    not performing the expansion or contraction if the modified simplex would have a different dimensionality from the simplex.    
   
   
       12 . The method of  claim 1 , further comprising: 
 converting configuration parameter values of the new point to one of integer and real values based on a value type for the configuration parameters;    checking the converted configuration parameter values to determine if a dimensionality of the simplex is changed by the conversion of the configuration parameters; and    setting the converted configuration parameter values of the new point that result in a change in the dimensionality of the simplex to converted configuration parameter values that do not reduce the dimensionality of the simplex.    
   
   
       13 . The method of  claim 12 , wherein setting the converted configuration parameter values of the new point that result in a change in the dimensionality of the simplex to converted configuration parameter values that do not reduce the dimensionality of the simplex includes: 
 setting the converted configuration parameter values to converted configuration parameter values that equal the converted configuration parameter values minus a penalty value.    
   
   
       14 . The method of  claim 13 , wherein the penalty value is a quadratic function of a distance between an original configuration parameter value of the new point and the converted configuration parameter value.  
   
   
       15 . The method of  claim 1 , further comprising: 
 using configuration parameter values of the best point in the simplex to configure the computing device if no improvement of the simplex is obtainable.    
   
   
       16 . A computer program product in a computer readable medium for determining configuration parameter value settings for a computing device to optimize an operational characteristic of the computing device, comprising: 
 first instructions for obtaining a simplex of points, wherein each point in the simplex represents a set of configuration parameters for the computing device;    second instructions for performing a geometric transformation on the simplex of points to identify a new point to investigate;    third instructions for sampling the operational characteristic at the new point;    fourth instructions for determining if the operational characteristic associated with the new point is worse than a value of the operational characteristic for each point in the simplex of points;    fifth instructions for determining a set of points in the simplex that need to be resampled if the new point is worse than a value of the operational characteristic for each point int he simplex of points;    sixth instructions for resampling the operational characteristic at each of the points in the set of points; and    seventh instructions for determining a new simplex based on the resampled operational characteristic of points in the set of points.    
   
   
       17 . The computer program product of  claim 16 , wherein the set of points comprises a best point in the simplex of points, and wherein the seventh instructions for determining a new simplex based on the resampled operational characteristic of points in the set of points include instructions for determining whether to expand or contract the simplex based on the resampling of the operational characteristic at the best point in the simplex of points to obtain the new simplex.  
   
   
       18 . The computer program product of  claim 16 , further comprising: 
 eighth instructions for extending the simplex in a direction of the new point if the operational characteristic of the new point is better than values of the operational characteristic for each point in the simplex of points.    
   
   
       19 . The computer program product of  claim 16 , further comprising: 
 eighth instructions for assigning an upper threshold and a lower threshold to a size of the simplex; and    ninth instructions for limiting expansion or contraction of the simplex based on the assigned upper and lower thresholds.    
   
   
       20 . The computer program product of  claim 19 , wherein the lower threshold on the size of the simplex represents a lowest resolution of significance for each of the parameters of the simplex.  
   
   
       21 . The computer program product of  claim 19 , wherein if one or more of the configuration parameter values associated with the new point violates one of the upper threshold and lower threshold, the new point is mapped to a point closest to the new point whose associated configuration parameter values satisfy the upper threshold or lower. threshold.  
   
   
       22 . The computer program product of  claim 17 , wherein the instructions for determining whether to expand or contract the simplex based on the resampling of the operational characteristic at the best point in the simplex of points include: 
 instructions for comparing a resampled operational characteristic value for the best point to a previous operational characteristic value for the best point; and    instructions for determining whether to expand or contract the simplex based on a difference between the resampled operational characteristic value and the previous operational characteristic value.    
   
   
       23 . The computer program product of  claim 22 , wherein if the difference is greater than a threshold, the simplex is expanded.  
   
   
       24 . The computer program product of  claim 22 , wherein if the difference is not greater than a threshold, then the simplex is contracted.  
   
   
       25 . The computer program product of  claim 16 , wherein configuration parameter values for points in the simplex may include both real and integer configuration parameter values.  
   
   
       26 . The computer program product of  claim 25 , further comprising: 
 eighth instructions for checking the dimensionality of the modified simplex obtained by expanding or contracting the simplex; and    ninth instructions for not performing the expansion or contraction if the modified simplex would have a different dimensionality from the simplex.    
   
   
       27 . The computer program product of  claim 16 , further comprising: 
 eighth instructions for converting configuration parameter values of the new point to one of integer and real values based on a value type for the configuration parameters;    ninth instructions for checking the converted configuration parameter values to determine if a dimensionality of the simplex is changed by the conversion of the configuration parameters; and    tenth instructions for setting the converted configuration parameter values of the new point that result in a change in the dimensionality of the simplex to converted configuration parameter values that do not reduce the dimensionality of the simplex.    
   
   
       28 . The computer program product of  claim 27 , wherein the tenth instructions for setting the converted configuration parameter values of the new point that result in a change in the dimensionality of the simplex to converted configuration parameter values that do not reduce the dimensionality of the simplex include: 
 instructions for setting the converted configuration parameter values to converted configuration parameter values that equal the converted configuration parameter values minus a penalty value.    
   
   
       29 . The computer program product of  claim 28 , wherein the penalty value is a quadratic function of a distance between an original configuration parameter value of the new point and the converted configuration parameter value.  
   
   
       30 . The computer program product of  claim 16 , further comprising: 
 eighth instructions for using configuration parameter values of the best point in the simplex to configure the computing device if no improvement of the simplex is obtainable.    
   
   
       31 . An apparatus for determining configuration parameter value settings for a computing device to optimize an operational characteristic of the computing device, comprising: 
 means for obtaining a simplex of points, wherein each point in the simplex represents a set of configuration parameters for the computing device;    means for performing a geometric transformation on the simplex of points to identify a new point to investigate;    means for sampling the operational characteristic at the new point;    means for determining if the operational characteristic associated with the new point is worse than a value of the operational characteristic for each point in the simplex of points;    means for determining a set of points in the simplex that need to be resampled if the new point is worse than a value of the operational characteristic for each point int he simplex of points;    means for resampling the operational characteristic at each of the points in the set of points; and    means for determining a new simplex based on the resampled operational characteristic of points in the set of points.    
   
   
       32 . A method of configuring a computing device by optimizing configuration parameter value settings, comprising: 
 obtaining a simplex of points, wherein each point in the simplex represents a set of configuration parameters for the computing device, and wherein each point has a corresponding operational characteristic value associated with the point;    performing one or more geometric transformations on the simplex based on the operational characteristic values associated with the points of the simplex to identify a new points to investigate;    measuring a value of the operational characteristic based on a set of configuration parameters associated with the new points; and    configuring the computing device based on values of a set of configuration parameters associated with a best point in a resulting simplex, wherein performing the one or more geometric transformations includes checking the new points obtained from performing the one or more geometric transformations to determined if one or more conditions are violated and wherein the conditions are set so as to compensate for dynamic and noisy operating environments of the computing device.    
   
   
       33 . The method of  claim 32 , wherein performing the one or more geometric transformations includes: 
 applying an upper and lower limit on a size of the simplex;    comparing new point configuration parameter values against the upper and lower limit; and    adjusting the new point configuration parameter values based on the comparison.    
   
   
       34 . The method of  claim 32 , wherein performing the one or more geometric transformations includes: 
 permitting both real and integer valued configuration parameter values;    determining if new point configuration parameter values result in a reduction in dimensionality of the simplex; and    adjusting the new point configuration parameter values based on the determination.    
   
   
       35 . The method of  claim 32 , wherein performing the one or more geometric transformations includes: 
 resampling the operational characteristic at a best point in the simplex if a geometric transformation does not result in a new point whose configuration parameter values result in a better operational characteristic value;    comparing a resampled operational characteristic value of the best point to an original operational characteristic value of the best point; and    determining whether to expand or contract the simplex based on the comparison.