Scheduling jobs on interruptible cloud computing instances

Abstract

Techniques are provided for scheduling multiple jobs on one or more cloud computing instances, which provide the ability to select a job for execution from among a plurality of jobs, and to further select a designated instance from among a plurality of cloud computing instances for executing the selected job. The job and the designated instance are each selected based on a probability distribution that a cost of executing the job on the designated instance does not exceed the budget. The probability distribution is based on several factors including a cost of prior executions of other jobs on the designated instance and a utility function that represents a value associated with a progress of each job. By scheduling select jobs on discounted cloud computing instances, the aggregate utility of the jobs can be maximized or otherwise improved for a given budget.

What is claimed is: 
     
       1. A method for cloud computing instance scheduling, the method comprising:
 receiving a request to schedule a plurality of jobs, the request including a budget representing a maximum permitted cost to execute a combination of the jobs; 
 selecting i) a first job for execution from among the plurality of jobs and ii) a designated instance from among a plurality of cloud computing instances for executing the first job selected for execution, wherein the selecting is based on a probability distribution on a time and a cost of executing the first job selected for execution on the designated instance before interruption, the probability based on a profiling of prior executions of other jobs on the designated instance and a utility function representing a value associated with a progress of each of the plurality of jobs including an overhead cost associated with rescheduling each of the plurality of jobs due to the interruption; 
 sending a request to execute the first job selected for execution to the designated instance 
 receiving, from the designated instance, an indication that the first job selected for execution has been interrupted during the execution; 
 updating, responsive to receiving the indication, the utility function based on a remaining budget after deducting, from the budget, a cost incurred for executing the first job until the interruption occurred and the overhead cost 
 selecting a second job for execution from among the plurality of jobs based on the updated utility function; and 
 sending a request to execute the second job selected for execution to the designated instance. 
 
     
     
       2. The method of  claim 1 , further comprising:
 selecting a new designated instance from among the plurality of cloud computing instances for resuming execution of the first job; and 
 storing, in a processed job data store, a state of completion of the first job selected for execution at or prior to interruption of execution of the first job. 
 
     
     
       3. The method of  claim 2 , further comprising sending, to the new designated instance, a request to resume execution of the first job selected for execution starting from the state of completion of the first job selected for execution at or prior to the interruption of execution of the first job. 
     
     
       4. The method of  claim 2 , wherein the utility function further represents an expected amount of completion of the second job prior to an interruption. 
     
     
       5. The method of  claim 1 , wherein the utility function is a submodular set function a probability distribution that the first job selected for execution executes, on the designated instance, and a probability distribution that the first job is interrupted after a certain period of time. 
     
     
       6. The method of  claim 1 , wherein the utility function is a piece-wise linear increasing function of an execution progress of the first job selected for execution and a probability that the first job selected for execution executes, on the designated instance, to completion without interruption and within the respective budget. 
     
     
       7. The method of  claim 1 , wherein the first job selected for execution is a machine learning training job to be executed on a single, non-distributed cloud computing instance, the machine learning training job including a stochastic approximation process for training a machine learning model from a set of training data. 
     
     
       8. A system for cloud computing instance scheduling, the system comprising:
 at least one processor; and 
 a scheduler module executable by the at least one processor and configured to 
 receive a request to schedule a plurality of jobs, the request including a budget representing a maximum permitted cost to execute a combination of the jobs; 
 select i) a job for execution from among the plurality of jobs and ii) a designated instance from among a plurality of cloud computing instances for executing the job selected for execution, wherein the selecting is based on a probability distribution on a time and a cost of executing the job selected for execution on the designated instance before interruption, the probability distribution being based on a profiling of prior executions of other jobs on the designated instance and a utility function representing a value associated with a progress of each of the plurality of jobs including an overhead cost associated with rescheduling each of the plurality of jobs due to the interruption; and 
 send a request to execute the job selected for execution to the designated instance. 
 
     
     
       9. The system of  claim 8 , the scheduler module further configured to:
 receive, from the designated instance, an indication that the job selected for execution has completed execution or an indication that the job selected for execution has been interrupted during the execution; 
 select a new designated instance from among the plurality of cloud computing instances for resuming execution of the job; and 
 store, in a processed job data store, a state of completion of the job selected for execution at or prior to interruption of execution. 
 
     
     
       10. The system of  claim 9 , wherein the indication is that the job selected for execution has been interrupted during the execution, and wherein the scheduler module is further configured to send, to the new designated instance, a request to resume execution of the job selected for execution starting from the state of completion of the job selected for execution at or prior to the interruption of execution. 
     
     
       11. The system of  claim 9 , wherein the job selected for execution is a first job, and wherein the scheduler module is further configured to:
 select a second job for execution on the designated instance based on a remaining budget and the utility function, the remaining budget being the budget less a cost of executing the first job on the designated instance prior to receiving the indication and the overhead cost, the utility function representing an expected amount of completion of the second job prior to an interruption; and 
 send, to the designated instance, a job execution request for executing the second job on the designated instance. 
 
     
     
       12. The system of  claim 8 , further comprising a profiler module executable by the at least one processor and configured to calculate the utility function as a maximized submodular set function of a size of the job selected for execution and a probability that the job selected for execution executes, on the designated instance, to completion without interruption and within the respective budget. 
     
     
       13. The system of  claim 8 , further comprising a profiler module executable by the at least one processor and configured to calculate the utility function as a piece-wise linear increasing function of an execution progress of the job selected for execution and a probability that the job selected for execution executes, on the designated instance, to completion without interruption and within the respective budget. 
     
     
       14. The system of  claim 8 , wherein the job selected for execution is a machine learning training job to be executed on a single, non-distributed cloud computing instance, the machine learning training job including a stochastic approximation process for training a machine learning model from a set of training data. 
     
     
       15. A computer program product including one or more non-transitory machine-readable mediums encoded with instructions that when executed by one or more processors cause a process to be carried out for cloud computing instance scheduling, the process comprising:
 receiving a request to schedule a plurality of jobs, the request including a budget representing a maximum permitted cost to execute a combination of the jobs; 
 selecting i) a job for execution from among the plurality of jobs and ii) a designated instance from among a plurality of cloud computing instances for executing the job selected for execution, wherein the selecting is based on a probability distribution on a time and a cost of executing the job selected for execution on the designated instance before interruption, the probability distribution being based on a profiling of prior executions of other jobs on the designated instance and a utility function representing a value associated with a progress of each of the plurality of jobs including an overhead cost associated with rescheduling each of the plurality of jobs due to the interruption; and 
 sending a request to execute the job selected for execution to the designated instance. 
 
     
     
       16. The computer program product of  claim 15 , wherein the process further comprises:
 receiving, from the designated instance, an indication that the job selected for execution has completed execution or an indication that the job selected for execution has been interrupted during the execution; 
 selecting a new designated instance from among the plurality of cloud computing instances for resuming execution of the job; and 
 storing, in a processed job data store, a state of completion of the job selected for execution at or prior to interruption of execution. 
 
     
     
       17. The computer program product of  claim 16 , wherein the indication is that the job selected for execution has been interrupted during the execution, and wherein the process further comprises sending, to the new designated instance, a request to resume execution of the job selected for execution starting from the state of completion of the job selected for execution at or prior to the interruption of execution. 
     
     
       18. The computer program product of  claim 16 , wherein the job selected for execution is a first job, and wherein the process further comprises:
 selecting a second job for execution on the designated instance based on a remaining budget and the utility function, the remaining budget being the budget less a cost of executing the first job on the designated instance prior to receiving the indication, the utility function representing an expected amount of completion of the second job prior to an interruption; and 
 sending, to the designated instance, a job execution request for executing the second job on the designated instance. 
 
     
     
       19. The computer program product of  claim 15 , wherein the utility function is a submodular set function based on the probability distribution that the job selected for execution executes, on the designated instance, and the probability distribution that they get interrupted after a certain period of time. 
     
     
       20. The computer program product of  claim 15 , wherein the utility function is a piece-wise linear increasing function of an execution progress of the job selected for execution and a probability that the job selected for execution executes, on the designated instance, to completion without interruption and within the respective budget.