We propose adaptive online application runtime prediction methods to improve application latency in clouds. Scheduling algorithms are highly sensitive to the value of application runtime. %Currently available schedulers rely on inaccurate user predictions as well as inaccurate over the shelf forecasting tools. Predicting the application runtime values in the cloud is challenging because of highly dynamic nature of application runtime values, the requirement of real-time prediction and scarcity of training data. To provide an accurate and fast online prediction model, we first analyze available HPC traces and design hybrid models from adaptive online generative models known as State Space Models. We show how State Space Models are generalizations of widely used methods for application runtime prediction in HPC clusters including exponential smoothing and recursive least square. To overcome high variance of application runtimes in the cloud, our proposed methods facilitate on-the-fly automated model selection and model switching. Our machine learning prediction results on HPC application traces show that our adaptive online prediction models predict the runtimes 33% to 80% more accurately than existing prediction approaches. Besides, our extensive trace-based scheduling simulations show that our predicted runtimes improve the performance (wait time) by 25%.

We consider the problem of scheduling jobs with varying demands on multiple servers. Each server has a certain computing capacity and can schedule multiple jobs simultaneously as long as the jobs' total demand does not exceed the server's capacity. This scenario arises commonly in virtualization, cloud computing, and MapReduce (or Hadoop). We study this problem with the requirement that jobs must be scheduled non-preemptively, meaning that every job must be completed without interruption once it gets started. Often, preemption is out of choice since preempting a job can be prohibitively costly or is not allowed due to system constraints. We focus on the popular objective of minimizing total completion time of jobs. This problem is NP hard hence we study heuristics with provable approximation guarantees. Succinctly, the interaction between two orthogonal quantities, jobs demands and sizes makes the scheduling decision significantly more challenging. In this paper we propose novel algorithms for scheduling jobs with non-uniform demands on multiple homogeneous servers without preemption. We first observe that the Smallest Volume First (SVF) algorithm that favors jobs with smaller volumes could perform very poorly in general. However, we show that SVF yields a nearly optimal schedule when the system is overloaded and jobs have demands considerably smaller than servers' capacities. This result supports the intuition that SVF should work well unless some jobs with high demands occupy the servers for long, blocking other jobs. Building on this intuition and using reduction to geometric packing problems, we develop algorithms that are constant approximation for all instances for the first time. Prior to our work, there was no theoretical study on this problem even for the single server case.