MLSys提前看｜机器学习的分布式优化方法
机器之心分析师网络
作者：仵冀颖
编辑：Hao Wang
第三届机器学习与系统会议（MLSys 2020）将于 2020 年 3 月 2 日至 4 日在美国奥斯汀会议中心举行。MLSys 是 2018 年新成立的一个聚焦机器学习在系统、软件、硬件等多个综合领域中应用研究的学术会议。
随着机器学习算法和模型的不断发展，传统的软硬件平台、部署环境等无法支撑机器学习的应用，这也成为了目前机器学习方法落地及大规模推广应用的主要困难之一。目前，有关于 MLSys 的研究方向包括硬件领域、软件领域和对机器学习算法的改进三个方面，以 MLSys 2020 为例，本届大会的议题包括：Distributed and parallel learning algorithms（5 篇论文）、Efficient model training（8 篇论文）、Efficient inference and model serving（8 篇论文）、Model/Data Quality and Privacy（4 篇论文）、ML programming models and abstractions & ML applied to systems（5 篇论文）以及 Quantization of deep neural networks（4 篇论文）。整个会议一共录用 34 篇论文。
在本篇提前看中，我们选择了三篇文章进行详细分析，以了解机器学习与系统（Machine Learning and Systems）领域最新的研究成果。其中，前两篇文章属于经典的机器学习分布式优化方法（通信方式、内存分配方法），第三篇文章则是关于一种新的用于机器学习的具有高度系统性和设备（统计、数据）异质性的分布式方法--联邦学习。
Blink: Fast and Generic Collectives for Distributed ML
Efficient model training topic
https://arxiv.org/pdf/1910.04940.pdf
随着高质量数据库、大规模数据集的不断发展，深度学习模型不断改进，在图像分类、目标检测、机器翻译、语音处理等领域都获得了很好的效果。与之同时，漫长的训练时间却成为了另一个让人头疼的问题。在处理一些图像分类任务时，在单个 GPU 中的训练时间甚至需要几天！基于多个 GPU 的数据并行训练（Data-Parallel Training）的引入，大大缓解了大规模深度学习模型训练耗时长的问题。在数据并行训练中，每个 GPU 都有一个完整的模型参数副本，同时也会与其他参与训练的 GPU 交换参数。这篇文章介绍的是 MLSys 领域中基于 GPU 的模型参数同步问题。
跨 GPU 的参数同步在大规模训练时产生了较大开销，对于常见 ML 模型，通信开销可以从 50% 到 90% 不等。解决这一问题的手段主要有两种：硬件手段—先进的多 GPU 服务器，例如 NVIDIA』s DGX-1、DGX-2 等；软件手段，利用了 Wait-free 反向传播技术的现代通信原语，例如 NVIDIA『s Collective Communications Library (NCCL)、百度的 Ring AllReduce 等。本文研究的是软件手段，提出了 Blink—一个通过包装生成树动态生成最佳通信原语的集合通信库。为了处理硬件生成中的拓扑异质性问题或集群调度程序中的分配问题，Blink 能够动态生成给定拓扑的最佳通信原语。
【目前的问题】
即使在 NVIDIA DGX-1 这样的快速多 GPU 服务器上运行数据并行训练时，深度学习工作负载也会带来很高的通信开销。更重要的是，作者发现，即使在像 DGX-1 这样的高性能服务器内，现有通信原语如 NCCL 或 Horovod 也会放大通信开销，作者认为，这主要是因为它们无法处理拓扑异质性问题。DGX-1 中既有诸如 NVLink（20-25GB/s）的 GPU 点对点（P2P）互连，也有诸如 PCIe（8-12GB/s）的共享互连。PCIe 通过 PCIe 交换机层次结构将多个 GPU 相互连接到一台计算机内，并连接到 CPU 和 I/O 设备。NCCL、Horovod 等通信原语基于环的模式（Ring-based Protocols）进行数据传输，然而，基于环的协议有结构上的限制：对于每个环，每个节点只能有一个输入和一个输出。基于环的模式将所有的通信节点通过首尾连接形成一个单向环，数据在环上依次传输。假设有 3 个 GPU，GPU0 为信息的发送者，将信息发送给剩下的 GPU，基于环的通信原语按照环的方式将信息传输，即 GPU0-->GPU1-->GPU2。这种限制使得环无法适应由于调度程序分配而导致的不规则拓扑，如图 1 所示。环的吞吐量受到带宽最低的链路的限制，因此这些协议要么将自己限制在高带宽、同质链路上，要么将吞吐量限制在环中带宽最低的链路上。以 NCCL 为例，对于一台机器内的多 GPU 通信，NCCL 将优先使用 NVLink，而当在 NVLink 环中时，PCIe 将成为瓶颈。
图 1. 群集上每个 8-GPU 服务器中分配给 Cloud-X 上 40000 个多 GPU 作业的 GPU 数
此外，这些限制还会导致链接使用不足，如图 2 所示。
图 2. DGX-1P 中 NCCL 与本文提出的 Blink 在 6-GPUs 上的广播比较
通过将 GPU 之间的链接建模为图，前期的研究结果表明，包装生成树 (Packing Spanning Trees) 能够生成从有选择的根顶点到有向图中的所有其他顶点的最大流。基于此研究，作者认为一对多协议（如使用根节点的生成树进行广播）是克服链路利用率不足的一个潜在有效选择。当然，除了像广播这样只转发数据的操作之外，还需要实现像 AllReduce 这样的通信原语，即可以被建模为在一个方向上减少并前进（面向根的方向），然后在另一个方向广播。
【Blink 详解】
图 3. Blink 工具链工作流
给定拓扑，Blink 的主要方法是动态地生成适当的集合通信原语。通过引入包装生成树来实现高利用率，使用能够最大化传输速率的算法，同时最小化所使用的树的数量。最后，通过在双向链路的每个方向上执行多对一和一对多的操作来实现像 AllReduce 这样的多对多算法。Blink 工具链完整工作流见图 3 所示。具体步骤包括:
（1）给定深度学习任务，一旦安排并分配了一组 GPU，Blink 就能够探测机器的拓扑结构，并通过分配的 GPU 推断互连拓扑结构。
（2）给定拓扑，将集体通信操作建模为有向图上的流，并计算生成树的最大分数填充。此步骤表示为图 3 中的 TreeGen，此步骤输出一组生成树和对应于应通过它们发送多少数据的权重。
（3）CodeGen 解析生成树并生成 CUDA 代码。生成的代码与 NCCL 提供的 API 匹配，并打包到共享库 libblink.so 中。
（4）设置 LD_PRELOAD 标志，以便在调用主程序时动态加载 Blink 实现。这确保了现有程序可以在没有任何修改的情况下运行
1、包装生成树
将从分配的资源推断出的拓扑建模为一个有向图，其中每个 GPU 是顶点 V，每个链路（NVLink 或 PCIe）标记为有向边缘 E。每个有向边缘还具有带宽比例容量。通过找到图中的有向生成树或树状图的最大填充可以达到最优速率。每个树状图 Ti 从根涡生成，沿着有向链接扩展到其它涡点。通过确定满足能力限制的最大权重树状图，可以解决在广播中确定最佳时间表的问题。
由上式，给定一个图 G，顶点为 V，边为 E，根为 r，生成树为 T1, T2, T3, ... Ti，希望找到权重 w_i，使得通过任何边的权重树的总和不超过特定边的容量。
2、减小生成树的数目（优化算法）
乘法权重更新（multiplicative weight update，MWU）是一种广泛应用于优化、博弈论等各个领域的算法。本文使用 MWU 实现分数线性包装问题的近似线性时间逼近。使用一个容量和一个权重来初始化每一个边，这个权重用来标记已经使用了多少容量。运行一个迭代方法，每次迭代都会找到给定当前分配的最小权值生成树。然后，将所选树上的权重增加一个 ε 因子，并相应地更新图上的权重。给定 T1, T2, T3, ... Tk，为了最小化生成树的数目，构造了一个整数线性规划问题（integer linear program，ILP），每个权重被限制为 0 或 1：
其中，k 由 MWU 过程返回的树的数目控制，因此比图中的生成树的总数小得多。
3、推广到多对多的情况
为了处理多对多的操作，作者利用了这样一个事实：在这些机器中发现的所有链接本质上都是双向的，因此可以创建一个无向图，用链接的一个方向运行多对一原语，并相应地在另一个方向运行一对多原语。这种使用两个无向树的策略也与 AllReduce 操作所需的消息数下限相匹配。
AllReduce 的进程需要发送的最小消息数是 2x|(N-1)/N|。N 个顶点上的生成树包含 N-1 条边，并考虑了两个方向上的树（一个用于 Reduce，一个用于 Broadcast），类似的，本文方法同样有 2x(N-1）条消息。
4、处理复杂通信问题
处理复杂问题重点探讨的是处理复杂的 PCIe 和 NVLink 拓扑。使用 PCIe 和 NVLink 的主要挑战来自 NVIDIA 驱动程序不允许用户直接控制对两个链路的访问，如果检测到 NVLinks，系统将自动启用使用 NVLinks 的 GPU 之间的 P2P 数据传输。作者通过实验发现，使用 cudaDeviceDisablePeerAccess 会禁用 NVLinks 并强制通过 PCIe 链路传输数据。然而，这仍然有一个局限性，即不能用这两组链接构造一个统一的拓扑。作者通过构造两个独立的树集来解决这个问题，一个在 PCIe 链路上，另一个在 NVLinks 上。这种方法的难点之一是平衡在每种链路类型上传输的数据量，作者使用的方法是最小化每个传输所花费的最大时间，即最小化 MAX（T_pCIe, T_NVL），其中 T_pCIe 和 T_NVL 表示每条链路上的数据总数。定义 D_total 为待传输的数据总量，T_dpa 为调用 disable_peer_access（）的延迟，BW_PCIe 和 BW_NVL 表示为 PCIe 和 NVLink 树的带宽，通过使 T_PCIe=T_NVL 可以实现最佳的数据分割。
其中，T_dpa 由经验性测量得到并可能根据 GPU 的数量而变化。
5、应对多服务器设置
最后，作者以 DGX-2 和多机训练为例，讨论如何应对多服务器设置。DGX-2 由 16 个通过 NVSwitch 连接的 V100 GPU 组成；每个 GPU 通过 6x NVLink 连接到 switch。在 DGX-2 上，Blink 为 AllReduce（reduce broadcast）生成的生成树为：对于 mGPU，每个 GPU 充当 1/m 个数据块的根，每个根直接连接到（m-1）个叶节点，从而生成 m 个一跳（one-hop）树。当训练任务的 GPU 跨越多个服务器、通过交换机或交换机层次结构连接时，Blink 使用三相协议，如图 4 所示。其中，第一个阶段对本地生成树上的每台服务器进行缩减—每台服务器中的每棵树的根会像以前一样聚合来自其子级的数据。第二个阶段跨服务器进行 reduce 广播（类似于 DGX-2 中的内容）–跨 n 个服务器，有 n 个单跳跨服务器树，每个服务器的本地根连接到其他服务器上的（n-1）个根。第三阶段根据每个服务器的本地根目录，将第二阶段的结果广播给服务器中的所有节点。
图 4. 用于跨服务器设置的三相 AllReduce 协议，其中 X_m,g 表示服务器 m、GPU g 上的数据分区
【实验分析】
首先，作者给出了本文提出的包装生成树的理论效益。在 V100 和 P100 机器上，实验比较了 NCCL 在给定拓扑中创建的环的数量和 Blink 打包的所有可能分配的生成树的总重量（从 3GPU 到 8GPU）。我们使用广播和 AllReduce 所需消息的下限（分别为 [(N-1)/N] 和 [2x(N-1)/N]）将其转换为广播速率。对于 8GPU 的情况给出了 4 个环，每个环将在 8/14 的链路带宽下工作，对于 4 个这样的环，有效速率是 32/14。实验中，近似 PCIe 环的带宽为 NVLink 环带宽的一半。实验结果如图 5，在所有情况下包装生成树的速度与使用环一样快，而在某些情况下（即环必须通过 PCIe），包装生成树的速度达到了环的 6 倍。
图 5. DGX-1P（P100）和 DGX-1V（V100）理论加速比对，方块图显示了可能的配置分布
第二，作者给出在三种不同的硬件设置（DGX-1P，DGX-1V，DGX-2）上 NCCL 和 Blink 在广播和 AllReduce 中的吞吐量比较的实验结果。作者在这一组实验中给出了一系列实验结果以验证 Blink 的有效性，受篇幅所限，我们不一一贴出，给出 NCCL 和 Blink 之间的广播吞吐量比较作为示例，该示例比较 AWS（p3.16xlarge）上 DGX-1V 上 GPU 分配引起的所有可能拓扑，使用的 GPU 数量从 3 到 8 不等。为了使互连完全饱和，使用总数据大小为 500MB（50MB 到 1000MB 的误差线）进行测试。具体结果见图 6。
与 NCCL 相比，Blink 的性能可以提高 6 倍（2 倍的几何平均值）。在 GPU 未通过 NVLink 完全连接的情况下（例如 GPU 1、4、5、6），NCCL 无法在这些 GPU 上形成仅 NVLink 的环，从而迫使其重新使用 PCIe 进行数据传输。这会导致许多 NVLink 通道未使用，显著降低吞吐量。NCCL 在 Blink 可以形成完全连接的 NVLink 环并且 Blink 只能创建一个生成树时匹配 Blink。但是，即使在这些情况下，由于优化了分块传输，Blink 仍能获得 3-5GB/s 的更高性能。
图 6. DGX-1V 上所有独特拓扑 NCCL2 和 Blink 的广播吞吐量比较
第三，作者讨论在使用 PCIe 和 NVLink 执行混合数据传输时的权衡。为简洁起见，仅在 AWS DGX-1V 服务器上显示 3-8 GPU 的广播结果。实验结果见图 7，显示了当 Blink 同时通过 NVLink 和 PCIe 传输时，仅通过 NVLink 传输的额外 2-5 GB/s 性能增益。从 NVLink 到 PCIe 的通信通道切换时间随着 GPU 数量的增加而增加。对于 3 和 4 GPU 设置，与仅 NVLink 广播相比，混合传输可实现约 5GB/s 的提升；对于 7 和 8 GPU，此加速仅为约 2GB/s。这是因为启用和禁用对等访问（即在 PCIe 和 NVLink 之间切换）所花费的总时间与使用的 GPU 数成正比。
图 7. 混合和 NVLink 在不同 GPU 数下的广播吞吐量比较
最后，作者给出在单个 DGX-1 和多个 DGX-1 设置上使用四个常用 DNN 的 Blink 的端到端加速结果。作者将 Blink 与 Pytorch 结合起来，并评估训练的端到端性能增益。使用四个流行的 CNN：AlexNet、ResNet18、ResNet50 和 VGG16，并在 ImageNet-1K（ILSVRC12）数据集上训练这些模型。对于所有模型都使用与原始论文中相同的每 GPU 小批量大小和超参数。
如图 8 所示，在单服务器的情况下，将集合通信后端从 NCCL2 切换到 Blink，可以将端到端 DNN 训练迭代所花费的时间最多减少 40%（6.3% 几何平均值），并实现最多 87% 的通信时间减少（31% 几何平均值）。
图 8. DGX-1V 机器内的闪烁端到端训练时间缩短（ImageNet1K）
在多服务器的情况下，图 9（a）显示 Blink 比 Horovod 的 NCCL/MPI 高出 11%，与单服务器训练相比，Blink 在 NCCL 方面的改进有所减少。为了了解更快的互连将如何改变性能，图 9（b）给出了一个改变跨机器带宽的模拟结果。实验比较了 100MB 数据的吞吐量，发现随着跨机器带宽的增加，Blink 的设计将带来更显著的端到端优势。
图 9.Multi-DGX-1 DNN 中 Blink 训练结果
【文章小结】
本文提出的 Blink 是一个快速通用的集体通信库，用于加速分布式机器学习。为了处理在现代 GPU 硬件中普遍存在的拓扑异质性，Blink 使用动态包生成树以最大化链路利用率。与目前最先进的、基于环的集体通信协议（如 NCCL2）相比，Blink 可以实现高达 8 倍的模型同步速度，并将端到端 DNN 模型训练时间减少 40%。
Salus: Fine-Grained GPU Sharing Primitives for Deep Learning Applications
Efficient inference and model serving topic
https://arxiv.org/pdf/1902.04610v1.pdf
随着深度学习（deep learning，DL）应用的普及，GPU 计算正变得越来越流行。然而，与传统资源（如 CPU 或网络）不同，现代 GPU 本身并不支持细粒度共享原语（最细的颗粒度就是整个 GPU）。因此，实现诸如分时和抢占等公共策略的代价是非常昂贵的。更糟糕的是，当一个 DL 应用程序不能完全使用 GPU 的资源时，GPU 不能在多个应用程序之间有效地共享，从而导致 GPU 利用率低下。虽然这种访问 GPU 的排他性简化了硬件设计并使其变得高效，但它导致了两个主要的低效率：首先，粗粒度、一次一个的 GPU 分配模型阻碍了 GPU 集群管理器的调度能力；其次，并非所有的 DL 作业都能一直充分利用 GPU。此外，日益流行的 DL 模型的自动超参数调整趋势进一步强调了提高 GPU 利用率的必要性。这种自动超参调整可以被视为「预训练」的过程。它通常是通过为超参数探测并行生成许多训练作业来完成的，其中许多作业一旦被认为质量低劣就会被杀死。
为了解决这些问题，这篇文章的作者提出 Salus，一种使细粒度的共享 GPU 与灵活的调度策略共存的方法。Salus 通过公开两个 GPU 共享原语来实现这一点：快速任务切换和内存共享。前者确保可以在 GPU 上快速切换当前活动的 DL 作业，从而实现高效的时间共享和抢占。后者通过在同一设备上打包更多的小 DL 作业来确保高利用率。DL 应用程序独特的内存使用模式是在 Salus 中高效实现这些原语的关键：识别三种不同的内存使用类型，并在处理它们时应用不同的管理策略。将这两个原语组合在一起，可以使用细粒度时空共享来实现各种解决方案。
【SALUS 详解】
1、总体结构
Salus 被实现为一个单一的执行服务，它整合了所有 GPU 访问，从而支持 GPU 共享，同时避免了 GPU 上进程之间代价高昂的上下文切换。因此，任何未修改的 DL 作业都可以使用 DL 框架特定的适配器利用 Salus，如图 10 所示。从用户角度来说，Salus 相当于一个虚拟计算资源。而从用户角度，框架的 API 并没有什么变化，无需增加新操作。
Salus 已经开源：https://github.com/SymbioticLab/Salus
图 10. Salus 位于 DL 框架和 DL 堆栈中的硬件之间，对用户是透明的
当在用户脚本中创建 DL 作业时，DL 框架中的 Salus 适配器在 Salus 中创建相应的会话（1a）。在创建过程中，DL 作业的计算图也被转移到 Salus。然后，会话继续从存储器管理器（1b）请求通道。根据系统中的当前作业，此进程可以阻塞从而会话将排队。在作业运行过程中，无论是训练还是推断，迭代都由用户脚本生成并转发到 Salus 中的相应会话（2a）。然后，它们由迭代调度器（2b）根据其关联的 GPU 通道进行调度，并发送给 GPU 执行。Salus 执行服务通过 DL 作业的迭代粒度调度实现 GPU 共享。
2、快速任务切换
首先，作者对于 DL 任务中内存分配的类型进行分析。
模型：这些主要保存模型参数，通常由一些大的内存块组成。由于模型大小在整个训练过程中通常是固定的，因此模型数据很少或没有时间变化，并且是可预测的。短暂：这些是每次迭代所需的临时内存。这些内存通常保存中间层的输出以及算法本身生成的临时数据。它们只在计算期间才需要，并且在迭代之间被释放，从而产生 DL 作业的时间内存使用模式。它们通常也是大内存分配。框架：这些通常被 DL 框架用于记账或数据准备通道。它们经常在迭代中持续存在。由上述分析可知，模型和框架类的内存需求在迭代过程中是一直存在的。此外，对于 DL 作业，持久内存使用率明显低于临时内存。有可能在 GPU 中保留多个作业的持久内存，同时仍有足够的空间存储任一作业的短暂内存。由此，作者得出结论：不从 GPU 中删除持久内存就可以实现快速的作业切换。
考虑到迭代在 DL 作业中通常很短（从几十毫秒到几秒不等），而且粒度更细，例如在 GPU 内核级别，因此可以进一步利用 GPU 资源。但是，细粒度的调度也会给执行服务增加更多的开销。因此，对于给定的调度粒度，需要在最大利用率和效率之间寻找最优的折衷。考虑下面的场景，给定 12GB 的 GPU 内存容量，作业 A 和作业 B 进行了两次迭代。它们的模型内存使用量是 PA=PB=1GB，而临时内存使用量是 EA=EB=7GB（由于框架相对较小，忽略了它的内部使用量）。内存的分配方式不是一次分配所有 8GB，而是一个作业的每个迭代以不同的增量分配。在迭代之间切换的选择允许回避渐进式内存分配的问题。这是因为框架在每次迭代后都会释放所有短暂的分配，并且模型和框架内部分配在整个迭代中保持不变。
3、内存共享
在高效作业交换的基础上，作者设计了一种特殊的内存布局方案 GPU 通道（Lane），实现了内存共享，从而提高了内存利用率。首先，将 GPU 内存空间分为短暂的和持续的区域。「模型」和「框架」分配持续区域，而「短暂」则分配的是短暂的区域。短暂区域进一步划分为通道，通道是连续的内存空间，其中可以包含用于迭代的短暂内存分配。然而，通道又不仅仅是关于内存。实现通道内串行的迭代过程以及基于 GPU 流的通道间并行处理，其中，每条通道都可以分配给多个 DL 任务。
首先，通过实现一个能感知应用程序的箱式内存分配器 (application-aware bin-based memory allocator) 来解决这个问题，以减少内存碎片。这种方法打破了通常在 DL 框架中使用的内存优化，因为它们假设一次运行一个作业。将短暂区域划分为通道并不能消除内存碎片，它会将通道内的碎片移动到通道级别的碎片，只不过解决通道级别的碎片化要相对容易一些。在通道的情况下，所分配的内存在每次迭代结束时完全释放，并在下一次迭代开始时返回，毕竟它们是短暂的内存。因此，碎片整理几乎是自动进行的，无需任何成本，也不需要额外的内存移动。
在进行通道内存分配的过程中，始终保持满足下式：
其中，Pi 和 Ei 分别是任务 i 的持久性内存（模型和框架内部）和短暂内存，Lj 表示通道 j 的通道大小，同时也被定义为通道中所有工作的最大短暂内存使用数。C 是 GPU 的容量。Salus 通过确保所有允许的作业都分配有足够的持久内存容量，并为具有最大临时内存需求的迭代保留足够的内存，提高了内存的利用率，同时也确保了通道中至少有一个作业可以继续。
作者也认为：「如何组织通道分配是一个悬而未决的问题。我们通过实验认为使用我们的算法非常有效，但是给定一组任务，找到最优通道数存在更多其它的可能。」
4、调度策略
通过使用细粒度的 GPU 共享原语，Salus 可以将多个作业打包在一起以提高效率，优先抢占长时间运行的作业而不是较短的作业（或基于其他优先级标准），此外，还有很多不同的调度策略值得进一步探索。在这篇文章中作者试用了简单的调度策略，包括 PACK（目标是优化资源利用）、SRTF（最短剩余时间优先）和 FAIR（在当前任务中平均分配资源）。
【实验分析】
本文将 Salus 与 TensorFlow 集成进行实验，所有的实验都是在一台基于 x86_64 的 Intel Xeon E5-2670 机器上进行的，带有 2 个 NVIDIA Tesla P100 GPU。每个 GPU 都有 16GB 的片上存储器，以及使用 Tensor-Flow v1.5.0 和 CUDA 8.0。实验中主要基准是当今 GPU 集群中常用的 FIFO 调度，此外还与 NVIDIA MPS 进行了比较。
首先，评估 Salus 对训练的影响，对比方法包括 FIFO、SRTF、PACK 和 FAIR。图 11 中实验证明了 Salus 允许快速抢占内存，同时又允许实现最短剩余时间优先（SRTF）调度策略。考虑长作业任务，一个大的训练工作已经运行了一段时间，然后用户想快速地为较小的网络做一些超参数调整的测试。如果没有 Salus，用户只能等到大的工作完成才能开始新的测试-这是 HOL 阻塞的一个例子。而 Salus 能够通过高效切换来实现抢占，以运行短作业，并在稍后恢复较大的作业。图 11（a）中的任务为：当作业 #1 到达时，后台作业 #0 立即停止，Salus 切换到运行新到达的较短作业。作业 #2 比作业 #3 来得早，但由于作业 #3 较短，所以它是先安排的。最后，由于作业 #5 较短，因此作业 #4 被抢占，并让作业 #5 运行到完成。在该过程中，后台作业 #0 仅在没有其他较短作业存在时才被调度。图 11（b）是另一个 Salus 快速切换能力的例子。它是以秒为单位的内存分配活动的可视化：在作业切换时，第二个作业的迭代在第一个作业停止后立即开始。
图 11. 使用 SRTF 运行长任务的详细信息。在两个切片中，时间都是标准化的
图 12 中实验展示了 Salus 如何允许多个 DL 作业之间的秒粒度公平共享，而不是分钟粒度。在这两种情况下都考虑单一的 GPU 通道。一共包括 4 个训练任务：googlenet_100、resnet50_25、alexnet 100 和 resnet50_50 在实验过程中处于活动状态，Salus 尝试使其 GPU 时间相等。同样，所有的切换都发生在亚秒的粒度。
图 12. 使用 FAIR 的长任务内存使用情况
其次，作者对于 Salus 在超参调参情况下的性能进行了实验。作者评估了两组超参调参任务：resnet50_50 和 superres_128，分别用于图像分类和图像分辨率增强。每组任务包含 300 个作业，当 300 个作业全部完成时代表一个任务完成。使用 FIFO（在 TensorFlow 中）和 Salus 实现的最大完工时间的比较如图 13 所示。在 resnet50_50 的情况下，Salus 有 1.07 倍的改进，而 superres_128 中 Salus 的最大完工时间改进是 2.38 倍。在 resnet50_50 中几乎没有什么改进，这是因为即使 GPU 有足够的内存将许多作业放在一起，计算也很可能成为此时完成任务的瓶颈。
图 13. 超参调参任务情况
【文章小结】
现代 GPU 及其运行时不允许在 GPU 中共存多个进程。对于 DL 任务来说，执行一个任务过程中空闲状态的内存无法释放给其它作业使用，这导致了巨大的资源浪费、性能损失、效率降低以及出现线头阻塞 (Head-of-lineblocking,HOL)。本文提出的 Salus 是一个整合的执行服务，它支持在复杂的、未修改的 DL 作业之间细粒度的 GPU 共享。
Salus 是一种尝试，它还带来了很多需要进一步研究解决的问题。首先，Salus 提供了一种机制，但策略问题是：在共享 GPU 上运行 DL 作业的最佳调度算法究竟是什么？本文探讨了集中简单的调度策略，但是对于最佳调度策略的判断依据未做讨论。其次，虽然本文没有重点介绍，但 Salus 可以扩展到同一台机器上的多个 GPU 甚至其他加速器。最后，作者提到，他们在下一步的工作中计划利用 RDMA 将 Salus 扩展到多台机器上的 GPU 中。
Federated Optimization in Heterogeneous Networks
Distributed and parallel learning algorithms topic
https://arxiv.org/pdf/1812.06127.pdf
联邦学习已经成为了一种在远程设备网络中分发机器学习模型训练的有效方法。虽然都是针对机器学习的分布式优化，但是联邦学习与传统的分布式优化方法（例如本篇文章中我们分析的前两篇论文）有两个关键的区别：*高度的系统异质性**和统计异质性*。为了处理异质性和解决高通信成本问题，联邦学习采用的是局部更新和低参与度的优化方法。FedAvg 是一种著名的联邦学习方法：在每次迭代中，FedAvg 首先在 K 个设备上执行 E 轮随机梯度下降（SGD）阶段，其中 E 是一个小的表示 Epoch 次数的常数，K 是网络中所有设备的一小部分。然后，这些设备将其模型更新传递到中央服务器，并在那里对其进行平均化处理。虽然 FedAvg 在处理异质环境问题中显示出了其有效性，但它并没有完全解决与异质相关的潜在挑战。
关于联邦学习，机器之心做过重要研究进展的梳理，感兴趣的读者可以读一读相关文章：打破数据孤岛：联邦学习近期重要研究进展
在存在系统异质性的情况下，基于 FedAvg 框架，各个设备并不能根据自身的资源情况完成工作量可变的工作。相反，如果在给定的时间内，设备没有能够在 E 轮迭代中返回局部优化的结果，FedAvg 会直接删除该设备。这种直接删除没有及时反馈局部优化结果的设备（如 FedAvg）或简单收集设备中的部分信息（如 FedProx 中修正项为 0 的情况下）的操作都会在一定程度上增大系统的统计异质性，并且会对收敛行为产生不利影响。为了解决联邦学习中的异质性问题，本文提出了 FedProx 框架。FedProx 引入了一个修正项（the proximal term）来提高整体框架的稳定性，该修正项的本质是针对局部模型中的参数和全局模型中的参数增加差异性的限制，从而为解释全局与部分局部信息之间的异质性提供理论依据。
【FedProx 详解】
首先回顾一下经典的 FedAvg 方法。目标函数为下式：
其中，N 为设备总数，pk≥0 表示每个设备更新的权重。一般来说，本地优化目标衡量的是不同数据分布的本地经验风险 Dk，例如
其中，n_k 表示第 k 个设备上有 n_k 个样本。一般设置为 p_k=n_k/n，其中 n 为全部 n_k 的总和。一般认为 Fk(w) 为非凸的。
为了减少通信量，联邦优化方法中的一种常用技术是，在每个设备上，使用基于设备数据的局部目标函数作为全局目标函数的代理。在每次外部迭代中，选择一个参与本次迭代的设备子集，并使用局部优化算子优化每个选定设备上的局部目标函数。然后，这些设备将其本地模型更新传递给中央服务器，中央服务器聚合它们并相应地更新全局模型。在这种情况下，如果能够做到非精确地求解每个局部目标函数的最优解，就能够保证整体的灵活性能，这也意味着必须允许根据执行的本地迭代次数（与更精确的本地解决方案相对应的附加本地迭代）调整本地计算量与通信量。从数学上表示，这是一种γ-不准确解。
FedAvg 中有一个值得注意的问题是：FedAvg 中 E 的选择对全局目标函数的收敛性起着重要作用。一方面，E 越大就意味着存在较多的局部计算和较少的设备间通信，这能够极大地提高全局目标函数的整体收敛速度。但是从另外一个角度分析，对于不同的（异质的）局部目标 Fk，设置较大的 E 值，却可能导致每个设备都致力于实现其局部目标函数的最优，而不是全局目标函数的最优，这反而会影响全局目标函数的收敛甚至导致发散。
本文提出的框架 FedProx 与 FedAvg 类似，它在每一轮中选择一个参与更新的设备子集，执行本地更新，然后对这些更新进行平均化处理以形成全局更新。然而，FedProx 做了一些简单而关键的修改，使得其具有收敛性保证。
1、容忍部分工作（Tolerating partial work）
在分布式工作的联邦学习网络中，不同的设备资源不同，例如硬件条件、网络环境、电池水平等，因此不可能要求设备完成一样多的工作。在 FedProx 中，我们通过允许基于可用系统资源的设备在本地执行可变工作量的工作来改进 FedAvg，最后聚合从各个设备发出的「部分」解决方案（与完全删除这些设备的策略是不同的）。此时，FedProx 执行的是 (γ_k)^t-不准确解。(γ_k)^t-不准确解测量在第 t 轮时为解决设备 k 上的局部子问题而执行的局部计算量。局部优化过程的迭代次数为 (γ_k)^t 的近似。通过引入 (γ_k)^t-不准确解，能够有效扩展 FedAvg 的收敛结果，从而解决与系统异质性相关的问题。
2、修正项（Proximal term）
允许联邦学习框架具备灵活的性能的关键是有针对性的实现每个设备中的局部目标函数优化，这就要求必须允许设备能够根据每次执行的本地迭代次数（与更精确的本地解决方案相对应的附加本地迭代）自动调整本地计算量与通信量。
向局部目标函数中增加一个修正项，以有效地限定可变化的局部更新的影响。特别地，不是仅仅最小化局部函数 Fk，而是令设备 k 使用它的局部优化算子来近似地最小化以下目标函数 h_k：
增加修正项有两个有益效果：（1）通过使得局部的更新更加接近于初始（全局）模型来解决联邦学习框架中不同设备间的统计异质性问题，而不需要手动设置局部 E 的大小。（2）它允许安全地整合各个局部设备由于系统异质性所导致的可变数量的本地工作。
完整的 FedProx 工作流程如下：
最后，作者提到，FedProx 只是对 FedAvg 进行了很小的修改，这使得我们能够对目前已经出现的大量的 FedAvg 方法/框架进行推理，将本文的改进方法与相关的方法/框架进行集成。特别的，也可以认为 FedAvg 是 FedProx 的一种特殊情况，（1）μ=0（2）局部优化使用 SGD（3）跨设备和更新轮次（即，不存在系统概念）的常数γ（对应于本地 epoch 的数量）。
【实验分析】
本文使用了合成数据和真实数据库（MINIST、FEMNIST、Shakespeare、Sent140）进行实验，使用 TensorFlow，以及 SGD 作为局部优化算子。对于每个数据集，调整 FedAvg 上的学习率（E=1 且不存在系统异质性），并对该数据集上的所有实验使用相同的学习率。对于所有数据集上的所有实验，将所选设备的数量设置为 10。基于全局目标函数 f(w) 衡量最终效果。图 14 给出在不同数据库中关于异质网络中收敛性的实验结果。通过比较 FedAvg 和 FedProx（μ=0），在存在系统异质性的情况下，允许各个设备执行可变的工作量有助于整体目标函数的收敛。将 FedProx（μ＝0）与 FedProx（μ＞0）进行比较，证明了所增加的修正项的优点。μ>0 的 FedProx 具有更稳定的收敛性，此外能够在存在系统异质性（50% 和 90% 离散）和不存在系统异质性（0% 离散）的情况下收敛。
图 14. 与 FedAvg 相比，FedProx 在异质网络中的收敛性得到了显著的改善
图 15 中的实验通过强制每个设备运行相同数量的 epoch（E）来消除系统异质性的影响。在这个设置中，FedProx（μ=0）将简化为 FedAvg。上面一行的图示中，给出四个统计异质性从左到右增加的合成数据集上的训练损失。其中，μ=0 的方法对应于 FedAvg 的实验结果。异质性的增加会导致更差的收敛性，但是当μ>0 时，能够缓解这一问题。下面一行图示显示了四个合成数据集的相应差异性度量（梯度方差）。该度量能够有效捕获数据统计异质性，由实验结果可知，该度量的趋势与训练损失一致；较小的差异表示更好的收敛性。
图 15. 数据异质性对收敛性的影响
文章小结
在这篇文章中，作者提出了 FedProx--一个解决联邦学习固有的系统和统计异质性问题的优化框架。FedProx 允许在设备之间局部地执行可变量的工作，并且依赖一个修正项来确保方法的稳定性。作者对一组联邦数据集的实证评估验证了其理论分析，并证明了 FedProx 框架可以显著改善现实异质网络中联邦学习的收敛行为。
作者介绍：仵冀颖，工学博士，毕业于北京交通大学，曾分别于香港中文大学和香港科技大学担任助理研究员和研究助理，现从事电子政务领域信息化新技术研究工作。主要研究方向为模式识别、计算机视觉，爱好科研，希望能保持学习、不断进步。