.. Kenneth Lee 版权所有 2019-2020
:Authors: Kenneth Lee :Version: 1.0
流水线深度
这两天和人对这个问题的定义有争议，我通过本文理顺这个逻辑链。
问题如下：
有一组相同的互不相关的计算ops，每组计算都需要一个确定大小的buffer才能完成，这些 计算复用同一组计算单元，一定程度上可以并行（比如ops复用三个计算单元unit1, unit2, unit3，在计算过程中，ops[1]在使用unit1的时候，ops[2,3]可以同时使用unit2 和unit3）。为了提升计算效率，我们使用多个buffer来提高计算效率。比如有10个ops， 我们使用3个buffer，那么，我们可以让ops[0]使用buffer[0]，ops[1]使用Buffer[1]， ops[2]使用Buffer[2]，等ops[0]-buffer[0]计算完成，投入计算ops[3]-buffer[0]，然后 等ops[1]-Buffer[1]计算完成，投入计算ops[4]-Buffer[1]，...如此类推，直到所有的 ops全部计算完成。
这个计算过程可以简单表述如下：::
for i in [0..n] with buffers(m):
ops[i]
现在的问题是，这是否是一个流水线问题，如何定义这个问题的流水线深度。
wiki上对计算机流水线的定义如下：
| In computing, a pipeline, also known as a data pipeline,
| is a set of data processing elements connected in series,
| where the output of one element is the input of the next
| one. The elements of a pipeline are often executed in
| parallel or in time-sliced fashion. Some amount of buffer
| storage is often inserted between elements.
实践中的流水线包括：指令流水线，图形流水线，软件流水线，HTTP流水线等等。它们的 本质上都是在比喻生产线上的流水线——保证生产线上的每个工人都完成单一的工作，并且 不会闲着。
我们类比着考量一下：比如一个快餐店，为了服务一个顾客，你需要给他打饭，打菜，装 汤三个步骤。你有3个工人。
你一种选择是：三个工人每人都串行完成三个工作。这种是多线程。我们基于顾客进行调 度。这种我们就不会称为流水线。它的缺点是三个员工每个都要占据一套完整的打饭，打 菜和装汤的工具，而且没法专注。
你还有第二种选择：你需要一个人打饭，一个人打菜，一个人装汤，所有用户一起排队， 第一个人给第一个顾客打饭，然后给第二给顾客打饭，而第二个人等他给第二个顾客服务 的时候，开始服务第一个顾客的打菜，这样，整个工作也能并行起来。只是启动阶段有点 浪费，类似这样（Tn表示第n个时间slot）：
.. figure:: _static/食堂流水线.jpg
无论顺着横轴还是纵轴看，可以发现，除了开始阶段，每个顾客都没有等待，每个员工也 没有闲着。流水线可以实现类似多线程模型的并行度，但没有前面提到的多线程模型的浪 费问题。
如果我们单独从员工的时间线上看这个过程是这样的：
.. figure:: _static/食堂流水线2.jpg
可以看到，在流水线运行起来后，它几乎可以达到多线程一样的效果，但每个员工都不需 要是多功能的。
Wiki上没有定义“流水线深度”这个概念，但很多CPU设计的教材中，都提到这个概念，并把 执行体（对应上面的员工）的数目，称为流水线深度。我认为这只是一种方便的表述。因 为执行体的数量和“深度”这个概念没有什么可比性。从上面你那个图可以看到，“并行的执 行序列”的数量，才是流水线的“深度”，但在现在的情形中，明显流水线的深度等于执行行 体的个数。
相对多线程模型，流水线模型简化了每个执行单元的复杂度，但它是有明显缺陷的：当每 个执行体的执行时间不一样的时候，每个“并行序列”就不可能执行得这么高效。比如，假 如打菜需要两倍于打饭和装汤的时间，就会有很多等待：
.. figure:: _static/食堂流水线3.png
这一点我们是需要知道的。
现在回到最前面的问题。这个问题容易引起争议，是因为这个问题中交叉了两个流水线模 型。ops本身可以构成一个流水线模型。ops包含了多个op，如果ops都复用同一个执行体， 这样你有多少Buffer都不好使（根本没有意义，全部都需要串行执行），瓶颈在执行体上 。
如果ops下层有多个执行实体，可以基本上做到无限并行。这样瓶颈才在Buffer上，Buffer 的数量决定了同时可以投入运行的ops的数量，这显然构成一个流水线模型，而瓶颈在 Buffer的数量上。这个并行的“深度”明显和Buffer的数量相关。这当然是个流水线，而且 深度等于Buffer的数量：
.. figure:: _static/buffer流水线.jpg
如果这是一个对外的编程接口，ops这个序列是不可控的（程序员决定的），那么我们只能 把这个序列抽象为一个可以“一定程度并行”的执行序列，这样，我们对这个for的语义定义 当然是一个基于Buffer的流水线了。
最后，我们的问题是，当我知道ops中的op用到哪些执行体以及它们的时长比例，我应该如 何决定Buffer的数量？
这个模型其实很简单，这个模型其实有两个完全独立的控制要素，一个是ops的执行体构成 的流水线模型（参考上面那个基于部件的时序图，下面称为指令流水线），一个是Buffer 数量构成的流水线模型（下文称为Buffer流水线）。ops的设计者只要先构造前者的并行模 型（请注意，同一个序列的ops可以复用同一个执行体，所以整个流水线画出来会有点 Dirty，但仍是可以画的），然后把Buffer的数量设置为那个模型的深度就可以了。
比如我们设计一个ops序列是这样的unit1, unit2, unit3, unit2，流水线将是这样的：
.. figure:: _static/buffer流水线2.jpg
我靠，其实这样一看，ops里面卷入多少个独立计算单元，就放多少个buffer就是最优的。 除非你要考虑省Buffer或者多大的Buffer计算效率最高这种额外的要素。
上面这个结论是从语义来的，但其实还有余地。在语义上，一组ops没有完成之前，它的 buffer不能用于下一组ops的运行，所以，buffer流水线的深度受限于指令流水线的深度。
但如果我们的ops执行到中间就不需要这个Buffer呢？比如，我们把ops分成ops_b使用 buffer，和ops_nb不使用buffer两个部分，这个模型就有可能变成这样：
.. figure:: _static/buffer流水线3.jpg
这个Buffer流水线的深度是4，但只需要2个buffer。如果ops_b足够短，这个流水线的深度 可以更深。
所以，上面这个loop语义，如果基于buffer的结束使用时间来决定下一组ops的投入，流水 线的Buffer深度不受限于Buffer的数量，而受限于ops_b的长度，这在每种确定的参数下， 都是可计算的。