Timezone: »

Neural DAG Scheduling via One-Shot Priority Sampling
Wonseok Jeon · Mukul Gagrani · Burak Bartan · Weiliang Zeng · Harris Teague · Piero Zappi · Christopher Lott
Event URL: https://openreview.net/forum?id=AzRMQCt9zy »

We consider the problem of scheduling operations/nodes, the dependency among which is characterized by a Directed Acyclic Graph (DAG). Due to its NP-hard nature, heuristic algorithms were traditionally used to acquire reasonably good solutions, and more recent works have proposed Machine Learning (ML) heuristics that can generalize to unseen graphs and outperform the non-ML heuristics. However, it is computationally costly to generate solutions using existing ML schedulers since they adopt the episodic reinforcement learning framework that necessitates multi-round neural network processing. We propose a novel ML scheduler that uses a one-shot neural network encoder to sample node priorities which are converted by list scheduling to the final schedules. Since the one-shot encoder can efficiently sample the priorities in parallel, our algorithm runs significantly faster than existing ML baselines and has comparable run time with the fast traditional heuristics. We empirically show that our algorithm generates better schedules than both non-neural and neural baselines across various real-world and synthetic scheduling tasks.

Author Information

Wonseok Jeon (Qualcomm AI Research)
Mukul Gagrani (QualComm)
Burak Bartan (Stanford University)
Weiliang Zeng (QualComm)
Harris Teague (Qualcomm)
Piero Zappi (Qualcomm Tech. Inc.)

Piero Zappi is a Sr. Staff research Engineer at Qualcomm. His current work focus on applying ML to combinatorial optimization problems.

Christopher Lott (Qualcomm AI Research)

More from the Same Authors