骆沁毅，美国南加州大学研究助理，在读博士生，研究方向为分布式机器学习和数据分析，本科毕业于清华大学电子系。在ASPLOS、MICRO、PLDI等顶会上发表数篇论文，曾获国家奖学金、WeTech高通奖学金、提名微软博士生奖学金等荣誉。

本次演讲中，骆沁毅带来了她和同事们发表在ASPLOS 2020上的最新作品——Prague[1]。这是一种在异构平台上进行高效机器学习分布式训练的方法，其特点是融合了目前的主流分布式训练算法All-Reduce和前沿算法AD-PSGD的优点，既能在同质环境下获得高性能，又具有良好的异质性容忍度。在本次演讲中，骆沁毅条理清晰地介绍了Prague的整个设计过程和它们背后的思考，包括：探索了算法和系统实现之间、统计效率与硬件效率之间的相互作用，以及深入的同步优化等。

 整理：智源 区陈凯、吴继芳、常政

一、背景介绍：机器学习分布式训练

近些年来机器学习已经渗透到 会的方方面面，对日常生活产生了广泛影响。为了使得机器学习模型达到足够高的精度，常用的方法是提高模型自身的复杂度以及采用更大规模的训练数据集。然而这使得模型训练成为一个非常耗时的工作。一般情况下，我们会通过分布式训练来加速模型训练过程。

所谓的分布式训练是把训练工作分配到多个机器（或者称之为Worker）上，每个Worker先是独立处理一部分工作，然后各Worker再进行同步，从而协调完成整个训练任务。根据任务分配和协调方式的不同，分布式训练可以分为四类：数据并行，模型并行，混合并行和流水线并行。

骆沁毅演讲中涉及的方法属于数据并行。和其它方式相比，数据并行具有较高的吞吐量，也被应用于多个机器学习框架中。简单来讲，在数据并行方式中，每个Worker都保有一个完整的模型副本。Worker先会在本地处理分配到的训练数据，比如计算梯度，然后再和其他Worker同步模型参数。

Parameter Server [2] (图1.a所示)，或简称为PS， 是一类传统的数据并行的实现方法。PS是一个中心化的结构，每一个Worker会把自己计算得到的梯度上传到中心节点，中心节点对所有Worker的梯度做平均化处理后，再传回各个Worker。作为中心化的结构，PS中存在中心节点通信瓶颈问题。且Worker数量越多，该问题越突出，这制约了PS的扩展能力。

All-Reduce [3] (图1.b所示)，采用了基于流水线式的同步方式，使得节点间的通信变得更加高效。图1.c则展示了基于去中心化式 (Decentralized) 的通信方式。

图2: All-Reduce和AD-PSGD在同构和异构平台上的性能比较

图4: 两个Worker同步操作出现冲突

三、Partial All-Reduce机制

如图4右半部分所示，出现两个Worker同步操作冲突的情况下，相应的参数平均化操作依然可以通过矩阵来表示。既然如此，为何不通过一次联合同步来代替两次单独的同步来降低同步开销呢，既然两次同步可能以任意的顺序发生，比如可能是Worker0先和Worker3同步，也可能是Worker4先和Worker3同步，因此如图4所示，Worker0和Worker4收到不同参数的做法不符合常理。

鉴于上述分析，骆沁毅在Prague中使用了基于组的Worker同步机制，也就是Partial All-Reduce (简称为P-Reduce) 机制。P-Reduce采用图5中所示的参数平均化矩阵。

图6：Worker从Group Generator获取组信息过程

Group Generator设计的关键点在于如何生成组，组的质量和数量会直接决定同步的速度。针对于生成组主要考虑两个问题，第一是组间冲突（Conflict）问题，第二是Straggler问题。

1. 避免组间冲突

组间冲突（Conflict）是指不同组的Worker有重叠，这些组在执行P-Reduce操作时仍然需要满足原子性（即串行操作）。这也是Group Generator采用中心化组织的原因，如果每个Worker自己生成组，产生Conflict的可能性非常大，需要多轮communication才能消除冲突。虽然采用中心化组织，Worker和GG之间也需要通信，但是交互信息非常小，不会导致通信或者规模瓶颈。Group Generator减少冲突的方法有两种：Fixed Schedule 和 Randomized Schedule。

固定调度 (Fixed Schedule)

Fixed Schedule即Static GG，手动实现无冲突的分组。通过多轮实验，发现好的Schedule是周期性的。图7中展示了一个周期 Schedule，交替于Inter phase和Intra phase之间。图中有16个Worker，W0-W3、W4-W7、W8-W11、W12-W15分别属于不同的Node。Inter phase 是指会有node之间的Worker communication。Intra phase是指node内部的Worker communication，在node内部communication可以加快执行速度。图中第一个iteration是Inter phase, 所以G5中的Worker 在不同的node上。下一个iteration是Intra phase，所以每个组中的Worker都在同一个node上。

图8：随机调度策略

图10：Threshold Rule 定义

四、系统实现

Pargue基于TensorFlow实现，其中：P-Reduce使用NCCL作为后端，通过MPI创建NCCL communicator；GG使用gRPC python 包实现。实现两个版本的Pargue系统，分别是：

1. Static GG：手动设计 Group Schedules。

2. Smart GG：实现前面提到的 Randomized Schedules, 包括randomized group division, inter-intra synchronization 和 threshold rule。

同时，实现两个baseline 算法，分别是：

All-Reduce：Horovod with NCCL backend on TensorFlow,

AD-PSGD：TensorFlow remote variable access。

五、实验与结果

1. 实验过程

在图像和自然语言处理领域都进行了实验，使用的模型和数据集为：

1. Vision：VGG-16 on CIFAR-10；Resnet-18、Resnet-50和Resnet-200 on ImageNet。

2. NLP：Transformer on News-Commentary dataset。

硬件环境：GTX partition in the Maverick2 cluster of TACC Super Computer（4 GPUs/node），共有16个Workers，分布在4个nodes上，每个node有4个Workers, 每个Worker占用一个GPU。同时，针对Resnet-50，在8个GTX nodes（32个Workers）上也进行了实验。

在实验中，通过人工随机添加slowdown，即在每个iteration中，每个Worker以1/#Workers的概率随机slowing down。每个Worker slowing down 的概率是相互独立的。

2. 实验结果

① 吞吐量：分为有slowdown和没有slowdown两种情况，结果如图11所示。

图12：Speedup w.r.t. time to reach the same loss (VGG-16)

图中展示了四个算法在不同的异构性平台上训练模型的效率。其中，蓝色代表没有slowdown，橙色代表有2倍slowdown， 灰色代表有5倍slowdown。纵坐标是Speedup，数值越高表示性能越好。从图中可以看出当存在slowdown时，All-Reduce影响比较明显。AD-PSGD对slowdown不敏感，基本无影响。但是AD-PSGD 本身存在Communication Overhead的问题，在没有slowdown的情况下，效果并没有All-Reduce那么好。Static GG在有slowdown的情况下，也受到很明显的影响。Smart GG在没有slowdown的情况下达到与All-Reduce相近的效果，同时又在有slowdown的情况下相较于All-Reduce有更好的对抗Straggler的能力。

③ 模型准确率：最终得到的模型的准确率，结果如图13所示。

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35190 人正在系统学习中