来自论文Tiresias:A GPU Cluster Manager for Distributed Deep Learning
概述
给一个庞大的GPU集群，在实际的应用中，现有的大数据调度器会导致长队列延迟和低的性能，该文章提出了Tiresias，即一个GPU集群的调度器，专门适应分布式深度学习任务，该调度器能够有效率的调度并且合适地放置深度学习任务以减少他们的任务完成时间（JCT(Job Completion Time)），一个深度学习任务执行的时间通常是不可预知的，该文章提出两种调度算法，基于局部信息的离散化二维Gittins索引(Discretized Two Dimensional Gittins index)以及离散化二维LAS，对信息不可知并且能够降低平均的JCT，在实验中JCT能够快5.5倍，相比于基于Apache YARN的资源管理
介绍
许多平台提供方建立了GPU集群，共享给用户来满足日益增长的深度学习任务数量，根据Microsoft的跟踪分析，至2016年深度学习任务数量每年增长10.5倍，高效的任务调度和智能的GPU分配是减少集群平均JCT并且最大化GPU利用率的关键因素.
通过观察，得知现有的集群管理设计的两个主要限制:
1. 由于训练时间不可预知的朴素调度
虽然最短优先(SJF)和最短保持时间优先(SRTF)可以被用于减少JCT，但是这两个算法都需要任务的执行时间，而深度学习任务的执行时间通常是未知的，通常我们训练到误差收敛为止。
我们可以做一个简单的假设，即任务有平滑的误差曲线，运行直到完成，在实际生产系统中可能并非如此。
目前内部的解决方案继承于Apache YARN的容量调度器，该调度器是为大数据任务构建的，它只执行基本的策略，例如非抢占的调度策略，结果是用户会遭受长队列延迟，甚至对于很小的任务都要等待数个小时。
2. 在任务布置方面过于激进的合并
现有集群管理器还尝试将DDL任务合并到具有足够GPU的最小数量的服务器上，举个例子，一个需要16个GPU的任务在每个服务器都是4个GPU的集群中需要至少4个服务器，如果不能完全满足则会被阻塞，在此之下的假设是网络要尽量避免变成瓶颈或者浪费GPU周期
该文章提出了Tiresias，一个共享的GPU管理器，解决了上述的问题，即调度和放置的问题。为了保重Tiresias是实际可用的以及容易被部署，基于对生产任务的跟踪的分析，训练细节的度量以及两个简单但有效的想法。除此之外，有意地让Tiresias对用户透明。
第一个想法
第一个想法是一个新的调度框架2DAS，可以当任务的执行时间不确定时减少JCT，在此框架下提出了两种调度算法：
- Discretized 2D-LAS
- Discretized 2D Gittins index
Gittins索引策略是单服务器场景下用于优化JCT的策略，其中JCT的分布是已知的。
同样的，传统的LAS((Least-Attained Service)算法也是被广泛用于任务时间不可预知的场景下，例如数据中心的网络调度。
上述两个方案都是给任务一个优先级，前者使用Gittins索引，后者直接应用收到的任务(随着时间会改变，任务会按照优先级来进行调度)
使用上述策略到DDL调度问题会面对两个挑战：
- 当计算任务优先级的时候，我们需要同时考虑空间(GPU的个数)以及时间(多久)两个维度
- 由于优先级会持续发生变化，任务会持续地被抢占，虽然当开始和停止一个流是简单的情况下，网络是可以容忍的，但抢占一个任务是花费较大的，我们需要将数据和模型从内存和GPU那复制回去。为了防止侵略性的任务抢占，应用优先级离散化于两个上述算法，即一个任务的优先级只能改变固定的值
综上所述，有先验的任务执行时间的分布的情况下选用基于Gittins索引的算法，如果没有先验知识的话则选用LAS算法
第二个想法
第二个想法是使用模型结构来尽可能地松弛化合并放置的约束，我们发现只有某些确定类型的DL模型是对是否合并是敏感的，敏感度是由于其张量大小分布的偏差。我们利用这种直觉将任务分成两类：
- 对于合并敏感(高度偏差)
- 其他
我们实现了一个RDMA网络分析库，能够通过网络级别的活动判别分布式深度学习任务的模型结构，通过利用这个库Tiresias就可以智能地放置任务。
Tiresias首先在一个测试环境运行任务几个迭代，然后根据之前度量的总结标准以确定最好的放置策略。
贡献
- Tiresias是第一个对于信息不可知的GPU资源管理，也是第一个考虑了两个维度(时间和空间)以及优先级离散化的调度
- Tiresias使用一个简单的，外部可观察的，模型特殊的标准来判别什么时候放松worker的GPU合并的约束
- 该设计有实用性和易部署性，并且性能显著提高
背景和动机
分布式机器学习(DDL)
这里，我们关注数据的并行化，数据的并行化是目前流行的分布式深度学习框架的公共部分。
如上图所示，每一个Worker有一个GPU，运行本地的深度学习模型副本，训练集被划分成等大小的部分分配给Worker们，所有的任务同步训练，一个被观察到的事实是这样的架构能够更快的收敛，相比于异步的分布式训练。
固定时间的迭代
深度学习训练是按迭代的方式工作的，在每一个轮次，worker要做一次前向和反向的计算，接着worker将本地的结果互相更新深度学习模型，称之为模型聚集(Model Aggregation)，由于每一个迭代的计算时间都是差不多的，故迭代的时间是高度可预测的。
参数服务器架构
参数服务器，简称PS(Parameter Server)，这种架构是最流行的模型聚集的方法，参数服务器掌握主要的深度学习模型副本，使用从所有worker那里得到的本地结果来更新模型，然后worker在每个迭代的一开始拉回参数来更新本地的模型，一个深度学习任务可以有多个参数服务器。
测试和错误的探索
为了得到一个高质量的模型，需要对超参数的各种组合进行探索，称为超参数调优(hyperparameter-tuning)，用户可以用AutoML等搜索工具来进行高效的探索。在AutoML中，许多带着不同超参数设置的深度学习任务被生成来训练相同的任务，其中的大多数由于随机的误差或者低质量的提升会被消除。利用一开始测试阶段的反馈，AutoML能够搜索新的参数配置以及产生大量新的任务，当然其中只有少数拥有较高的质量。
挑战
该文章主要针对分布式深度学习集群管理面临的主要挑战，这些挑战来自于分布式深度学习训练的特性，并且并不特别针对Microsoft集群
不可预测的作业时间
现有的解决方案用于预测深度学习任务训练时间都假设：
- 拥有平滑的误差曲线
- 到达他们的训练目标并结束
然而，很多较弱的模型在训练错误的探索阶段，它们的误差曲线不像最好的模型那么平滑。
深度学习任务什么时候停止亦是不确定的。
通常来说，用户会定义最大的迭代轮数以应对当模型到达不了预期的误差的情况，即便如此，一个有效的资源管理设计也是不能依赖于误差曲线进而预测任务的结束时间的。
过度侵略性的任务合并
在模型聚集阶段尝试减少网络的通信在分布式训练中是一种通用的优化，因为网络可能是性能瓶颈并且浪费GPU周期。
然而，许多现存的GPU管理在放置分布式深度学习任务时盲目地遵从一个合并约束，特别地，他们将作业的所有组件（参数服务器和Worker）分配给相同或最小数量的服务器
一个分布式深度学习作业如果不能合并通常会等待，即使集群中有足够的空闲资源，虽然这个约束是为了高性能，但是会导致更长的队列延迟和低的资源利用。
为了理解这个约束的重要性，我们运行4个8GPU并发的任务，使用不同的放置策略(随机，经常性的合并)，在8个4GPU服务器集群上，每个任务使用8个参数服务器(和Worker数目一致)。
上述性能都以合并策略作为基准进行标准化。Worker的位置主要影响了VGG系列和AlexNet。然而集群的操作者和用户都不能告诉一个任务究竟属于哪个类别。
抢占的时间开销
现有的生产集群不能抢占，由于大量的时间开销。 为了表现这个问题，我们人工测试了在本地停止和重启一个分布式机器学习任务。在停止阶段，主要的Worker会记录当前的模型到共享的内存，该记录的文件当重启的时候会被载入。
潜在的收益
我们可以通过减轻两个方面来获得巨大的收益
1. 任务如果没有确切的持续时间，就不能被很好地调度
我们可以通过日志学习到时间的分布，进而使用Gittins索引策略，该策略广泛用于传统的多臂老虎机问题，进而降低平均的JCT。即使没有时间的分布，我们可以使用LAS算法。
2. 分布式深度学习任务应该被经常合并
虽然合并任务的位置可以最大程度减小通信的时间，但是我们发现有的分布式深度学习任务对于位置是敏感的
将智能的放置策略和调度策略结合，可以将平均JCT提高至少5倍
Tiresias的设计
主要是两个模块的设计，一个是调度器，一个是放置管理，以及用于学习任务特性的分析器
整体架构
主要是围绕两个目标，一个是用户，一个是操作者
1. 最小化平均JCT
2. 高GPU利用率
Tiresias有额外的目标来平衡上述两个目标
3. 任务不能无限的饥饿
给出一些实际的假设:
- 在线的任务到达: 任务被用户提交，一个任务的资源需求是给定的，但是优先级是未知的。
- 未知的任务持续时间：由于非平滑的误差曲线和不确定的停止，一个任务的持续时间无法预知，不过任务持续时间的分布是可以通过日志获取。
- 未知的任务特性：一个用户不知道也不能控制深度学习框架怎么分配tensor到参数服务器，以及相应的偏差。
- All-or-nothing资源分配：资源服务器和Worker需要同时活跃
任务的生命周期: Tiresias目的是优化先前的目标，同时不需要对任务资源需求，持续时间等做任何的假设。
给出整体的架构图
调度
整个系统的设计目标是，最小化平均JCT，增加集群利用率以及避免饥饿
我们观察到抢占式的调度式必需的，需要应用抢占来避免HOL(Head-of-line)阻塞，一些小的任务会被大的任务阻塞住。这是FIFO调度的缺陷，对于抢占的算法有许多，比如分时间片，SJF和SRTF。
Gandvia就是用分时间片来调度的。然而基于分时的算法目的在于公平分享达到隔离，并不是为了最小化JCT。而SJF和SRTF由于预测一个任务的持续时间很困难也不可行。只考虑GPU个数也不够有效，需要同时考虑任务的持续时间。
为什么是二维调度
通过回顾基于时间或大小的启发式方法，我们认为在具有有限GPU资源的群集上调度DDL作业时，仅考虑一个方面（空间或时间）是不够的。 在SRTF调度程序中，具有较短剩余时间的大型作业可占用许多GPU，从而导致许多小型但新提交的作业出现不可忽略的排队延迟
如果调度程序是最小优先（例如，GPU的数量），则即使大型作业接近完成也可能被小作业流阻塞。
这个图比较的是:
- 最小优先SF
- SRTF
- 最小保持服务优先SRSF
其中前两个是单维度的，第三个是考虑两个维度，表将SRSF作为基准进行标准化
可以看出SRSF是要比一维的调度策略要优的
2DAS调度器
2DAS是对传统LAS的扩展，同时考虑了时间和空间，它会赋予任务一个优先级，这个优先级和时间以及空间有关。
而这个优先级函数有不同的情况，当有没有先验知识的时候，即没有任务持续时间的分布的时候，使用LAS算法，如果有先验分布，则使用Gittins索引
我们将该算法和SRSF进行对比
由于SRSF是有充分的先验知识，故平均JCT比较短为9.3，而Gittins是10，LAS是11.7
优先级离散化
使用连续的优先级会导致一系列的抢占和一系列的重启，对于分布式深度学习任务来说，抢占和重启的代价很高，过多的抢占会导致2DAS不可用，为了解决这个问题，基于传统的多级别反馈队列(MLFQ)算法实现优先级离散化的框架
即，将原有的一个队列变成K个队列
给出一个任务的生命周期图
放置
给定一个任务，需要参数服务器以及Worker，如果有足够的资源，Tiresias需要知道是否在尽可能少的机器中合并一些任务的GPU或者去分发它们，前者在微软的的生产集群中实现，故一个任务即使资源足够也可能被放置在等待队列。
该文章使用ILP，即瞬间线性规划来优化这个分配问题。
合并对于任务来说重要吗?
深度学习模型中对于合并敏感的一般都有较大的张量， 原因是模型聚合中的消息大小与模型的结构密切相关。 例如，TensorFlow中的模型由许多张量组成。 每个张量都被包装为单个通信消息。因此，DDL中的消息大小分布取决于模型的张量大小分布。 张量大小通常分布不均匀; 有时存在巨大的张量，其中包含这些模型中的大部分参数。 因此，聚合较大的张量会更严重地受到网络争用的影响，而较小张量的传输往往会相互交错。
利用这个直觉，设计了Tiresias的分析器，用于分析每个模型的偏差程度，再使用放置的算法
总结
与Apache YARN的容量调度程序（YARNCS）和Gandiva相比，Tiresias旨在最小化平均JCT。 与Optimus不同，Tiresias可以在没有或具有部分先验知识的情况下有效地安排工作（表2）。 此外，Tiresias可以根据Tiresias pro fi ler自动捕获的模型结构巧妙地放置DDL作业。
分析
给出JCT的优化效果
平均JCT，Tiresias要高YARN-CS5倍左右，中位数JCT则最多高出27倍
GPU利用率看上去则差不多
长队列延迟的效果
