Monte Carlo grid scheduling algorithm selection optimization

Abstract

A method for utilizing the Monte Carlo method to determine the most efficient arrangement of schedulers for a grid using a Scheduler Optimization Program (SOP). The SOP obtains the schedulers and scheduler timetable from memory and randomly selects a time period and scheduler to analyze. The SOP then uses the selected scheduler to modify the scheduler timetable. The SOP then runs the ROI calculator to obtain a ROI property for the modified timetable. If the ROI property for the modified timetable is greater than the ROI property for the original scheduler timetable, the SOP replaces the scheduler timetable with the modified timetable.

1 . A method for optimizing an allocation of a plurality of schedulers within a grid computing network wherein the allocation is determined by a return on investment calculator.  
   
   
       2 . A method of  claim 1  comprising: 
 selecting a first scheduler;    obtaining a first scheduler timetable and a first scheduler timetable return on investment property;    creating a second scheduler timetable by modifying the first scheduler timetable with the first scheduler;    running the return on investment calculator to obtain a second scheduler return on investment property;    determining whether the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property; and    responsive to the determination that the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property, replacing the first scheduler timetable with the second scheduler timetable.    
   
   
       3 . The method of  claim 2  further comprising: 
 responsive to the determination that the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property, replacing the first scheduler timetable return on investment property with the second scheduler timetable return on investment property.    
   
   
       4 . The method of  claim 2  further comprising: 
 determining whether the second scheduler timetable is in a previous results file; and    responsive to the determination that the second scheduler timetable is not in the previous results file, saving the second scheduler timetable in the previous results file and performing the steps in  claim 2 .    
   
   
       5 . The method of  claim 2  further comprising: 
 determining whether the second scheduler timetable is in a previous results file; and    responsive to the determination that the second scheduler timetable is in the previous results file, selecting a new first scheduler.    
   
   
       6 . The method of  claim 2  further comprising: 
 determining if a plateau has been reached; and    responsive to the determination that the plateau has not been reached, repeating the steps of  claim 2 .    
   
   
       7 . The method of  claim 2  wherein the selection of a first time period and the first scheduler is random.  
   
   
       8 . The method of  claim 2  further comprising: taking a user configurable number of steps away from a greater return on investment property, and then repeating the steps in  claim 2 .  
   
   
       9 . The method of  claim 8  wherein the step of taking a user configurable number of steps away from a greater return on investment property comprises: 
 accepting a user-configurable number of backward steps;    taking a backward step comprising: 
 selecting a first scheduler;  
 obtaining a first scheduler timetable and a first scheduler timetable return on investment property;  
 creating a second scheduler timetable by modifying the first scheduler timetable with the first scheduler;  
 running the return on investment calculator to obtain a second scheduler return on investment property;  
 determining whether the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property; and  
 responsive to the determination that the second scheduler timetable return on investment property is not greater than the first scheduler timetable return on investment property, replacing the first scheduler timetable with the second scheduler timetable.  
   
   
   
       10 . The method of  claim 9  wherein taking the backward step further comprising: 
 responsive to the determination that the second scheduler timetable return on investment property is not greater than the first scheduler timetable return on investment property, replacing the first scheduler timetable return on investment property with the second scheduler timetable return on investment property.    
   
   
       11 . The method of  claim 9  further comprising: 
 determining whether the number of backward steps taken equals the user-configurable number of backward steps;    responsive to the determination that the number of backward steps taken equals the user-configurable number of backward steps, repeating the steps in  claim 2 .    
   
   
       12 . The method of  claim 9  further comprising: 
 determining whether the number of backward steps taken equals the user-configurable number of backward steps;    responsive to the determination that the number of backward steps taken does not equal the user-configurable number of backward steps, repeating the steps in  claim 9 .    
   
   
       13 . A program product for optimizing an allocation of a plurality of schedulers within a grid computing network wherein the allocation is determined by a return on investment calculator.  
   
   
       14 . A program product of  claim 13  comprising: 
 a computer-usable medium;    wherein the computer usable medium comprises instructions comprising: 
 instructions for selecting a first scheduler;  
 instructions for obtaining a first scheduler timetable and a first scheduler timetable return on investment property;  
 instructions for creating a second scheduler timetable by modifying the first scheduler timetable with the first scheduler;  
 instructions for running the return on investment calculator to obtain a second scheduler return on investment property;  
 instructions for determining whether the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property; and  
 responsive to the determination that the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property, instructions for replacing the first scheduler timetable with the second scheduler timetable.  
   
   
   
       15 . The program product of  claim 14  further comprising: 
 responsive to the determination that the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property, instructions for replacing the first scheduler timetable return on investment property with the second scheduler timetable return on investment property.    
   
   
       16 . The program product of  claim 14  further comprising: 
 instructions for determining whether the second scheduler timetable is in a previous results file; and    responsive to the determination that the second scheduler timetable is not in the previous results file, instructions for saving the second scheduler timetable in the previous results file and performing the steps in  claim 14 .    
   
   
       17 . The program product of  claim 14  further comprising: 
 instructions for determining whether the second scheduler timetable is in a previous results file; and    responsive to the determination that the second scheduler timetable is in the previous results file, instructions for selecting a new first scheduler.    
   
   
       18 . The program product of  claim 14  further comprising: 
 instructions for determining if a plateau has been reached; and    responsive to the determination that the plateau has not been reached, instructions for repeating the steps of  claim 14 .    
   
   
       19 . The program product of  claim 14  wherein the selection of a first time period and the first scheduler is random.  
   
   
       20 . The program product of  claim 14  further comprising: taking a user configurable number of steps away from a greater return on investment property, and then repeating the steps in  claim 14 .  
   
   
       21 . The program product of  claim 20  wherein the step of taking a user configurable number of steps away from a greater return on investment property comprises: 
 instructions for accepting a user-configurable number of backward steps;    instructions for taking a backward step comprising: 
 instructions for selecting a first scheduler;  
 instructions for obtaining a first scheduler timetable and a first scheduler timetable return on investment property;  
 instructions for creating a second scheduler timetable by modifying the first scheduler timetable with the first scheduler;  
 instructions for running the return on investment calculator to obtain a second scheduler return on investment property;  
 instructions for determining whether the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property; and  
 responsive to the determination that the second scheduler timetable return on investment property is not greater than the first scheduler timetable return on investment property, instructions for replacing the first scheduler timetable with the second scheduler timetable.  
   
   
   
       22 . The program product of  claim 21  wherein taking the backward step further comprising: 
 responsive to the determination that the second scheduler timetable return on investment property is not greater than the first scheduler timetable return on investment property, instructions for replacing the first scheduler timetable return on investment property with the second scheduler timetable return on investment property.    
   
   
       23 . The program product of  claim 21  further comprising: 
 instructions for determining whether the number of backward steps taken equals the user-configurable number of backward steps;    responsive to the determination that the number of backward steps taken equals the user-configurable number of backward steps, instructions for repeating the steps in  claim 14 .    
   
   
       24 . The program product of  claim 21  further comprising: 
 instructions for determining whether the number of backward steps taken equals the user-configurable number of backward steps;    responsive to the determination that the number of backward steps taken does not equal the user-configurable number of backward steps, instructions for repeating the steps in  claim 21 .    
   
   
       25 . An apparatus for optimizing an allocation of a plurality of schedulers within a grid computing network wherein the allocation is determined by a return on investment calculator comprising: 
 means for selecting a first scheduler;    means for obtaining a first scheduler timetable and a first scheduler timetable return on investment property;    means for creating a second scheduler timetable by modifying the first scheduler timetable with the first scheduler;    means for selecting a first time period;    means for determining whether the first time period coincides with a second time period in the first scheduler timetable;    responsive to the determination that the first time period does not coincide with the second time period, means for dividing the first time period and the second time period so that the first time period and the second time period coincide;    means for determining whether the second scheduler timetable is in a previous results file; and    responsive to the determination that the second scheduler timetable is in the previous results file, means for selecting a new first scheduler;    responsive to the determination that the second scheduler timetable is not in the previous results file, means for saving the second scheduler timetable in the previous results file;    means for running the return on investment calculator to obtain a second scheduler return on investment property;    means for determining whether the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property;    responsive to the determination that the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property, means for replacing the first scheduler timetable with the second scheduler timetable;    responsive to the determination that the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property, means for replacing the first scheduler timetable return on investment property with the second scheduler timetable return on investment property; and    wherein the selection of a first time period and the first scheduler is random.    
   
   
       26 . The apparatus of  claim 17  further comprising: 
 means for determining if a plateau has been reached; and    responsive to the determination that the plateau has not been reached, means for repeating the steps of  claim 17 .    
   
   
       27 . The apparatus of  claim 17  further comprising: means for taking a user configurable number of steps away from a greater return on investment property, and then repeating the steps in  claim 17 .  
   
   
       28 . The apparatus of  claim 27  wherein the step of taking a user configurable number of steps away from a greater return on investment property comprises: 
 means for accepting a user-configurable number of backward steps;    means for taking a backward step comprising: 
 means for selecting a first scheduler;  
 means for obtaining a first scheduler timetable and a first scheduler timetable return on investment property;  
 means for creating a second scheduler timetable by modifying the first scheduler timetable with the first scheduler;  
 means for running the return on investment calculator to obtain a second scheduler return on investment property;  
 means for determining whether the second scheduler timetable return on investment property is greater than the first scheduler timetable return on investment property; and  
 responsive to the determination that the second scheduler timetable return on investment property is not greater than the first scheduler timetable return on investment property, means for replacing the first scheduler timetable with the second scheduler timetable.  
   
   
   
       29 . The apparatus of  claim 28  wherein taking the backward step further comprising: 
 responsive to the determination that the second scheduler timetable return on investment property is not greater than the first scheduler timetable return on investment property, means for replacing the first scheduler timetable return on investment property with the second scheduler timetable return on investment property.    
   
   
       30 . The apparatus of  claim 28  further comprising: 
 means for determining whether the number of backward steps taken equals the user-configurable number of backward steps;    responsive to the determination that the number of backward steps taken equals the user-configurable number of backward steps, means for repeating the steps in  claim 25 .    
   
   
       31 . The apparatus of  claim 28  further comprising: 
 means for determining whether the number of backward steps taken equals the user-configurable number of backward steps;    responsive to the determination that the number of backward steps taken does not equal the user-configurable number of backward steps, means for repeating the steps in  claim 28.