Deep Reinforcement Learning Enhanced Greedy Algorithm for Online Scheduling of Batched Tasks in Cloud in Cloud HPC Systems
Yuanhao Yang, Hong Shen
Abstract
In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogenous servers for achieving the goal of maximize systems net gain defined as the value of completed tasks minus system operation cost. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing we deploy a DRL module to make prediction for the best allocation sequence for each arriving batch of tasks based on knowledge (allocation strategies) learnt from prior batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximally increase the total gain. We show that our greedy strategy has a performance guarantee of competitive ratio 1/(1+k) to the optimal offline solution, which improves the existing result for the same problem, where k is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRLs prediction error within a proven performance guarantee for any allocation sequence, enabling a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of joining machine-learning and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems.