Tiresias: A GPU Cluster Manager for Distributed Deep Learning

[gaocegege]

https://www.usenix.org/system/files/nsdi19-gu.pdf

开源 simulation https://github.com/SymbioticLab/Tiresias

[gaocegege]

用到了一种叫做两维调度的策略，基于零知识的调度，没有太看懂，回头再看看

[gaocegege]

这是一篇做调度的论文，其调度的目标是：

• 最小化任务的完成时间
• 提高 GPU 的利用率
• 任务不应被 Head-of-lines 等问题导致出现 Starvation

作者基于 Microsoft 的生产集群的 Trace 数据，得到了这么几个观察：

• 任务的运行时间，是不可预测的
• GPU 训练的抢占成本是很高的，CV 领域的模型，在保存 checkpoint 的时候，会引入从 1 秒到 27 秒不等的时间上的 overhead
• 单纯的考虑 PS-Worker 的亲和性的 Gang Scheduling 会造成排队的高延迟，而且对于某些任务来说，这样的优化并不会显著加快训练速度。这个优化指的是尽量把 PS 和 Worker 调度到同一台机器上，并不能对所有的训练都有帮助，它只对部分任务有帮助

对于第一个问题，是显而易见的。如 #86 采取了对运行时间的预测的方式来指导调度，在生产环境来看就不是特别容易落地。第二个问题，也显而易见。

第三点，可以参考下图

图中左侧是随机调度，右边是亲和调度。可以看到，对于 ResNet 等模型，其实亲和性并不能带来太多收益。这个跟 Tensor 的尺寸分布有关。

可以看到，VGG 等受到亲和性影响较大的模型，都是有超大的 Tensor 的，而且大的 Tensor 占比很高。

[gaocegege]

基于这些观察，这篇论文提出了两个调度方法，分别用于不同场景。这个结合的算法被称为 2DAS

当没有任何知识的情况下，2DAS 会用 Least Attained Service 算法。而 Attained Service 会根据任务申请的 GPU，和已经运行的时间来计算。Attained Service 越多，优先级越低。如果是知道任务时间的分布的（通过历史任务或者其他方式），就用另外一种算法 Gittins index 计算优先级，伪代码如图，index 越高代表优先级越高

LAS 算法喜欢那些运行时间短，需要的资源少的任务。Gittins index 是任务在下一个 quantum 下完成训练的概率。概率越高优先级越高。

LAS 算法可见参考文献 [1]，Gittins index 算法可见参考文献 [2]

[1]: Nuyens, Misja, and Adam Wierman. "The foreground–background queue: a survey." Performance evaluation 65.3-4 (2008): 286-307. [2]: Gittins, John, Kevin Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.

[gaocegege]

可以看到，LAS 和 Gittins index 都是连续的算法，而连续的算法会造成抢占非常频繁。论文作者为了解决这个问题，将优先级离散化，然后应用了 Multi-Level Feedback Queue（多级反馈队列调度算法，MLFQ）。MLFQ 是一个 CPU 进程调度里的一个算法，原理很简单，这里不多介绍。

在真正调度的时候，是采取了如下所示的算法

前面提到，不是所有的模型训练，都可以从 PS Worker 亲和性调度的优化中受益。因此在调度的时候，2DAS 引入了一个 profiling 的过程，会进行一些小迭代的训练。然后利用一个 tensor size 和 tensor 到 ps 的 mapping 情况的函数，判断这个模型训练是否能够受益。这一 profiling，是用 RDMA 的 interception 完成的。

Profiling 的时候，会拦截 RDMA 调用（ibverbs 等），从 RDMA 通信中分析得到数据，然后利用函数计算出受益情况。开源代码里有说这部分会开源，但现在还没有。而且理论上，这一套也可以作用在 TCP/IP 栈上，但是需要重新写一个 monitoring 的工具

[gaocegege]

在未来工作中，作者提到了这一调度算法需要更好的形式化分析，来证明它的正确性。另外就是应该支持更加轻量级的抢占，Gandiva 中有一个方案，但是对用户代码（DL Framework）有侵入性。按照我的理解，跟 ElasticDL 的目标比较类似，支持容错和弹性调度，这样就不需要真正的抢占，只需要 scale down 释放一部分资源出来。

最后就是更加细粒度的调度，现在 2DAS 只是对网络做了 profiling，但 PS 和 Worker 在一台机器上的时候，PCIe 等级别上的互相干扰等问题都需要考虑。这就需要拓扑感知。