이질적인 환경에서의 DAG 스케줄링을 위한 간격(Gap) 인지 생성 학습 방법

A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling

이질적인 환경에서 방향성 비순환 그래프(DAG)를 효율적으로 스케줄링하는 것은 자원 용량 및 의존성 때문에 어려운 과제입니다. 실제로, 다양한 자원 풀과 작업 유형을 가진 환경에 대한 적응성과 빠른 스케줄 생성 요구 사항은 이러한 어려움을 더욱 복잡하게 만듭니다. 본 논문에서는 이질적인 DAG 스케줄링을 위한 엔드-투-엔드 강화 학습 프레임워크인 WeCAN을 제안합니다. WeCAN은 작업-풀 호환성 계수와 생성으로 인한 최적성 간극 문제를 해결합니다. 이 프레임워크는 두 단계의 단일 패스(single-pass) 설계를 채택합니다. 단일 패스 과정에서 작업-풀 점수와 전역 파라미터를 생성하고, 이를 바탕으로 네트워크 호출을 반복하지 않고 스케줄을 구성하는 생성 맵을 사용합니다. 가중치 크로스-어텐션 인코더는 호환성 계수에 의해 제어되는 작업-풀 상호 작용을 모델링하며, 환경 변화에 크기 의존적이지 않습니다. 또한, 널리 사용되는 리스트 스케줄링 맵은 제한된 접근성으로 인해 생성으로 인한 최적성 간극을 발생시킬 수 있습니다. 본 논문에서는 실행 가능한 스케줄 순서를 통해 생성 맵의 도달 가능한 집합을 특성화하고, 생성으로 인한 간극의 메커니즘을 설명하며, 간극 제거를 위한 충분 조건을 제시하는 순서 공간 분석을 도입합니다. 이러한 조건에 따라, 분석적으로 파라미터화된 감소 규칙을 가진 확장된 스킵(skip) 구현을 설계하여, 도달 가능한 순서 집합을 확장하면서 단일 패스 효율성을 유지합니다. 계산 그래프 및 실제 TPC-H DAG에 대한 실험 결과, 제안하는 방법이 강력한 기준 모델보다 향상된 최단 실행 시간을 달성했으며, 추론 시간은 기존 휴리스틱과 유사하고, 다중 라운드 신경망 스케줄러보다 빠릅니다.

Efficient scheduling of directed acyclic graphs (DAGs) in heterogeneous environments is challenging due to resource capacities and dependencies. In practice, the need for adaptability across environments with varying resource pools and task types, alongside rapid schedule generation, complicates these challenges. 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 computation graphs and real-world TPC-H DAGs demonstrate improved makespan over strong baselines, with inference time comparable to classical heuristics and faster than multi-round neural schedulers.