[Paper] Schedule Preemption이 Dynamic Task Graph Scheduling에 미치는 영향 연구

Source: arXiv - 2602.03081v1

개요

이 논문은 동적 작업‑그래프 워크로드에 대한 스케줄 선점을 조사한다—상호 의존적인 작업 스트림을 실시간으로 컴퓨팅 자원 풀에 할당해야 하는 상황이다. 기존 할당을 고수하거나 모든 것을 지속적으로 재‑최적화하는 대신, 저자들은 중간 지점을 제안한다: 가장 최근의 작업만 재배열을 허용한다. 그들의 Last‑K Preemption 모델은 적당하고 제어된 선점이 전체 재스케줄링의 대부분 성능 이점을 얻으면서 공정성과 오버헤드를 관리할 수 있음을 보여준다.

주요 기여

• Last‑K Preemption 모델: 최근에 제출된 K개의 서브‑그래프에만 재스케줄링을 제한하는 새로운, 조정 가능한 정책.
• 포괄적인 실증 연구: 네 가지 워크로드 계열(합성, RIoTBench, WF‑Commons, 적대적)에서 세 가지 전략을 비교
  1. 비선점 (재배열 없음)
  2. 전체 선점 (매 라운드마다 모든 작업을 재스케줄)
  3. 부분 선점 (Last‑K)
• 다중 지표 평가: makespan, 공정성(작업당 지연 감소), 자원 활용도, 스케줄러 실행 시간 오버헤드.
• 설계 가이드라인: 워크로드 변동성 및 공정성 요구사항에 기반해 K 값을 선택하는 방법.
• 재현성을 위한 오픈‑소스 구현 및 벤치마크 스위트.

방법론

1. Task‑graph model – 각 들어오는 작업은 CPU/IO 요구사항과 선행 제약을 가진 작업들의 방향성 비순환 그래프(DAG)이다.
2. Scheduling rounds – 시스템은 주기적으로 모든 ready 작업을 수집하고, 휴리스틱(예: list‑scheduling)을 실행하여 고정된 동질 워커 집합에 매핑한다.
3. Preemption policies
   • Non‑preemptive: 작업이 배치되면 그 할당은 절대 변경되지 않는다.
   • Full preemptive: 각 라운드 전에 스케줄러가 이전 모든 배치를 버리고 새 스케줄을 다시 계산한다.
   • Last‑K: 가장 최근 K개의 DAG에 속한 작업만 재배치 대상이 되며, 오래된 할당은 고정된다.
4. Workload generators
   • Synthetic: 깊이/폭을 제어할 수 있는 매개변수화된 DAG.
   • RIoTBench: 현실적인 IoT 스트림 처리 그래프.
   • WF‑Commons: 과학 워크플로우 트레이스(예: Montage, Epigenomics).
   • Adversarial: 공정성을 압박하도록 설계된 워크로드(예: 많은 소규모, 지연 민감 DAG와 대규모 배치 작업이 혼합).
5. Metrics
   • Makespan (전체 경과 시간)
   • Fairness index (작업당 지연 감소에 대한 Jain의 공정성 지수)
   • Utilization (유용한 작업에 사용된 CPU 사이클 비율)
   • Scheduler overhead (스케줄링 알고리즘에 소요된 실제 시간)

모든 실험은 동일한 기본 휴리스틱을 사용하고 프리엠션 정책만을 달리하여 16노드 클러스터(각 노드 8코어)에서 수행된다.

Source: …

Results & Findings

핵심 요약

• 부분 선점은 완전 선점이 얻는 완성 시간 이득의 > 80 %를 확보하면서 공정성을 비선점 기준과 거의 동일하게 유지합니다.
• 오버헤드는 재배치를 위해 고려하는 작업 수에 거의 선형적으로 증가합니다; 마지막 K 개만 제한하면 스케줄링 시간이 크게 감소합니다.
• 워크로드 변동성이 중요합니다: 매우 동적인 스트림(RIoTBench)의 경우 K 를 크게(≈15 % 활성 DAG) 잡는 것이 최적의 트레이드‑오프를 제공하고, 안정적인 과학 워크플로우에서는 K = 5 %만으로도 충분합니다.
• 적대적인 작업 혼합은 완전 선점의 공정성 함정을 드러냅니다—작은 지연 민감 작업이 반복적으로 밀려나지만, Last‑K는 이전 할당을 “고정”함으로써 이를 보호합니다.

실용적 함의

• 클라우드‑네이티브 배치/스트림 처리 플랫폼(예: Apache Flink, Spark Structured Streaming)은 Last‑K 스타일의 “부분 재균형” 훅을 채택하여 짧은 수명의 작업에 대한 지연 보장을 희생하지 않으면서 처리량을 향상시킬 수 있다.
• 이기종 IoT 파이프라인을 실행하는 엣지‑컴퓨팅 오케스트레이터는 재배열 윈도우를 가장 최근의 센서 버스트로 제한함으로써 제한된 디바이스에서 CPU 활용도를 높일 수 있다.
• 스케줄러 설계자는 세 가지 경쟁 목표인 속도(전체 실행 시간), 공정성, 그리고 제어‑플레인 오버헤드를 균형 있게 맞추기 위한 구체적인 조정값(K)을 얻게 된다. 논문의 가이드라인은 관찰된 작업 도착 간격 패턴을 기반으로 K를 설정하는 데 도움을 준다.
• **지터에 페널티를 부과하는 서비스‑레벨 계약(SLA)**은 이점을 얻을 수 있다: 오래된 할당을 고정함으로써 시스템은 “작업 마이그레이션 폭풍”이 발생해 일시적인 자원 부족을 일으키는 위험을 감소시킨다.

Last‑K를 구현하는 것은 간단하다: 활성 DAG 식별자의 FIFO 큐를 유지하고, 새로운 스케줄링 라운드가 시작될 때 히어리스트릭에 사용할 작업은 큐의 꼬리에서만 추출한다; 나머지는 그대로 전달된다.

제한 사항 및 향후 연구

• 동질적인 자원: 실험은 동일한 작업자를 가정합니다; 이질적인 CPU/GPU 또는 메모리 제한 노드는 최적의 K에 영향을 줄 수 있습니다.
• 단일 휴리스틱: 연구는 고전적인 리스트‑스케줄링 휴리스틱을 사용합니다; Last‑K 제약 하에서 보다 정교한 솔버(ILP, 강화 학습)를 탐색하는 것은 향후 과제입니다.
• 정적 K: 논문은 워크로드당 고정된 K를 선택합니다; 관측된 변동성을 기반으로 런타임에 K를 조정하는 적응형 방안은 트레이드‑오프를 더욱 개선할 수 있습니다.
• 네트워크 인식 스케줄링: 데이터 전송 비용은 추상화되어 있습니다; 대역폭을 고려하면 공정성/활용도 균형이 바뀔 수 있습니다.

전반적으로, 이 연구는 동적 DAG 스케줄러를 위한 실용적인 중간 경로를 제시하며, 제어된 제한적 선점이 관리 가능한 복잡도로 거의 최적에 가까운 성능을 제공할 수 있음을 보여줍니다—이는 많은 프로덕션 시스템이 오늘부터 활용할 수 있는 통찰입니다.

저자

• Mohammadali Khodabandehlou
• Jared Coleman
• Niranjan Suri
• Bhaskar Krishnamachari

논문 정보

• arXiv ID: 2602.03081v1
• 분류: cs.DC
• 출판일: 2026년 2월 3일
• PDF: PDF 다운로드