TL;DR
This paper introduces DeepWeave, a novel framework that uses Deep Reinforcement Learning (DRL) and Graph Neural Networks (GNNs) to automatically generate coflow scheduling policies for distributed computing jobs. By learning from historical workload traces, DeepWeave significantly reduces job completion times, outperforming state-of-the-art methods by at least 1.7x.
What Problem Does This Paper Address?
In modern distributed computing systems like those used for big data processing (e.g., Spark, MapReduce), jobs are often modeled as Directed Acyclic Graphs (DAGs). These DAGs consist of computation stages and communication stages. The communication stages involve "coflows," which are collections of correlated network flows that must be transmitted between machines. The transmission of these coflows can consume a substantial portion (over 50%) of a job's total execution time. Efficiently scheduling these coflows is crucial for minimizing the overall job completion time (JCT). However, coflow scheduling is an NP-hard problem, and existing solutions often rely on hand-crafted heuristics that simplify the problem, leading to suboptimal performance. Furthermore, many existing approaches focus on scheduling within a single communication stage and fail to consider the inter-stage dependencies within a job DAG, limiting their effectiveness for complex, multi-stage jobs.
Methods
DeepWeave tackles this challenge by employing a Deep Reinforcement Learning (DRL) framework. The core idea is to train an agent to learn an optimal coflow scheduling policy without requiring explicit human expertise or pre-defined models.
Here's a breakdown of the key components:
- Graph Neural Network (GNN): To effectively process the complex, graph-like structure of job DAGs, DeepWeave utilizes a GNN. This allows the model to generalize well to DAGs of varying sizes and shapes by capturing the relationships between computation and communication stages. The GNN learns node attributes and job-level summaries by passing messages between nodes, effectively encoding the DAG's structure and dependencies.
- Policy Network: The output from the GNN is fed into a Policy Network, which is a feedforward neural network. This network generates a priority list for the coflows (represented as edges in the DAG). A higher priority value indicates that a coflow should be scheduled sooner.
- Policy Converter: This module translates the priority list generated by the Policy Network into concrete coflow scheduling actions. It prioritizes coflows based on their assigned priorities and then schedules individual flows within those coflows, aiming to minimize their completion times.
- DRL Framework: The entire system is trained using a DRL approach. The agent interacts with a simulator, observing the state (job DAG and status), taking an action (scheduling a coflow), and receiving a reward (negative of the job completion time). This reward signal guides the agent to learn a policy that minimizes JCT. The paper mentions using a policy gradient method with a baseline to stabilize training.
Datasets
The paper uses the following for evaluation:
- TPC-DS: This benchmark is used to generate job DAGs with varying shapes and critical path lengths. The authors use Shark to generate queries and then model these as DAGs.
- Facebook trace: Mentioned as a source used by previous works for training and testing, but noted as being composed of single-stage jobs, lacking the multi-stage coflow correlations that DeepWeave aims to address.
Key Insights and Ideas
- Learning to Schedule is Powerful: The paper demonstrates that a DRL agent can learn effective coflow scheduling policies from data, bypassing the need for complex, hand-engineered heuristics. This opens up new avenues for optimizing network resource allocation.
- GNNs are Crucial for DAGs: The use of GNNs is highlighted as a key enabler for DeepWeave's success. Their ability to process graph-structured data allows the model to understand the intricate dependencies within job DAGs, which is essential for effective coflow scheduling across multiple stages.
- Inter-coflow Dependencies Matter: By considering the entire job DAG, DeepWeave can make more informed scheduling decisions that account for how coflows in different stages interact, leading to significant JCT reductions compared to methods that only optimize individual communication stages.
- Generalization is Achieved: The GNN-based approach allows DeepWeave to generalize well to different DAG sizes and shapes after training, making it robust in real-world scenarios where job structures can vary.
Key Results
- Significant JCT Reduction: DeepWeave consistently outperforms state-of-the-art coflow scheduling schemes, achieving job completion times at least 1.7x faster than the best comparison methods.
- Performance Degradation of Baselines: Existing methods like Approximate and IAOA show significant performance degradation as the DAG length increases, primarily because they fail to fully account for coflow correlations across different stages.
- Low Deadline Missing Rate: DeepWeave also exhibits the lowest deadline missing rate, indicating its reliability in meeting job completion deadlines.
Limitations and Future Work
- Neural Network Architecture Tuning: The paper notes that the performance is sensitive to the neural network architecture. While they found a good balance with a 2-layer Policy Network and GNNs with specific hidden layer configurations, further exploration of optimal architectures could yield even better results.
- Real-world Deployment: The current evaluation is based on simulations. Future work could focus on deploying and evaluating DeepWeave in real-world distributed computing environments to validate its performance under actual network conditions.
- Enriching the System: The authors express a desire to "enrich our work to achieve a more powerful coflow scheduling system on real applications," suggesting ongoing efforts to enhance the system's capabilities and applicability.
Summary updated