ODGS: Dependency-Aware Scheduling for High-Level Synthesis with Graph Neural Network and Reinforcement Learning

Scheduling determines the execution order and time of operations in a program. The order is related to operation dependencies, including data and resource dependencies. Data dependency is intrinsic in a program, showing operation data flow. Resource dependency is determined by scheduling methods, resolving operation resource contention. Existing scheduling methods focus on data dependency, rather than building and exploiting operation dependency graph (ODG) with extra resource dependency. As ODG contains all dependencies determining operation execution order, it provides global program information, facilitating efficient scheduling. In this work, we propose ODGS, a dependency-aware scheduling method for high-level synthesis with graph neural network (GNN) and reinforcement learning (RL). We adopt GNN to perceive accurate relations between operations. We use the relations to guide an RL agent in building a complete ODG. We perform feedback-guided iterative scheduling with ODG to converge to a high-quality solution. Experiments show that our method reduces 16.4% latency and 26.5% resource usage on average, compared with the latest RL-based method. Moreover, we reduce an average 2.9% latency over the GNN-based method under the same resource usage. The same resource usage is obtained by improving the GNN-based method with manual resource constraint tuning. Without tuning, its basic version consumes an average 237.6% more resources than our method.