Learning scheduling algorithms for data processing clusters

By Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, Mohammad Alizadeh. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2018

812 citations recorded by the source corpus.

Efficiently scheduling data processing jobs on distributed compute clusters requires complex algorithms. Current systems 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. However, off-the-shelf RL techniques 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 average job completion time by at least 21% over hand-tuned scheduling heuristics, achieving up to 2x improvement during periods of high cluster load.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/ac91892a8a6b6c3e97aa92b6fa8d54b42cade0ee

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Bao: Making Learned Query Optimization Practical (2020, background): “A few selected works outside the context of data management systems include reinforcement learning for job scheduling [37], automatic performance analysis [9], loop vectorization [20] and garbage collection [23].”
Domain-specific Genetic Algorithm for Multi-tenant DNNAccelerator Scheduling (2021, methodology): “Some works leverage RL for jobs ordering over clusters such as DeepRM [66], Decima [67] and Thamsen et al. [109].”
Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning (2020, methodology): “Similar to [26], a RL method combined with GNNs is proposed to accelerating computation in distributed system [27].”
Deep reinforcement learning: a survey (2020, methodology): “Motivated by prior applications, a scalable RL model with the graph embedding technique (Mao et al., 2019a) is trained by the PG algorithm to deal with the issue of continuous stochastic job arrivals.”
Neo: A Learned Query Optimizer (2019, background): “Decima [32] proposed a reinforcement learning-based scheduler, which processes query plans via a graph neural network to learn workload-specific scheduling policies that minimize query latency.”
Benchmarking Graph Neural Networks (2023, background): “[56] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh.”