Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling
  In practice, it is quite common to face combinatorial optimization problems
which contain uncertainty along with non-determinism and dynamicity. These
three properties call for appropriate algorithms; reinforcement learning (RL)
is dealing with them in a very natural way. Today, despite some efforts, most
real-life combinatorial optimization problems remain out of the reach of
reinforcement learning algorithms.
  In this paper, we propose a reinforcement learning approach to solve a
realistic scheduling problem, and apply it to an algorithm commonly executed in
the high performance computing community, the Cholesky factorization. On the
contrary to static scheduling, where tasks are assigned to processors in a
predetermined ordering before the beginning of the parallel execution, our
method is dynamic: task allocations and their execution ordering are decided at
runtime, based on the system state and unexpected events, which allows much
more flexibility. To do so, our algorithm uses graph neural networks in
combination with an actor-critic algorithm (A2C) to build an adaptive
representation of the problem on the fly.
  We show that this approach is competitive with state-of-the-art heuristics
used in high-performance computing runtime systems. Moreover, our algorithm
does not require an explicit model of the environment, but we demonstrate that
extra knowledge can easily be incorporated and improves performance. We also
exhibit key properties provided by this RL approach, and study its transfer
abilities to other instances.
