3.流水与并行

第三章、打怪抢宝之流水与并行喜欢玩魔兽的朋友都知道，游戏的前期，不论是基地、士兵或是英雄都是很弱的，此时英雄主要带领小兵到处去打怪练级，同时抢些小小的宝物。这一章的任务就是打怪抢宝，而流水与并行就是两个小小的宝物。称其为“小小的宝物”是恰当的，因为从第四章到第七章，将会隆重推出四件上古之神器：1）重定时、2）展开、3）折叠和4）脉动。这四个神器相对于流水与并行这两个小小宝物那可谓神通广大。实际上，流水就是重定时的特例，而并行又是展开的特例。题外话：前期不把级练好，那后期更甭想用得起上古神器了，所以这一章大家务必细心体会。下面采用结合实例讲解的方式，大家看了之后应该学会如何将流水与并行的技术应用到其他的DSP程序中去。本章分两个小节：1.主要介绍如何在DSP程序中应用流水与并行技术，同时还给出了流水的严格定义（并行没有进行严格的定义^_^b，大家先体会其过程，在展开一章将对并行做进一步的探讨）。2.使用一种技术，就应该知道这种技术所能带来的好处和坏处。流水和并行的坏处大家可以发帖子讨论，而好处呢？主要有高速度和低功耗，前者显而易见，不再多说，而后者低功耗将被详细讨论。讲解：第一节、流水与并行一、初步的认识如下图一a）的数据通路，迭代方程非常简单，就是3个数组对应元素相加，即()()()()ynxnanbn++x(n)y(n)a(n)b(n)a)++x(n)y(n)a(n)b(n)a’)割线++x(n)y(n)a(n)b(n)b)DD图一、示例，a)数据通路；b)流水线结构数据通路是一条前向（非递归）路径。从图一a’)可以更清晰地看到前向非递归的特点。对图一中的数据通路，假设加法节点计算时间为TA，那么关键路径长度就是TA+TA=2*TA。按图一a’)的割线处（割线所隔的两条同向边）插入“流水线寄存器”，也就是延时，就得到二级流水线结构如图一b)所示。图一b)二级流水线结构的关键路径长度变为TA，比原来的缩短了，这样迭代周期可以缩小，吞吐率也能提高。对图一a’)进行并行扩展也非常简单，注意观察迭代式子或者图一a)，节点不存在迭代间的优先关系，也就是说任一次迭代都可以单独进行而与其他次迭代没依赖关系。比如想构造一个2阶并行处理系统，那么可以将输入序列x(n)、a(n)和b(n)分为奇偶两列分别由两套相同的硬件电路来算。具体做法是，将n=2k和n=2k+1带入原迭代式，得两个新的迭代式，如下(2)(2)(2)(2)(21)(21)(21)(21)ykxkakbkykxkakbk这两个式子完全可以单独计算，根据式子构造的并行硬件如图一c)所示。++x(2k)y(2k)a(2k)b(2k)++x(2k+1)y(2k+1)a(2k+1)b(2k+1)图一、示例，c)并行处理结构练习：对于这个示例要构造更高阶的并行系统，如何操作？二、流水线观察前面的例子，可以看出流水线采用沿着数据通路引入流水线寄存器的方法来缩短有效的关键路径，从而缩短迭代周期（采样周期也会相应缩短），提高系统吞吐率。这里先直接给出流水线的三句口诀（也是流水线的严格定义，见课本）：1、一个架构的速度（或时钟周期）由任意两个寄存器间、或一个输入与一个寄存器间、或一个寄存器与输出间、或输入与输出间路径中最长的路径限定。2、这个最长的路径或“关键路径”可以通过在架构中恰当插入流水线寄存器来缩短。3、流水线寄存器只能按照穿过任一图的前馈割集的方式插入。为了说明第三点，需要引入两个定义：割集：割集是一个图边的集合，如果从图中移去这些边，图就成为不相连的了。前馈割集：如果数据在割集的所有边上都沿前进方向移动，这个割集就称为前馈割集。对于1，等价的说法就是零延时最长路径决定了架构的速度，也就是关键路径。对于2，在初步认识的示例中，的确是通过在架构中插入流水线寄存器从而缩短了关键路径长度，由原来的2*TA变为TA，缩短一半。但是要注意，如果想通过插入流水线寄存器的方法来缩短关键路径，那插入的位置就要恰当，必须保证流水线寄存器出现在关键路径的某些边上。众所周知，关键路径上的边必须是零延时的，如果在关键路径的某些边上插入流水线寄存器，那么这条关键路径将被这些流水线寄存器斩断成若干段，架构中新的关键路径肯定小于等于旧的关键路径。之所以有“等于”，是那么一种情况，如果流水线寄存器不是插入到关键路径的某条边上，那原始关键路径没有被斩断，架构的关键路径长度不变。还有另一种情况，在一个架构中，存在多条等长的关键路径，流水线寄存器只斩断其中一些，还有一些没斩断，那么架构的关键路径长度还是不变。反过来说，流水线寄存器要插入到能斩断所有关键路径的边上才能缩短关键路径长度。总之，插入流水线就是想斩断原始的所有关键路径，以得到更短的关键路径。那么插入流水线寄存器，是不是指随便在某些边上加入延时就行了呢？不是的，要想保证架构的功能不变，必须按照规定的法则进行流水线寄存器的插入。看第3个口诀：流水线寄存器只能按照穿过任一图的前馈割集的方式插入。---------------------------------------我们先把割集和前馈割集弄清楚-------------------------------------割集是一个连通图的边的集合，如果从图中移去割集中所包含的边，该连通图就会成为“两个”不相连的连通子图。首先割集中的边要足够多，多到只要移去割集中的边，就能把原来的一个连通图变为两个孤立的连通子图。其次，割集中的边要足够少，少到只要少移去一条割集中的边，就得不到不相连的两个连通子图（注：割集的严格定义可以参考图论方面的书籍）。这里要明白一点，割集中的边是充分的但不多余，恰好可使一个连通图变为两个不相通的连通子图，如下图二的几个示例：BDCABDCABDCAa)b)c)图二、割集示例：a)割集；b)不是割集，不充分；c)不是割集，多余了图二a)是割集，边不多也不少；b)不是割集，如果多加A-B的边就是了；c)也不是割集，多了B-C的边。如果指定割线方向，如图三所示，每条割线（红色虚线）都有一个方向。如果割集中的边都在割线的同一侧，那么该割集成为单向割集，比如图三a)和c)；反之，割集中的边不全在割线同一侧，则称该割集为双向割集，如图三b)。课本上说流水线寄存器只能在前馈割集上插入，其实有些不恰当，应该是在单向割集上插入。BDCABDCABDCAa)b)c)图三、割集示例：a)单向割集；b)双向割集；c)单向割集-------------------------------------------------回到流水线讲解------------------------------------------------明白了割集和单向割集（也就是课本上的前馈割集，以后我们均认为在单向割集上插入流水线寄存器），此外还有一点需要注意：当DSP系统有多个输入端和多个输出端时，应该先把多个输入端折合成一个输入节点，多个输出端折合成一个输出节点，当然了，输入节点和输出节点计算不耗时间，也就是计算时间为0u.t.。比如图四a)的DSP框图，输入有四个分别为a(n)、b(n)、c(n)和d(n)，输出有两个分别为y(n)和z(n)；图四b)为其DFG，所有输入折合为节点I，所有输出折合为节点O。++*b(n)a(n)d(n)z(n)y(n)c(n)++*IOa(n)d(n)c(n)y(n)z(n)b(n)图四、多输入多输出系统及其DFGa)b)下面以图四的DFG为例，来练练手，看如何插入流水线寄存器以缩短关键路径。首先假设加法节点计算时间TA=1u.t.，乘法节点计算时间为TM=2u.t.，那么图四b)的DFG关键路径为++*IO(0)(1)(1)(2)(0)，长度为TA+TA+TM=4u.t.。列出图四b)DFG的一些单向割集如图五所示。++*IO图五、四种可能的单向割集++*IO++*IO++*IOa)b)c)d)图五a)的割集不算斩断有效关键路径，因为决定关键路径长度的是两个加法节点和一个乘法节点，而a)只是将一个计算时间为0u.t.的输入节点从关键路径是去掉而已；b)斩断有效关键路径，新的关键路径为I++或者是*O，长度均为2*TA=TM=2u.t.；c)和a)类似，不算斩断关键路径，仅仅是把计算时间为0u.t.的输出节点从关键路径上去掉而已；d)斩断有效关键路径，新的关键路径为+*O，长度为TA+TM=3u.t.。比较上述的四种流水线插入，b)的插入最有效，可以使得关键路径缩短到2u.t.，次之是d)的插入，关键路径缩短到3u.t.，而a)和d)属于无效的流水线插入。练习：对图五，还能找出其它能作为流水线插入的单向割集吗？对于图五的示例，如果进行两次流水线插入，也就是先进行b)再进行d)，可得如下结构++*IODDDDDD，虽然关键路径只剩一条*O（只进行b)的话，就有两条：I++和*O），但是关键路径长度仍然为TM=2u.t.，看起来第二次的流水线插入d)并没有起到作用，因为它只斩断了I++这条关键路径，还剩另一条等长的关键路径*O没被斩断，而且*O似乎也没办法斩断了。下面我们要介绍的细粒度流水线将可以解决*O没法斩断的问题。仔细分析新的关键路径*O，如果乘法节点能拆分，比如拆成两个部分，分别为节点*1和节点*2，且两个节点计算时间相等都为1u.t.，也就是原始乘法节点的一半，如图六a)，那么可以再次插入一级流水线（红色割线所示），就可以斩断乘法节点，从而得到关键路径长度为1u.t.的“终极”细粒度流水架构如图六b)所示。++*1IODD2DDD*2++*1IODD2DD2D*2Da)b)图六、a)乘法节点可拆分;b)细粒度流水线架构细粒度流水线，无非就是假设那些决定架构关键路径的节点是可以拆分的，将其拆分之后再运用流水线寄存器将其斩断，从而进一步缩短关键路径。反过来，我们把节点不可拆分的流水线称为“粗粒度”流水线。流水线想要用好，除了按正确的方法（单向割集法）进行插入之外，还要注意分析插入的位置，使得插入的流水线寄存器恰好能斩断有效的关键路径，从而得到更短的关键路径，如若不然这种流水线插入就没有意义了。题外话：课本以3阶FIR滤波器为例介绍流水线，帖子中我们不用这个例子，留给大家自己去分析。这样流水线一节就有两个示例分析可以帮助你理解和掌握它。大家看书切记盲从，应该与实际结合起来进行思考，又时书上的一些说法是不太恰当，我想主要是由于文字表达的问题，而不是作者的水平有问题。说实在的，只有真正用心的人才能听得懂作者要说的意思。这本书的很多技术都是作者千辛万苦从N多文献中总结出来的，疏忽之处在所难免，但如果没有这本书，你想深入掌握这些本事，可能得自己去看好多文章，有时都不知从何下手，不论如何，谢谢这个印度老儿KeshabK.Parhi。此外，课本3.2.1节数据广播结构不属于流水线内容，但其中所用的转置变换有时是非常有用的，这一小节留个大家自己阅读，只要弄明白如何用SFG进行架构的转置操作就行。这段内容看完，大家至少记住两点：1）流水线的插入方法，单向割集法；2）怎样插入流水线才能缩短关键路径。三、并行处理在课本的P51，一上来作者就揭示了流水与并行的对偶关系，即一个DSP程序，如果可以划分为一组不相关的计算能够在一个流水线系统中按交替的方式计算，那么它也能够利用复制的硬件按并行处理的模式计算。这说明了DSP固有的并行性可以通过流水线来挖掘，同时也可以通过并行处理来挖掘。------这种流水和并行的关系，作为思考题，大家好好琢磨琢磨，心得体会发贴讨论。这一节所讨论的并行处理，主要通过观察来构造，当然了通过观察肯定很难构造出复杂系统的并行处理架构，之所以在这讨论并行，主要是让大家为第五章的展开入个门，而在第五章将给出一套简洁（2步法）而强大的构造并行硬件的方法。示例分析：3阶FIR滤波器的并行处理，迭代公式如下()()(1)(2)ynaxnbxncxn直接实现形式如下图***++DDx(n)y(n)abc关键路径为*++，长度是TM+TA+TA。为了将其改造