提出新方法WeCAN,解决异构资源下任务调度的兼容性与生成误差问题。
A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling
- 两阶段单次遍历生成调度,通过权重交叉注意力建模任务-资源兼容性。
- 在真实TPC-H和机器学习图上使完成时间更短,推理速度接近传统启发式方法。
- 揭示生成调度的可达顺序局限,设计可解析控制的跳过规则扩大可行解集。
高效调度有向无环图(DAG)是大规模数据密集型计算系统的核心问题,其中查询计划、数据处理负载和计算图由依赖任务构成,争夺有限的异构资源池。实际中,高性能执行要求调度器能适应不同资源组合与任务类型,并在严格运行时预算内生成调度。本文提出WeCAN,一种端到端强化学习框架,用于异构DAG调度,解决了任务-资源兼容性系数与生成导致的最优性差距问题。其采用两阶段单次遍历设计:一次前向传播生成任务-资源评分与全局参数,随后通过生成映射构建调度,无需重复网络调用。其加权交叉注意力编码器通过兼容性系数门控建模任务-资源交互,且对环境波动具有尺寸无关性。此外,常用列表调度映射可能因可达性受限而引入生成性最优性差距。本文引入顺序空间分析,通过可行调度顺序刻画生成映射的可达集,解释生成性差距机制,并给出消除间隙的充分条件。基于此,设计了一种带有解析参数化递减跳过规则的跳过扩展实现,在保持单次遍历效率的同时扩大可达顺序集。在真实世界TPC-H查询DAG、资源密集型工作负载数据集及机器学习编译器计算图上的实验表明,WeCAN在完成时间上优于强基线,推理时间与经典启发式相当,且快于多轮神经调度器。
原文摘要 · Abstract (English)
Efficient scheduling of directed acyclic graphs (DAGs) is a core problem in large-scale data-intensive computing systems, where query plans, data-processing workloads, and computation graphs consist of dependent tasks competing for limited heterogeneous resource pools. In practice, achieving high-performance execution requires schedulers to adapt across environments with varying resource pools and task types, while generating schedules under tight runtime budgets. We propose WeCAN, an end-to-end reinforcement learning framework for heterogeneous DAG scheduling that addresses task-pool compatibility coefficients and generation-induced optimality gaps. It adopts a two-stage single-pass design: a single forward pass produces task-pool scores and global parameters, followed by a generation map that constructs schedules without repeated network calls. Its weighted cross-attention encoder models task-pool interactions gated by compatibility coefficients, and is size-agnostic to environment fluctuations. Moreover, widely used list-scheduling maps can incur generation-induced optimality gaps from restricted reachability. We introduce an order-space analysis that characterizes the reachable set of generation maps via feasible schedule orders, explains the mechanism behind generation-induced gaps, and yields sufficient conditions for gap elimination. Guided by these conditions, we design a skip-extended realization with an analytically parameterized decreasing skip rule, which enlarges the reachable order set while preserving single-pass efficiency. Experiments on real-world TPC-H query DAGs, resource-intensive workload datasets, and ML-compiler computation graphs demonstrate improved makespan over strong baselines, with inference time comparable to classical heuristics and faster than multi-round neural schedulers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。