GPU Cluster Scheduling

集群调度

Survey

• Deep Learning Workload Scheduling in GPU Datacenters: Taxonomy, Challenges and Vision (ArXiv’22) [PDF][Awesome list]

集群数据分析

• Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads (ATC’19) [PDF] [Dataset] [阅读笔记]
  • 微软Philly集群衍生出的一系列工作之一，分析了多租户GPU集群中的workload的特点，可以为各类工作提供motivation

• MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters (NSDI’22) [PDF] [Dataset]

GPU集群调度

• Gandiva: Introspective Cluster Scheduling for Deep Learning (OSDI’18) [PDF]
  • 微软的调度器，可以通过job migration, time slicing, grown-shrink, packing等方式充分利用集群资源并减少fragmentation

• Optimus: An Efficient Dynamic Resource Scheduler for Deep Learning Clusters

• Tiresias: A GPU Cluster Manager for Distributed Deep Learning (NSDI’19) [阅读笔记(outer link)] [PDF] [Code]
  • 密歇根大学与微软、阿里巴巴、UNIST、字节跳动合作的开源GPU集群调度器
  • Discretized-2DAS（age-based）scheduler: 无需对DL任务全面的信息就可以减小JCT；model profile placement：无需来自用户的额外信息就可以把任务放在合适的位置，提高集群资源利用率且不会影响模型的performance；可以在避免starvation和最小化平均JCT上寻找trade off

• DL2: A Deep Learning-driven Scheduler for Deep Learning Clusters (ArXiv’19) [PDF]
  • 香港大学与阿里巴巴合作的工作，运用了强化学习，可以实现动态worker/parameter server调整，可以实现弹性训练

• Balancing Efficiency and Fairness in Heterogeneous GPU Clusters for Deep Learning (EuroSys’20) [阅读笔记] [PDF]
  • 微软印度的工作，异构设备的调度，可以为一个训练任务分配异构的GPU

• Themis: Fair and Efficient GPU Cluster Scheduling (NSDI’20) [PDF]
  • 威斯康星大学和微软合作的GPU调度器
  • 应用场景为一个DL app包含多个深度学习模型调参的job，提出了Finish-time fairness这样的一个新的metric

• Salus: Fine-Grained GPU Sharing Primitives for Deep Learning Applications

• Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads (OSDI’20) [PDF] [Code]
  • 微软和斯坦福合作，实现了调度器Gavel，在资源调度的时候考虑到了不同任务在不同GPU设备上的实际效率，异构是针对cluster而言的，在一个任务里不能有不同型号的GPU

• PipeSwitch: Fast Pipelined Context Switching for Deep Learning Applications (OSDI’20) [阅读笔记] [PDF] [Code]
  • 通过训练和上下文切换的pipeline式overlap，来达到高效的上下文切换

• HiveD: Sharing a GPU Cluster for Deep Learning with Guarantees (OSDI’20) [阅读笔记] [PDF] [Code]
  • MSRA与北京大学合作，抽象集群中的GPU资源，保证“共享安全”

• AntMan: Dynamic Scaling on GPU Clusters for Deep Learning (OSDI’20) [阅读笔记)] [PDF] [Code]
  • GPU集群中内存和op的细粒度调度，可以提升集群的利用率

• Job Scheduling for Large-Scale Machine Learning Clusters (CoNEXT’20) [PDF]
  • 弗吉尼亚大学的工作，实现了调度器MLFS，设计了对于数据并行、模型并行、以及混合情况下都适用的调度，并采用了强化学习的方法学习调度策略

• Optimizing Distributed Training Deployment in Heterogeneous GPU Clusters (CoNEXT’20) [PDF]
  • 香港大学和阿里巴巴的合作，实现了调度模块HeteroG
  • 一个任务中可能包含多种异构的GPU，通过强化学习的方法学习parallelism的最佳策略

• Elan: Towards Generic and Efficient Elastic Training for Deep Learning (ICDCS’20 Best Paper Honorable Mention Award) [阅读笔记] [PDF]
  • 清华大学与商汤合作的工作，实现了一个面向深度学习负载的弹性调度系统，可以提高运行深度学习负载的数据中心资源利用率

• Elastic Resource Sharing for Distributed Deep Learning (NDSI’21) [阅读笔记] [PDF]
  • KAIST的工作，提出了算法AFS，设计了一个需要elastic DL的调度算法，并实现了高效调度的系统CoDDL（基于OSDI’18的一篇poster）

• Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning (OSDI’21) [PDF] [Code]
  • Petuum磐腾科技提出的GPU集群调度方法
  • 可以在训练时动态调整资源数量，为深度学习训练的不同阶段找到合适的batch size，从而使得训练效率和训练的准确率都能够得到保障
  • 没有考虑到模型并行，且为了不同任务之间不互相影响，需要满足一个节点上不能有两个不同的任务，这样需要集群中资源非常充足。现实中可能会有很多集群不能满足这样的需求

• Chronus: A Novel Deadline-aware Scheduler for Deep Learning Training Jobs (SoCC’21) [PDF]
  • 针对DL训练任务的SLO进行调度，将任务分为SLO jobs和Best-Effort jobs两类

• Looking Beyond GPUs for DNN Scheduling on Multi-Tenant Clusters (OSDI’22) [PDF]
  • 这篇文章来自Microsoft Research。该工作提供了一种面向多租户集群的DNN任务调度器，在传统调度器的基础上将任务对CPU及内存资源分配的敏感度纳入考虑，从而更好地分配和利用现有的集群资源，提高平均任务完成时间。

• Lucid: A Non-intrusive, Scalable and Interpretable Scheduler for Deep Learning Training Jobs (ASPLOS’23) [PDF]
  • 解决现有的深度学习作业调度器存在可扩展性有限、决策过程不透明等等问题

• ElasticFlow (ASPLOS’23)

• Sia (SOSP’23)

传统集群调度

• Doninant Resource Fairness: Fair Allocation of Multiple Resource Types (NSDI’11) [PDF]
  • 伯克利提出的Dominant Resoruce Fairness(DRF)算法，多资源分配的max-min fariness

• Improving Service Level Agreements for a Job Scheduler by Visualizing Simulations (MIT thesis) [PDF]
  • “by deadline” SLA

• Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing (OSDI’14) [PDF]
  • 微软提出的在集群中处理大量数据处理的产业级别调度框架
  • 每个数据处理job可以用task组成的DAG来表示；每个job有单独的sheduler，用于调度每个job内部的的task

• HUG: Multi-Resource Fairness for Correlated and Elastic Demands (NSDI’16) [PDF]
  • 将传统的maxmin fairness推广到需求相关的多资源环境，将DRF推广到弹性需求

• Altruistic Scheduling in Multi-Resource Clusters (OSDI’16)[PDF]

• Scheduling Mix-flows in Commodity Datacenters with Karuna (SIGCOMM’16) [PDF]
  • 尽量保证有deadline的网络流的deadline，同时优化没有deadline的网络流的flow completion time

• Swayam: Distributed Autoscaling to Meet SLAs of Machine Learning Inference Services with Resource Efficiency (Middleware’17) [PDF]
  • Meet SLA for inference jobs

• Providing SLOs for Resource-Harvesting VMs in Cloud Platforms (OSDI’20) [PDF]
  • 传统的云计算调度，不同的是，本文考虑了SLO（65% of the Harvest VMs will survive more than a week）
    https://www2.seas.gwu.edu/~tlan/papers/NFS_INFOCOM_2015.pdf
    https://iqua.ece.toronto.edu/papers/lchen-infocom16.pdf