Gandiva Introspective Cluster Scheduling for Deep Learning

发表于 | 分类于 |

Gandiva: Introspective Cluster Scheduling for Deep Learning

论文发表在OSDI’18会议上，是系统设计/实现方面的顶级会议。作者是微软的研究员们。

Abstract

  1. 深度学习的一个关键特征是反馈驱动探索，其中用户经常运行一组作业（或多作业）以搜索特定任务的最佳结果，并使用准确率等早期反馈来动态地优先化或结束一部分作业; 同时的早期反馈对整个多工作任务的进行至关重要。

  2. 第二个特征是深度学习工作在资源使用方面的异构性，难以实现最佳拟合。

  3. Gandiva利用深度学习的第三个关键特征来解决这两个挑战：作业内可预测性，因为深度学习任务执行需要大量小批量重复迭代。

Gandiva利用作业内可预测性在多个作业中有效地对GPU进行时间分片，提供低延迟性。
此可预测性还用于评估作业性能和动态迁移作业以更好地适应GPU，从而提高集群效率。

通过原型实现和微基准测试表明，Gandiva可以在深度学习期间将超参数搜索加速一个数量级，并通过透明迁移和时间切片从而实现更好的作业-资源匹配。
实验表明，在180个GPU的集群中运行的实际工作负载中，Gandiva将聚合集群利用率提高了26％，表明这是一种管理大型GPU集群以进行深度学习的新方法。

1 Introduction

深度学习是计算密集型的，严重依赖功能强大但价格昂贵的GPU;云中的GPU VM价格是普通VM的10倍。 云运营商和大公司依靠集群调度器来确保GPU的有效利用。

尽管高效调度深度学习训练（DLT）工作非常重要，但今天的常见做法是使用传统的集群调度程序，如Kubernetes或YARN这些用于处理大数据 MapReduce的工具; DLT作业被简单地视为大数据作业，在启动时分配一组GPU，并保持对其GPU的独占访问，直到完成为止。

  • DLT工作的一个关键特征是反馈驱动的探索（第2节）。
    由于深度学习实验固有的反复试验方法，用户通常会尝试几种任务的配置（多任务），并使用这些任务的早期反馈来决定是否优先考虑或结束它们的某些子集。
    这种称为超参数搜索的条件探索可以是手动的也可以是自动的。
    传统的调度程序在排队时运行一部分作业子集;这种模式不适合多任务，需要同时对多任务中的所有工作进行早期反馈。
    此外，与多任务一起，其他DLT作业已经确定了正确的超参数并运行了几个小时到几天，导致线头阻塞（长时间运行的作业可以独立访问GPU直到完成），而依赖在早期反馈的多任务仍排队等待。长队列时间迫使用户使用保留的GPU，或者要求群集过度配置，从而降低群集效率。

  • 与任何其他群集工作负载一样，DLT作业是异构的，因为它们所针对的应用程序域不同。
    作业在内存使用，GPU核心利用率，带宽敏感度和其他作业的干扰性方面存在很大差异。
    例如，某些多GPU DLT作业可能对关联的GPU执行得更好，而其他作业可能对关联性不敏感（第3节）。
    将作业视为黑盒的传统调度程序因此将实现次优的集群效率。

  • 为了解决高延迟和低效率这两个问题，Gandiva利用了DLT作业的强大属性：作业内可预测性（第3节）。
    一项任务由数百万个类似的，分开的小批量迭代组成。
    Gandiva利用这种循环可预测性来实现有效的应用感知时间切片; 它重新定义了从作业到自动划分的微任务的调度原子。
    这使集群能够超额预订DLT任务，并通过时间切片为所有DLT任务提供早期反馈（包括作为多任务一部分的所有作业）。

  • Gandiva还使用可预测性来执行简介驱动的内省。
    它使用小批量不断反省其决策，以提高集群效率（第4节）。
    例如，它只在内存和GPU利用率较低时才在同一GPU上打包多个作业; 它动态地将通信密集型作业迁移到更加接近的GPU上; 它还机会性地“增长”工作的并行度以利用备用资源，并在备用资源消失时缩减工作量。
    我们目前实施的内省策略是一种有状态的反复试验策略，由于我们考虑的可预测性和有限的选择状态空间，这是可行的。

除了本文评估的特定内省和调度策略之外，Gandiva框架还提供以下API，任何DLT调度策略都可以利用这些API：（a）有效的暂停 - 恢复或时间切片，（b）低延迟迁移，（c）细粒度分析，（d）动态的工作内弹性，以及（e）动态优先级。
使这些原语高效和实用的关键是Gandiva的协同设计方法，跨越调度程序层和DLT工具包层，如Tensorflow或PyTorch。
传统的调度程序，有充分的理由将工作视为一个黑盒子。 然而，通过利用GPU集群的专用特性，Gandiva将调度程序定制为深度学习的特定工作负载，从而为调度程序提供更多的可见性和对作业的控制，同时实现对任意DLT作业的通用性。

通过修改两个流行的框架PyTorch和Tensorflow来实现Gandiva，为调度程序提供必要的新原语，并在Kubernetes和Docker容器之上实现初始调度策略管理器（第5节）。

2 Background

  1. 反馈驱动的探索。实现高精度的一个先决条件是模型选择，像ResNet或Inception这样的模型通常是反复实验处理的过程，尽管自动化的方法是一个活跃的研究领域。
    除了模型结构之外，还有许多超参数需要指定为DLT作业的一部分。
    超参数包括模型中的层数/权重，批量大小，学习速率等。这些通常由用户根据领域知识和反复试验选择，有时甚至可能导致早期训练失败。 因此，DLT工作的早期反馈至关重要，特别是在训练的初始阶段。

  2. 多作业。 一旦用户识别出要进一步探索的特定模型，用户通常执行超参数搜索以提高任务准确性。
    这可以在超参数的空间上使用各种搜索技术来完成; 也就是说，用户生成多个DLT作业或多个作业，每个作业使用一组超参数或配置执行训练。
    由于用户通常会探索数百种此类配置，因此此过程的计算成本非常高。
    超参数搜索方法，如Hyper-Opt和Hyperband。Hyperband可能最初产生128个DLT作业，并且在每一轮（例如，100个小批量迭代）中，以最低精度结束一半的作业。对于这些算法，对工作的早期反馈至关重要，因为否则他们将无法做出有效的训练决策。

3 DLT Job Characteristics

3.1 Sensitivity to locality

多GPU DLT作业的性能取决于分配的GPU的亲和性。不同的DLT作业对GPU间亲和力表现出不同的灵敏度。
即使对于同一台机器上的GPU，由于非对称架构，我们观察到不同级别的GPU间亲和性：两个GPU可能位于不同的CPU插槽中（表示为DiffSocket），位于同一CPU插槽中，但位于不同的PCIe交换机上（表示如同SameSocket），或在同一个PCIe交换机上（表示为SamePCIeSw）。




图1显示了VGG16和ResNet-50对服务器内局部性的不同敏感性。当使用Tensorflow对两个P100 GPU进行训练时，VGG16受到严重影响。当两个GPU位于不同的CPU插槽中时，VGG16仅实现最佳位置配置的60％，其中两个GPU放置在同一PCIe交换机下。另一方面，ResNet-50在此设置中不受GPU位置的影响。这是因为VGG16是一个比ResNet-50更大的神经模型，因此每个小批量的模型同步会在底层PCIe总线上产生更高的通信负载。

我们在分布式设置中观察到类似的趋势。
图2
显示了不同服务器间位置，训练ResNet-50和InceptionV3模型的4-GPU Tensorflow作业的性能。即使与40G InfiniBand网络互连，当作业分配到4个GPU时，也可以清楚地看到性能差异，它们均匀分散在4个服务器（表示为4 1-GPU），2个服务器（表示为2 2） -GPU），以及所有在一个服务器（表示为本地4-GPU），尽管两个模型的局部性的敏感性是不同的。
因此，DLT调度程序在分配GPU时必须考虑作业对位置的敏感性。

3.2 Sensitivity to interference

在共享执行环境中运行时，由于资源争用，DLT作业可能会相互干扰。
我们再次观察到不同的DLT作业表现出不同程度的干扰。

对于单GPU作业也存在干扰。 将语言模型作业（标记为LM）与另一个作业放在同一PCI-e交换机下时，
图3
显示了由于服务器内干扰导致的性能下降。
当两个LM一起运行时，两个工作都会减速19％。 但是，ResNet-50不会受到与LM共存的GPU的影响。 神经机器翻译（GNMT）表现出对LM的适度干扰。

图4
显示了与40G InfiniBand网络连接的两台4 GPU服务器之间的服务器间干扰。 当运行多个2-GPU作业时，每个GPU放置在不同的服务器上，ResNet-50显示减速高达47％，InceptionV3显示减速30％，而DeepSpeech仅显示5％减速。

3.3 Intra-job predictability

图5
DLT作业包含许多小批量迭代。
图5（a）中显示了在四个K80 GPU上使用ResNet-50模型时，在20秒的ImageNet数据训练期间使用的总GPU内存。
所使用的GPU存储器明显遵循循环模式。这些循环中的每一个对应于单个小批量（约1.5s）的处理，其中存储器在正向传播期间增加并且在反向传播期间减小。使用的最大和最小GPU内存分别为23GB和0.3GB，为77倍。该比例与小批量大小成比例（通常在16到256之间;在这种情况下为128）。

在图5（b）中显示了在一个K80 GPU上使用GNMT模型时，在WMT’14 English German language数据集训练期间使用的总GPU内存。虽然小批量迭代在ImageNet示例中彼此不相同（由于不同的句子长度和PyTorch中动态图形的使用），图形具有类似的循环性质。最大值和最小值之间的差异较小（3x）主要是由于较大型号（0.4GB）和较小的小批量（本例中为16）。

除了此处显示的图像和语言模型之外，其他训练领域，如语音，GAN和变分自动编码器都遵循类似的循环模式（由于空间限制而未显示），因为训练的核心都是梯度下降算法执行许多小批量迭代。

  • 利用可预测性。这种特征在Gandiva中以多种方式被利用。 首先，DLT作业可以自动拆分为小批量迭代，并且超过60秒的这些迭代的集合（微任务），形成调度间隔。
    其次，通过在存储器周期的最小值处执行挂起操作，可以显着减少要从GPU复制以保存在CPU中的存储量，从而使挂起/恢复和迁移能够比天真的实施更高效一个数量级。
    第三，可以对小批量进步率进行分析并将其用作代理，以评估应用包装或迁移等机制的有效性。

4 Design

图6

由于DLT作业被分配了一组固定的GPU（图6），因此集群出现高延迟和低利用率。 对GPU的独占访问会导致行头阻塞；阻止早期反馈；导致传入作业的高排队时间。 当作业无法完全利用其分配的GPU时，对固定GPU的独占访问也会导致GPU利用率降低。

4.1 Mechanisms

在Gandiva中，我们通过三种方式消除GPU对DLT作业的排他性和固定分配来解决这些低效问题（图6）

  1. Suspend-Resume and Packing。暂停 - 恢复是Gandiva用于删除一组GPU对DLT作业排他性的一种机制。现代操作系统支持CPU进程的高效挂起 - 恢复的时间切片。
    Gandiva利用这种机制并为GPU时间切片添加了自定义支持。
    如图5（a）所示，DLT作业对GPU内存的使用具有循环模式，最小和最大内存使用之间的差异高达77倍。 Gandiva的关键思想是利用这种循环行为，并在GPU内存使用率最低时采取暂停-恢复DLT作业。
    因此，当发出挂起调用时，DLT工具包会等待内存使用周期的最小值，将存储在GPU中的对象复制到CPU，释放所有GPU内存分配（包括缓存），然后调用经典CPU暂停机制。
    稍后，当CPU恢复作业时，DLT框架首先分配适当的GPU内存，将存储的对象复制回GPU，然后恢复作业。
    暂停 - 恢复还可以在同一服务器内改变GPU（例如，在六个1-GPU作业分时4-GPU的情况下）。 虽然更换GPU很昂贵，但我们会将这种延迟隐藏在关键路径之外。
    正如我们在评估（第6.1节）中所示，对于典型的图像分类工作，可以在100ms内完成暂停 - 恢复，而对于大型语言翻译工作，暂停 - 恢复可能需要1s。 给定1分钟的时间片间隔，这相当于2％或更少的开销。
    请注意，Gandiva中的暂停可能会延迟最多一个DLT作业的小批量间隔（通常为几秒或更短），但我们认为这是值得的权衡，因为它可以显着减少开销。 降低了GPU-CPU复制成本，减少了CPU中使用的内存。 此外，在此延迟期间完成了有用的工作。
    调度程序跟踪此延迟并相应地调整时间切片间隔以确保公平性。
    暂停 - 恢复时间切片的替代方法是同时在GPU上运行多个DLT作业，让GPU共享作业。
    我们称之为包装。 只有当打包作业不超过GPU资源（核心，内存）并且不会相互产生负面影响时，GPU中的打包才有效。 如果工作干扰，包装可能比暂停 - 恢复更糟糕（第6.1节）。 我们使用分析来监视DLT作业具有独占访问权限时的资源和进度。 如果两个工作被确定为包装的候选人，我们将它们打包在一起并继续监控它们。 如果给定的包装对工作效率产生不利影响，我们会拆开这些工作并返回暂停 - 恢复。

  2. Migration。 迁移是Gandiva用于更改分配给DLT作业的GPU集合的机制。 迁移在以下几种情况下非常有用：i）将时间切片的作业移动到群集中腾出的任何位置的GPU;
    ii）将干扰工作相互迁移开;
    iii）群集的碎片化，以便传入的作业获得具有良好局部性的GPU。
    我们评估了两种解决DLT流程状态迁移的方法。
    （1）在第一种方法中，我们利用通用的流程迁移机制，如CRIU。
    因为CRIU本身不支持使用GPU设备的进程迁移，所以我们首先对GPU对象创建检查点并在调用CRIU之前从进程中删除所有GPU状态。 由于CRIU检查点并恢复整个进程内存，因此使用PyTorch检查点的大小为GB数量级。
    因此，对于单GPU作业，所产生的迁移开销约为8-10s，对于多GPU作业，则更高。
    （2）的第二种方法是使用支持检查点的DLT作业。诸如Tensorflow之类的DLT框架已经支持创建自动检查点和模型恢复的API（例如，tensorflow.train.saver）。此API现在用于确保不必因服务器故障而重新运行长时间运行的作业。我们扩展框架以支持此类工作的迁移。通过在迁移之前”预热“目的地并且仅迁移必要的训练状态，我们可以将迁移率减少到一秒或两秒（第6.1节）。无论采用哪种方法，我们都发现服务器间迁移的开销与其提供的更高整体GPU利用率相比是值得的。

  3. Grow-Shrink。 Gandiva用于消除GPU对DLT作业的排他性的第三种机制是成长-缩减。该机制主要针对群集可能无法充分利用的情况，例如深夜时。基本思想是在空闲时机会性地增加可用于工作的GPU的数量，并且相应地减少负载增加时可用的GPU的数量。
    许多DLT作业（尤其是图像域中的作业）随着GPU数量的增加而看到线性性能缩放。
    Gandiva仅将这种机制应用于那些明确表明其足够自适应以利用这些增长机会的DLT工作。
    当多个DLT作业符合此标准时，Gandiva使用下面讨论的分析信息来估计每个作业的进度，然后相应地分配GPU。

  4. Profiling。与任何调度程序一样，Gandiva监视资源使用情况，例如CPU和GPU利用率，CPU / GPU内存等。然而，Gandiva的独特之处在于它还以应用程序感知的方式内省DLT作业估计其进度。 这种内省利用了DLT作业（第3节）展示的规则模式，并使用周期性来估计其进度。
    Gandiva估计DLT作业的小批处理时间，即对一批输入数据进行一次前向/后向传递的时间，作为GPU内存使用周期的两个最小值之间所花费的时间（图5（a））。 由于DLT作业通常在其生命周期中执行数百万个这样的小批量操作，因此调度程序在调度决策之前和之后比较DLT的小批量时间以确定其有效性。例如，考虑在前面描述的GPU中打包两个DLT作业的示例。 通过比较包装前后两个DLT作业中每个作业的小批量时间，Gandiva可以决定包装是否有效。 如果没有这样的分析，为了做出包装决定，人们不仅要模拟两个DLT作业在各种GPU上的性能，还要模拟它们可能相互干扰的各种方式（例如，高速缓存，内存带宽等）。 。），这是一项非常重要的任务，我们在第6.1节中看到了不同的包装性能。

略

8 Conclusion

略

0%