What drives performance improvement of Deep Learning Models in recent years

这一周主要是看论文，浏览了今年MLSys，ASPLOS以及去年SOSP和前年OSDI上与系统和机器学习相关的文章，重点阅读了一些与深度学习的性能提升相关的文章。受到之前包老师推荐阅读的文章（There’s plenty of room at the Top）的影响，我把这些文章分为三类，分别是Algorithm、Software和Hardware Architecture。由于我关注的这些会议都是偏系统的，所以Software层面的文章比较多。

Algorithm

在这几个会议中，我看到了两篇关于算法层面的文章，都出自MLSys 2020。

其中BPPSA (MLSys 2020)对神经网络反向计算梯度的过程中普遍采用的Back Propagation算法，进行了新的设计。利用一个现有的Blelloch scan algorithm算法，将梯度计算过程转化为scan操作，从而将BP算法的复杂度从O(n) 降到 O(log n)， 提高了反向计算梯度时的性能。

SLIDE (MLSys 2020) 这篇文章的标题就很有意思： In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems。 这篇文章指出了现在深度学习领域的一个趋势，就是对于基础的矩阵乘法等操作的优化已经达到了瓶颈，而深度学习算法本身又没有太多的发展，导致大家都开始研究专用于深度学习加速的硬件，而研发硬件不仅成本巨大，还很有风险，因为一旦上层的算法发生改变，可能之前的硬件架构就不能实现很好的利用率。因此这篇文章仍然尝试从算法层面对深度学习的性能进行优化。这篇文章采用了Adaptive dropout + Locality Sensitive Hash (LSH) table（一种在梯度更新过程中动态进行dropout的操作），并结合了HOGWILD（一种异步更新的SGD算法），从而在一个44核CPU上实现了Tesla V100 GPU 3.5倍的性能。

Software

在软件层面对深度学习模型的性能提升，自底向上可以分为：operator-level, graph-level, task-level。Operator-level的提升，包含cuDNN这样的加速库，从算子的实现层面进行了加速，但这类的工作比较少；graph-level的工作就是对神经网络的机构进行优化，这类工作也比较少；最多的优化是在task-level进行的，这个task-level是我自己总结的，在这里，一个task可以认为是神经网络训练或者推理过程中的一次前向计算或者反向参数更新（对于某些对神经网络进行划分的工作，这个task的粒度要小一些），很多工作就是不去看神经网络的底层实现细节，从task-level来进行任务的调度和分布式部署。

对于operator-level，我在这几个会议中只看到了TVM(OSDI 2018) 这一篇文章，从编译器的角度，针对不同的op生成优化后的代码。而在graph-level，TVM同样也进行了一定程度的，对神经网络计算图的优化。除此之外，就是Jia Zhihao发表的TASO (SOSP 2019) ，通过设计了一些神经网络子图的替换规则，利用回溯搜索的算法，自动生成替换后的网络结构。

下面主要分析task-level的工作。

在task-level，我们说的对“神经网络性能的提升”，也包括好几个场景，分别是超参数调优过程、训练阶段和推理阶段。这几个场景具有各自不同的特点，因此需要针对性地进行系统的设计。

超参数调优过程，会在很多组不同的神经网络参数甚至不同的神经网络结构下进行计算，评估模型的准确率，找出最优的参数组合，这其中运行的每一个任务的收敛性、模型结构和大小、资源占用情况可能都不相同，对于某些收敛性很差的参数组合，可能还需要提前终止来节省时间开销。

训练阶段是在一组已经确定的参数组合下，迭代地进行大量重复运算，每一次迭代都会更新模型中的参数，由于神经网络算法内在的数据依赖性，导致不同迭代周期之间难以并行，而同一迭代周期内的数据并行又会引入大量时间开销。

推理阶段虽然可以看做是一次训练阶段的前向计算过程，但推理往往发生在云服务器中，训练好的模型被用于处理大量的prediction query，这个场景需要关注的就不是运算性能，而是延迟、QoS等指标。同时，推理也会发生在各种移动设备端或者嵌入式设备中，在资源受限的情况下，如何保证低功耗和推理精度，也是大家比较关心的问题。

• 超参数调优

  在MLSys 2020上有两篇关于超参数调优的文章，其中一篇（FLEET）将超参数调优问题归纳为ensemble training， 在ensemble training中，训练一组结构相同的网络，称为homogeneous ensemble， 否则称为heterogeneous ensemble。 heterogeneous ensemble存在两个挑战：不同网络的训练速率不同，这会导致整个集群需要等待较慢的任务完成后才能释放某些硬件资源，资源利用率较低；收敛速率不同，也会导致硬件利用率较低。因此作者将这个问题转化为一个最优资源分配问题，通过提出一个高效的贪心算法，以及对DNN任务进行分组，FLEET实现了高效的资源分配和数据传输。

• 训练阶段

  对于训练阶段的性能提升，很多工作是对任务的划分和调度方式进行了设计。例如Generic Communication Scheduler (SOSP 2019) 通过对tensor进行细粒度的划分和按照优先级调度，从而提升了模型训练的性能。 PipeDream (SOSP 2019) 在模型并行的训练中引入了流水线机制，通过batch之间的并行，从而提高了硬件利用率，减少了训练时间。

  另一些工作则是从数据传输的角度来进行优化。目前广泛使用的数据并行在单机多卡的场景下，往往采用All-reduce算法来进行参数同步，All-reduce的后端往往采用NVIDIA提供的NCCL库。BLink (MLSys 2020) **针对NVLink场景中，NCCL库存在的缺陷进行优化，采用了packing spanning trees算法，从而进一步提高带宽利用率。Prague (ASPLOS 2020) 针对异构环境下的分布式训练，提出了新的Partial All-reduce原语，避免了All-reduce存在的straggler问题，并且提出了新的分组和调度算法，对异构环境有更好的适应性。PLink (MLSys 2020)** 则主要关注云服务器端的分布式训练，主要包含三个模块：ProbeEmbed用于探索集群中的网络拓扑结构，AggEngine根据拓扑信息，对workloads进行聚集，生成balanced部署方案，Autotune用于在网络条件变化时动态调整。

  除了提升训练性能，很多工作也提高了集群硬件资源利用率。Gandiva (OSDI 2018) 是针对GPU设计的调度器，作者根据神经网络任务的资源占用周期性，对GPU进行时间分片，并且加入了高效的任务换出机制，让不同的任务周期性地使用GPU，从而提高GPU的利用率。Salus（MLSys 2020）针对现阶段GPU任务调度中存在的粒度过大的问题，提出了细粒度GPU共享原语：fast job switching and memory sharing， 前者可以实现高效的GPU时间共享和抢占，后者通过将大量小的DL任务打包，保证了内存的使用率。Resource Elasticity in Distributed Deep Learning (MLSys 2020) 指出传统的机器学习框架，例如TensorFlow建立在固定的资源分配基础之上，一个任务往往与一定数量的资源绑定，直到这个任务计算完成，这并不能实现灵活的资源分配。而分布式场景下固定的资源分配可能会导致较低的利用率，集群中可能存在的straggler也可能导致整体性能下降，因此需要动态调整资源的分配。这篇文章在Tensorflow之上实现了一个动态调整资源分配的模块，提高了总体资源利用率，解决了straggler的问题。

• 推理阶段

  对于推理阶段，研究者主要关注大规模推理系统以及边缘计算设备中的推理性能。

  对于大规模推理系统，Parity model (SOSP 2019) **关注的是推理系统可能由多个分布式节点组成，系统可能遭受尾延迟的影响从而导致服务质量下降。作者提出用erasure code来对用户的query进行编码，从而通过很少的额外空间开销减少了尾延迟的影响。Willump (MLSys 2020)** 则指出目前的推理系统没有利用深度学习负载的特性，由于深度学习模型的计算存在模糊性，我们可以在推理系统中构造一个简单模型，只计算一部分feature，用于区分简单的数据；对于Top-K类型的query，可以先通过近似计算排除分数低的elements，再使用深度学习模型计算分数较高的elements，从而提升推理性能。PRETZEL (OSDI 2018) 指出目前的大规模推理系统主要关注易于部署的问题，通常把模型本身当做一个黑盒子部署到容器中来执行，在黑盒模型下，深度学习模型本身的流水线特性不能被利用，只能从caching, batching and buffering 角度来优化性能。

  对于嵌入式设备，MNN (MLSys 2020) 是一个移动设备的通用推理引擎，主要解决了移动端推理的两大挑战：通用性和效率。通用性包括要兼容来自不同深度学习框架训练出的模型，以及要兼容不同的硬件设备；在推理效率的前提下还要尽可能节省硬件资源。SkyNet (MLSys 2020) 是针对嵌入式设备的硬件资源限制，自下而上地设计的高效推理网络，用于嵌入式设备的目标检测。**Memory-Driven Mixed Low Precision Quantization (MLSys 2020) **按照不同的tensor进行不同精确度的量化，既满足嵌入式设备的内存限制，又最大程度保证模型精度。

Hardware Architeture

这几个会议上关于深度学习硬件体系结构的工作比较少，主要看到了以下3篇：DNNGuard (ASPLOS 2020) **是为了提高深度学习硬件的安全性，提出的一种新的硬件架构，能够在运行原始模型的同时，运行另一个攻击检测模型，在保证运算性能的同时，提高深度学习模型的安全性。OPTIMUS (MLSys 2020)是专门为了加速Transformer 模型（一个常用于翻译的循环神经网络）的推理而提出的硬件结构。作者通过分析算法原理，跳过冗余计算，提高MAC(乘加器)的利用率。PoET-BiN (MLSys 2020)** 是在FPGA上利用LUT结构搭建二元神经网络。

在浏览这几个会议的文章时，虽然我主要关注性能相关的文章，不过也注意到了一些比较有意思的其他主题：

• 一个趋势：内存很有限

  随着神经网络研究的深入，人们开始训练高精度图像、超长的语言序列、3D点云数据等等。这些训练数据往往会占用大量的内存。内存占用主要是由网络各个layer的中间结果（intermediate activations）造成的，因为这些中间结果会被用于计算梯度值，所以会在一次迭代周期的整个过程中被存在内存中。（这也限制了PipeDream没办法进一步提高硬件利用率）。

  GPU上的有限内存使得人们不能在这样的数据上采用复杂的网络结构或者较大的batch size。于是出现了一种解决方案，就是tensor rematerialization。可以在前向计算过程中释放中间结果，在计算梯度需要用到时，再通过一定的计算把这些中间结果重新算出来。而这会引入额外的计算时间。Checkmate (MLSys 2020)，通过一种近似算法寻找最优的tensor rematerialization方案，从而最小化总体的额外运算时间。

  图神经网络(GNN)处理的单个数据也比较大，使其难以进行大规模的训练和推理。ROC (MLSys 2020)是针对图神经网络（GNN）提出的分布式多GPU训练和推理框架。由于分布式训练，图神经网络中往往存在大量的数据传输，通过对图中每个顶点的设备做一定的规划，可以减少总的数据传输开销。（动态规划算法）

• 针对强化学习的框架

  Ray（OSDI 2018）是针对强化学习提出的一个分布式训练、模拟、推理框架。因为强化学习任务往往需要由某些设备与实际环境发生交互，因此存在端云结合的分布式场景。并且，强化学习任务往往包含大量的细粒度计算，以及异构的计算，运算时间以及资源的利用情况差别很大，传统的机器学习框架往往是为大量的、重复的计算任务设计的（例如Tensorflow，主要是为监督学习设计的，其计算任务往往包含大量的、迭代的计算）并不能很好地适用于这类情况。

• 联邦学习 Federated Learning

  随着终端设备计算能力的提高以及人们对隐私和安全性的重视，用户在本地更新、训练模型成为一大趋势，但由于单个用户往往不能持有训练的全部数据，可能会由多个用户联合，在本地，分布式地训练一个模型，这就是联邦学习。联邦学习与传统的分布式训练最大的区别在于high degrees of systems and statistical heterogeneity（每个用户持有的数据以及设备的性能存在很大差别）。Federated Optimization in Heterogeneous Networks (MLSys 2020) 通过在现有的联邦学习框架中增加对设备异构性的支持，解决了联邦学习过程中，算法收敛性得不到保证的问题。