如何通过流水线来隐藏数据移动带来的延迟
我们知道数据移动带来的延迟是阻碍程序性能的一个非常重要的因素。广义上的数据移动包括几个不同的方面。它包括不同进程间的信息传递(MPI)，比如从一维弹簧系统谈多进程并行计算中提到的分散式矩阵矢量乘法。它也包括数据从慢速存储到高速存储的移动，一个例子是如何从Wall/CPU time理解多线程程序的并行效率一文中关注的IO时间，具体来讲是属于发生在主存和硬碟之间的数据移动，以及从2018戈登贝尔奖谈高性能计算提到的数据在不同层次缓存之间的移动。它还包括数据在异质结构中host和target机器之间的移动。
我们为什么如此关注数据移动？因为数据移动受延迟和带宽的限制，在高性能计算程序中往往属于不可并行或者很难并行的部分。那么如何来克服这一难点呢？除了采用更先进的硬体来降低数据移动的延迟和提高数据传输的带宽，我们在本文中讨论一个来自软体层面的方法。
首先定义一个高性能计算程序的抽象模型。如图1所示。我们把程序分成两个部分。其中一个是计算部分，我们假设这一部分是可被完美并行的，即使用n个计算单元，耗时缩短为原来的1/n。另外一个是数据的输入或者输出部分，它抽象了上文中提到的数据移动。为了讨论的方便，我们在模型中独立地看数据的输入和输出，从而得到了一个简单的生产者-消费者模型。这个模型在一定程度涵盖了前文中提到的针对不同层次而实现的并行模型(基于MPI、多线程和异质结构的并行计算)。我们先看两个例子。例如从2018戈登贝尔奖谈高性能计算中提到的深度学习，其中训练数据的输入可以看作图1中的生产者，对模型的训练看作是消费者。再例如传统的动力学模拟，计算部分变成了生产者，对给定时间步的数据输出变成了消费者。
假设运行图1中以IO为代表的数据移动部分需要的时间是S, 总的计算量是C（即串列运行计算部分时需要的时间），那么使用n个工作单元运行这个简化模型需要的时间就是S+ C/n。从 Amdahls law 知道，数据移动的耗时S决定了这一模型的理论加速比上限。随著工作单元的增加，数据移动必将变成效率提升的瓶颈。这是因为在这一计算模型中，增加新的工作单元并不能减少S。
在这一模型中，我们还合理地假设生产者和消费者运行在一个大的循环里面，它们在程序中会被执行很多次。那么如果重叠生产者和消费者的工作会对运行时间有什么提升？我们以图1中的第二个流程为例子，在图2中示例了这个效果。计算单元作为生产者得到结果后立即进行新的时间步的计算，与此同时输出单元作为消费者输出计算单元得到的结果。不难看出，我们实现了一个存在于生产者和消费者之间的流水线。
我们可以看到在这个新的模型中，程序的运行时间变成了 max{S, C/n}。从流水线的角度不难理解这个结果。流水线中最慢的一级决定了流水线的吞吐量。图2中流水线的深度是2，在最理想的状况下，程序运行效率和图1相比也会有2倍的提升。通过实现流水线，我们在某种程度上隐藏了数据移动带来的延迟。
那么在实际中会有哪些原因会让效率的提升无法达到这个理想状况呢？首先，如果流水线的各级没有平衡就会降低流水线的吞吐量。比如IO过于频繁，S>>C/n，那么图2的运行时间为 S， 和图1的运行时间S+ C/n~S相比，就不会有显著提高。我们再考虑一下这个问题：图2忽略了哪些细节？比如图2没有画出流水线各级之间的缓存，缓存需要存储空间，并且计算单元和输出单元需要在使用缓存上实现某种同步，这又是一个让我们无法达到理想状况的原因。
我们简单谈谈图2在实现上的一些细节和难点。首先是对一个多层次并行的程序，实现流水线有多个可能，比如进程的层面考虑使用 non-blocking message，线程层面考虑使用 explicit tasking。 那么应该在哪一个层面来做流水线？答案并不唯一。主要的考虑仍然是实现流水线的代价和收益。假设在层次i的工作单元（包括图2中的计算单元+输出单元）数目是 ，并且我们只需要1个工作单元就可以完成输出，那么在i层实现流水线的计算时间变为
。这提示我们在实现之前可以先画一张表格，列出各个层次的
。当然实际决策远比这个公式复杂，计算时间不会有著这么简单的公式，并且需要考虑在新的实现中如何达到负载均衡，还需要考虑是否实现更多层级的流水线来达到更大的加速比，此外还需要考虑除了计算时间之外的其他成本。因而实际决策往往是设计+实验的反复迭代过程。
和图2中的简单示例相比，实际问题中阻碍图2实现的最大障碍往往来自于代码重构的难度，尤其是当需要重构的代码有数万行甚至数百万行之大、负载开发代码的人员是一个团队的时候，如何让整个团队接受必须代码重构这一事实，并且用合适的步伐向著合理的方向前进，这远比程序本身更复杂。不得不承认，以 Amdahls law 为代表的广义的高性能计算准则在这种情况下仍然是成立的。
此外，如何采用新的演算法来减少数据移动，在节约系统功耗上有著更重要的意义。这对于运行在下一代E级超级计算机或者移动终端（比如智能手机）上的高性能应用程序尤为重要，甚至可能是成败的关键。
本文提到的流水线技术在底层硬体的设计中早已被广泛使用。做好高性能计算，除了深入理解来自应用层面的并行性，理解编译器、操作系统乃至硬体架构会变得至关重要。也许我们会发现高性能计算原理和方法在软硬体层面上是殊途同归的。引用一句话来总结这一发现：
「To solve problems at scale, paradoxically, you have to know the smallest details」
这句话来源于一个记录google团队开发过程的有趣博客：https://www.newyorker.com/magazine/2018/12/10/the-friendship-that-made-google-huge
推荐阅读：
