Learning Scheduling Algorithms for Data Processing Clusters

Abstract

Efficiently scheduling data processing jobs on distributed compute clusters requires complex algorithms. Current systems, however, use simple generalized heuristics and ignore workload characteristics, since developing and tuning a scheduling policy for each workload is infeasible. In this paper, we show that modern machine learning techniques can generate highly-efficient policies automatically. Decima uses reinforcement learning (RL) and neural networks to learn workload-specific scheduling algorithms without any human instruction beyond a high-level objective such as minimizing average job completion time. Off-the-shelf RL techniques, however, cannot handle the complexity and scale of the scheduling problem. To build Decima, we had to develop new representations for jobs' dependency graphs, design scalable RL models, and invent RL training methods for dealing with continuous stochastic job arrivals. Our prototype integration with Spark on a 25-node cluster shows that Decima improves the average job completion time over hand-tuned scheduling heuristics by at least 21%, achieving up to 2x improvement during periods of high cluster load.

References in corpus (16)

• Continuous control with deep reinforcement learning
• Semi-Supervised Classification with Graph Convolutional Networks
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Trust Region Policy Optimization
• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
• Deep Reinforcement Learning for Multi-Agent Systems: A Review of Challenges, Solutions and Applications
• Learning Combinatorial Optimization Algorithms over Graphs
• RL${}^2$: Fast Reinforcement Learning via Slow Reinforcement Learning
• Robust Adversarial Reinforcement Learning
• Neo: A Learned Query Optimizer
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Device Placement Optimization with Reinforcement Learning
• The Optimal Reward Baseline for Gradient-Based Reinforcement Learning
• Model-Based Reinforcement Learning via Meta-Policy Optimization
• Variance Reduction for Reinforcement Learning in Input-Driven Environments
• Real-world Video Adaptation with Reinforcement Learning

Cited by in corpus (7)

• Neo: A Learned Query Optimizer
• Bao: Learning to Steer Query Optimizers
• Placeto: Learning Generalizable Device Placement Algorithms for Distributed Machine Learning
• Deep Reinforcement Agent for Scheduling in HPC
• RLScheduler: An Automated HPC Batch Job Scheduler Using Reinforcement Learning
• Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning
• Data Centers Job Scheduling with Deep Reinforcement Learning