Learning to Schedule DAG Tasks
This work addresses the scheduling problem for computational tasks in systems like databases, offering an incremental improvement by enhancing existing heuristic algorithms with a learning-based method.
The paper tackles the challenging problem of scheduling computational tasks represented by directed acyclic graphs (DAGs) by introducing a learning-based approach that uses reinforcement learning to iteratively add edges to the DAG, simplifying the problem and allowing heuristic algorithms to be improved, resulting in significant performance gains over popular heuristics on the TPC-H benchmark dataset.
Scheduling computational tasks represented by directed acyclic graphs (DAGs) is challenging because of its complexity. Conventional scheduling algorithms rely heavily on simple heuristics such as shortest job first (SJF) and critical path (CP), and are often lacking in scheduling quality. In this paper, we present a novel learning-based approach to scheduling DAG tasks. The algorithm employs a reinforcement learning agent to iteratively add directed edges to the DAG, one at a time, to enforce ordering (i.e., priorities of execution and resource allocation) of "tricky" job nodes. By doing so, the original DAG scheduling problem is dramatically reduced to a much simpler proxy problem, on which heuristic scheduling algorithms such as SJF and CP can be efficiently improved. Our approach can be easily applied to any existing heuristic scheduling algorithms. On the benchmark dataset of TPC-H, we show that our learning based approach can significantly improve over popular heuristic algorithms and consistently achieves the best performance among several methods under a variety of settings.