Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling
This addresses the challenge of efficient and deterministic scheduling for combinatorial optimization, specifically in edge computing, though it is incremental as it combines existing RL and ILP methods.
The paper tackles the NP-hard scheduling problem on dataflow graphs by introducing a two-phase RL-to-ILP framework, achieving up to 128× speed improvements while matching the performance of exact methods and improving on-chip inference runtime compared to a commercial compiler.
Scheduling on dataflow graphs (also known as computation graphs) is an NP-hard problem. The traditional exact methods are limited by runtime complexity, while reinforcement learning (RL) and heuristic-based approaches struggle with determinism and solution quality. This research aims to develop an innovative approach that employs machine learning (ML) for addressing combinatorial optimization problems, using scheduling as a case study. The goal is to provide guarantees in optimality and determinism while maintaining the runtime cost of heuristic methods. Specifically, we introduce a novel two-phase RL-to-ILP scheduling framework, which includes three steps: 1) RL solver acts as coarse-grain scheduler, 2) solution relaxation and 3) exact solving via ILP. Our framework demonstrates the same scheduling performance compared with using exact scheduling methods while achieving up to 128 $\times$ speed improvements. This was conducted on actual EdgeTPU platforms, utilizing ImageNet DNN computation graphs as input. Additionally, the framework offers improved on-chip inference runtime and acceleration compared to the commercially available EdgeTPU compiler.