并行计算的量化模型及其在深度学习引擎里的应用
撰文｜袁进辉
天下武功，唯快不破。怎么更快地训练深度学习模型是业界一直关注的焦点，业界玩家或开发专用硬件，或开发软件框架，各显神通。本文将介绍对深度学习计算效率最关键的一些基本定律，这有助于用户理解深度学习引擎的瓶颈在哪里以及如何解决这些挑战。
当然，这些定律在计算机体系结构的教材和文献中都可看到，譬如这本《计算机体系结构：量化研究方法（Computer Architecture: a Quantative Approach）》，但本文的价值在于有针对性地挑选最根本的几条定律，并结合深度学习引擎来理解。
1、关于计算量的假定
在研究并行计算的定量模型之前，我们先做一些设定。对于一个具体的深度学习模型训练任务，假设总的计算量 V 固定不变，那可以粗略认为只要完成 V 这个量级的计算，深度学习模型就完成训练。
GitHub 这个页面（https://github.com/albanie/convnet-burden）罗列了常见 CNN 模型处理一张图片所需的计算量，需要注意的是，本页面列出的是前向阶段的计算量，在训练阶段还需要后向阶段的计算，通常后向阶段的计算量是大于前向计算量的。这篇论文（https://openreview.net/pdf?id=Bygq-H9eg）对训练阶段处理一张图片的计算量给出了一个直观的可视化结果：
以 ResNet-50 为例，训练阶段处理一张 224X224x3 的图片需要 8G-Ops （约 80 亿次计算），整个 ImageNet 数据集约有 120 万张图片，训练过程需要对整个数据集合处理 90 遍（Epochs），粗略估计，训练过程共需要(8*10^9) *(1.2*10^6)* 90 = 0.864*10^18 次运算，那么 ResNet-50 训练过程的总计算量大约是 10 亿乘以 10 亿次运算，我们可以简单地认为，只要完成这些计算量就完成了模型运算。深度学习计算引擎的目标是以最短的时间完成这个给定的计算量。
2、关于计算装置的假定
本文仅限于下图所示的以处理器为中心的计算装置（Processor-centric computing)，以内存为中心的计算（Processing in memory）装置在业界有探索，但还不是主流。
上图所示的计算装置中 Computing Unit 可以是通用处理器如 CPU, GPGPU, 也可以是专用芯片如 TPU 等。如果 Computing Unit 是通用芯片，通常程序和数据都存储在 Memory Unit，这也是现在最流行的冯诺依曼结构计算机。
如果 Computing Unit 是专用芯片，通常只有数据存储在 Memory Unit。Communication Unit 负责把数据从 Memory Unit 搬运给 Computing Unit，完成数据加载（load），Computing Unit 拿到数据后负责完成计算（数据的形式转换），再由 Communication Unit 把计算结果搬运到 Memory Unit 完成数据存储（Store）。
Communication Unit 的传输能力通常用访存（Memory access）带宽 beta 表示，即每秒钟可以搬运的字节数，这通常和线缆数和信号的频率相关。Computing Unit 的计算能力通常用吞吐率 pi 表示，即每秒钟可以完成的浮点计算次数（flops），这通常和计算单元上集成的逻辑运算器件个数及时钟频率有关。
深度学习引擎的目标是通过软硬件协同设计使得该计算装置处理数据的能力最强，即用最短的时间完成给定的计算量。
3、Roofline Model: 刻画实际计算性能的数学模型
一个计算装置执行一个任务时能达到的实际计算性能（每秒钟完成的操作次数）不仅与访存带宽 beta 以及计算单元的理论峰值 pi 有关，还和当前任务本身的运算强度（Arithemetic intensity，或 Operational intensity）。
任务的运算强度定义为每字节数据需要的浮点计算次数，即 Flops per byte。通俗地理解，一个任务运算强度小，表示 Computing Unit 在 Communication Unit 搬运的一个字节上需要执行的运算次数少，为了让 Computing Unit 在这种情况下处于忙碌状态，Communication Unit 就要频繁搬运数据；
一个任务运算强度大，表示 Computing Unit 在 Communication Unit 搬运的一个字节上需要执行的运算次数多，Communication Unit 不需要那么频繁地搬运数据就能使 Computing Unit 处于忙碌状态。
首先，实际计算性能不会超越计算单元的理论峰值 pi。其次，假如访存带宽 beta 特别小，1 秒钟仅能把 beta 个字节从内存搬运到 Computing Unit，令 I 表示当前计算任务中每个字节需要的操作次数，那么 beta * I 表示 1 秒钟内搬运过来的数据实际需要的操作次数，如果 beta * I < pi，则 Computing Unit 就不会饱和，也表示 Computing Unit 的利用率低于 100%。
Roofline model 就是一种根据访存带宽，计算单元峰值吞吐率，任务的运算强度三者关系来推断实际计算性能的数学模型。由 David Patterson 团队在 2008 年发表在 Communications of ACM 上（https://en.wikipedia.org/wiki/Roofline_model），是一种简洁优雅的可视化模型：
图 1：Roofline Model
图 1 横轴的自变量表示不同任务的运算强度，即每字节需要的浮点运算次数。纵轴的因变量表示实际可达的计算性能，即每秒钟执行的浮点运算次数。上图展示了两个运算强度分别为 I_1 和 I_2 的任务能实际达到的计算性能，I_1 的运算强度小于 pi/beta，称为访存受限任务，实际计算性能 beta * I_1 低于理论峰值 pi。
I_2 的运算强度高于 pi/beta，称为计算受限型任务，实际计算性能达到理论峰值 pi，访存带宽仅利用了 pi/(I_2*beta)。图中斜线的斜率为 beta，斜线和理论峰值 pi 水平线的交点称为脊点（Ridge point），脊点的横坐标是 pi/beta，当任务的运算强度等于 pi/beta 时，Communication Unit 和 Computing Unit 处于平衡状态，哪一个都不会浪费。
回顾深度学习引擎的目标“以最短的时间完成给定的计算量”，就要最大化系统的实际可达的计算性能。为了实现这个目标，有几种策略可用。
图 1 中的 I_2 是计算受限型任务，可以通过增加 Computing Unit 的并行度并进而提高理论峰值来提高实际计算性能，譬如在 Computing Unit 上集成更多的运算逻辑单元（ALU）。具体到深度学习场景，就是增加 GPU，从一个 GPU 增加到几个 GPU 同时运算。
如图 2 所示，当在 Computing Unit 内增加更多的并行度后，理论峰值高于 beta * I_2，那么 I_2 的实际计算性能就更高，只需要更短的时间就可以。
图 2：提高 Computing Unit 的理论峰值来提高实际计算性能
图 1 中的 I_1 是访存受限型的任务，则可以通过改善 Communication Unit 的传输带宽来提高实际计算性能，提高数据供应能力。如图 3 所示，斜线的斜率表示 Communication Unit 的传输带宽，当斜线的斜率增大时，I_1 由访存受限型任务变成计算受限型任务，实际计算性能得到提高。
图 3：提高 Communication Unit 的数据供应能力来提高实际计算性能
除了通过改善硬件的传输带宽或者理论峰值来提高实际计算性能外，还可以通过改善任务本身的运算强度来提高实际计算性能。同样的任务可以有多种不同的实现方式，不同实现方式的运算强度也存在差别。运算强度由 I_1 改造成超过 pi/beta 后，就变成计算受限型任务，实际计算性能达到 pi，超过原来的 beta*I_1。
在实际的深度学习引擎里，以上三种手段（提高并行度，改善传输带宽，使用运算强度更好的算法实现）都会用到。
4、Amdahl's Law: 如何计算加速比？
图 2 的示例通过增加 Computing Unit 的并行度来提高实际计算性能，到底能把任务的执行时间缩短多少呢？这就是加速比问题，也就是效率提高了几倍。
为了讨论方便，（1）我们假设当前的任务是计算受限型，令 I 表示运算强度，即 I*beta>pi。在把 Computing Unit 的运算单元增加 s 倍后，理论计算峰值是 s * pi，假设该任务的运算强度 I 足够高，使得在理论峰值提高 s 倍之后仍是计算受限型，即 I*beta > s*pi；（2）假设没有使用流水线，Communication Unit 和 Computing Unit 总是顺序执行（后文我们将专门讨论流水线的影响）。让我们来计算一下任务执行效率提高了几倍。
在理论峰值是 pi 的初始情况下，1 秒钟 Communication Unit 搬运了 beta 字节的数据，Computing Unit 需要(I*beta)/pi 秒来完成计算。即在 1+(I*beta)/pi 秒时间内完成了 I*beta 的计算，那么单位时间内可以完成（I*beta) / (1 + (I*beta)/pi) 的计算，假设总计算量是 V，则一共需要 t1=V*(1+(I*beta)/pi)/(I*beta) 秒。
通过增加并行度把理论计算峰值提高 s 倍之后，Communication Unit 搬运 beta 字节的数据仍需要 1 秒钟，Computing Unit 需要(I*beta)/(s*pi)秒来完成计算。假设总计算量是 V，那么共需 t2=V*(1+(I*beta)/(s*pi))/(I*beta)秒完成任务。
计算 t1/t2 即获得加速比：1/(pi/(pi+I*beta)+(I*beta)/(s*(pi+I*beta)))，很抱歉这个公式比较难看，读者可以自己推导一下，比较简单。
在理论峰值是 pi 时，搬运数据花了 1 秒，计算花了(I*beta)/pi 秒，那么计算时间占的比例是 (I*beta)/(pi + I*beta)，我们令 p 表示这个比例，等于(I*beta)/(pi + I*beta)。
把 p 代入 t1/t2 的加速比，可以得到加速比为 1/(1-p+p/s)，这就是大名鼎鼎的 Amdahl's law（https://en.wikipedia.org/wiki/Amdahl%27s_law）。其中 p 表示原始任务中可以被并行化部分的比例，s 表示并行化的倍数，则 1/(1-p+p/s)表示获得的加速比。
让我们用一个简单的数字演算一下，假设 Communication Unit 搬运数据花了 1 秒钟，Computing Unit 需要用 9 秒钟来计算，则 p=0.9。假设我们增强 Computing Unit 的并行度，令其理论峰值提高 3 倍，即 s=3，则 Computing Unit 只需要 3 秒钟就可以完成计算，那么加速比是多少呢？利用 Amdahl's law 可以得知加速比是 2.5 倍，加速比 2.5 小于 Computing Unit 的并行度倍数 3。
我们尝到了增加 Computing Unit 并行度的甜头，能不能通过进一步提高并行度 s 来获得更好的加速比呢？可以。譬如令 s=9，那么我们可以获得 5 倍加速比，可以看到提高并行度的收益越来越小。
我们能通过无限提高 s 来提高加速比吗？可以，不过越来越不划算，试想令 s 趋于无穷大（即令 Computing Unit 理论峰值无限大），p/s 就趋于 0，那么加速比最大是 1/(1-p)=10。
只要系统中存在不可并行的部分（Communication Unit），加速比不可能超过 1/(1-p)。
实际情况可能比加速比上限 1/(1-p)要更差一些，因为上述分析假设了运算强度 I 无穷大，而且在增加 Computing Unit 并行度时，通常会使得 Communication Unit 的传输带宽下降，就使得 p 更小，从而 1/(1-p）更大。
这个结论令人很悲观，即使通信开销（1-p）只占 0.01,也意味着无论使用多少并行单元，成千上万，我们最大只能获得 100 倍的加速比。有没有办法让 p 尽可能接近 1，也就是 1-p 趋近于 0，从而提高加速比呢？有一枚灵丹妙药：流水线。
5、Pipelining: 灵丹妙药
在推导 Amdahl's law 时，我们假设了 Communication Unit 和 Computing Unit 串行工作，总是先令 Communication Unit 搬运数据，Computing Unit 再做计算，计算完成再令 Communication Unit 搬运数据，再计算，如此循环往复。
能不能让 Communication Unit 和 Computing Unit 同时工作，一边搬运数据一边计算呢？如果 Computing Unit 每计算完一份数据，就立刻可以开始计算下一批数据，那么 p 就几乎是 1，无论并行度 s 提高多少倍，都能获得线性加速比。让我们研究一下什么条件下可以获得线性加速比。
图 4：（同图 1）Roofline Model
图 4 中的 I_1 是通信受限型任务，1 秒钟 Communication Unit 可以搬运 beta 字节的数据，处理这 beta 字节 Computing Unit 需要的计算量是 beta*I_1 次操作，理论计算峰值是 pi，一共需要(beta*I_1)/pi 秒完成计算。
对于通信受限型任务，我们有 beta*I_1<pi，所以 Computing Unit 的计算时间是小于 1 秒的。这也就意味着不到 1 秒的计算却需要花 1 秒钟的时间搬运数据，那么计算时间就无法掩盖住数据搬运时间，p 最大可以做到（beta*I_1)/pi，加速比最大是 1/（pi-beta*I_1)。
图 4 中的 I_2 是计算受限任务，1 秒钟 Communication Unit 可以搬运 beta 字节的数据，处理这 beta 字节 Computing Unit 需要的计算量是 beta*I_2 次操作，理论计算峰值是 pi，一共需要(beta*I_2)/pi 秒完成计算。对于计算受限型任务，我们有 beta*I_2>pi，所以 Computing Unit 的计算时间是大于 1 秒的。
这也就意味着，每花 1 秒钟搬运的数据需要好几秒才能计算完，在计算的时间内有充足的时间去搬运下一批数据，也就是计算时间能掩盖住数据搬运时间，p 最大是 1，只要 I 是无穷大，加速比就可以无穷大。
使得 Communication Unit 和 Computing Unit 重叠工作的技术叫流水线（Pipelinging: https://en.wikipedia.org/wiki/Pipeline_(computing)）。是一种有效地提高 Computing Unit 利用率和提高加速比的技术。
6、并行计算的量化模型对深度学习引擎的启发
上文讨论的各种量化模型对深度学习引擎研发同样适用，譬如对于计算受限型任务，可以通过增加并行度（增加显卡）来加速；即使是使用同样的硬件设备，使用不同的并行方法（数据并行，模型并行或流水线并行）会影响到运算强度 I，从而影响实际计算性能；分布式深度学习引擎包含大量的通信开销和运行时开销，如何减小或掩盖这些开销对于加速效果至关重要。
在 Processor-centric 计算装置的视角下理解基于 GPU 训练深度学习模型，读者可以思考一下怎么设计深度学习引擎来获得更好的加速比。
在单机单卡情况下，只需要做好数据搬运和计算的流水线，就可以做到 GPU 100%的利用率。实际计算性能最终取决于底层矩阵计算的效率，也就是 cudnn 的效率，理论上各种深度学习框架在单卡场景不应该存在性能差距。
如果想在同一台机器内部通过增加 GPU 来获得加速，与单卡场景相比，增加了 GPU 之间数据搬运的复杂性，不同的任务切分方式可能会产生不同的运算强度 I（譬如对卷积层适合做数据并行，对全连接层适合模型并行）。除了通信开销，运行时的调度开销也会影响加速比。
多机多卡场景，GPU 之间数据搬运的复杂性进一步提高，机器之间通过网络搬运数据的带宽一般低于机器内部通过 PCIe 搬运数据的带宽，这意味着并行度提高了，可数据搬运带宽降低了，代表着 Roofline model 中斜线的斜率变小了，CNN 这种适合数据并行的场景通常意味着比较高的运算强度 I，而还有一些模型譬如 RNN/LSTM，运算强度 I 就小很多，这也意味着流水线中的通信开销更难以掩盖了。
7、总结
有用过分布式深度学习引擎的读者应该对软件框架的加速比有切身的体会，基本上，卷积神经网络这种适合数据并行（运算强度 I 比较高）的模型通过增加 GPU 来加速的效果还是比较令人满意的，然而，还有很大一类神经网络使用模型并行的运算强度才更高一点，而且即使使用模型并行，其运算强度也远低于卷积神经网络，对于这些应用如何通过增加 GPU 并行度来获得加速是业界尚未解决的难题。
在之前的深度学习评测中，甚至发生了使用多 GPU 训练 RNN 速度比单个 GPU 还要慢的情况（https://rare-technologies.com/machine-learning-hardware-benchmarks/）。无论使用什么技术解决深度学习引擎的效率问题，万变不离其宗，为了提高加速比，都是为了减小运行时开销，选择合适的并行模式来提高运算强度，通过流水线掩盖通信开销，也都在本文描述的基本定律涵盖的范围之内。
（本文完成于 2018 年初，文中所举例子已比较陈旧，但不影响原理的阐释。）
其他人都在看
欢迎下载体验 OneFlow v0.7.0 最新版本：https://github.com/Oneflow-Inc/oneflow/
不至于成为世界上最快的深度学习框架。 2022.03.23 加入
★ OneFlow深度学习框架：github.com/Oneflow-Inc/oneflow ★ OF云平台：oneflow.cloud
评论