7.脉动阵列

这一章，与大家一起讨论四种上古神器（包括：重定时、展开、折叠和脉动）的最后一件：脉动阵列。说起来这项技术还是咱们“龙的子孙”发明的，来自卡内基梅隆大学（现在哈佛？）的孔祥重教授。不过在正式讲解脉动阵列之前，有必要给大家打个预防针：脉动阵列在所讨论的四件神器中应该是最费脑筋的一件，要想真正理解并掌握脉动阵列，不仅需要良好的立体几何思维，也需要超人的细心，同时还需要一点点创造性思维。这种难啃的东西，很多人会放弃，但如果你深入进去，你肯定着迷。这里所讨论的脉动阵列只能说是入门，很多学者正努力扩展传统的脉动阵列理论，以拓宽脉动阵列的应用领域。对这方面感兴趣的同学可以google看文献深入学习，这里我们的目的就是讲解最简单的脉动阵列设计技术，带领大家入门，至于登堂入室那是你自己的事情咯！脉动阵列到底是什么呢？如幻灯片1给出的一维脉动阵列（线形）和二维脉动阵列（矩形），它们与主处理器的关系就像是“心脏和脉络”的关系，脉动阵列不断的接收从处理器泵出的待处理数据，然后从另一边将处理后的结果传回处理器。较为正规的定义：多个相同的处理单元（简称PE）按一定互联规则组成的网络，称为脉动阵列。脉动阵列可以是一维线形、二维三角形、二维矩形、二维六边形、二维二叉树型、三维长方体形等等。脉动阵列（这种PE网络）的特点是：1.每一个节点，也就是PE，也称为胞元，都是相同的。2.每个PE只与其相邻的PE进行通信，也就是说PE之间的通信具有局部性，而且通信是规则的。可想而知如果通信不是局部的而且不规则，那么网络中各PE的连接关系将会很错乱，硬件上进行布局布线也会遇到困难。3.每个PE都有其局部的存储器，也就是PE的某些边带有延时，延时在硬件上对于寄存器。这说明脉动阵列数据储存具有局部性，同时这也是流水运行的必要条件。由于脉动阵列的以上特点，造成PE之间的高度流水化、规则化，因此系统吞吐率非常大且易于VLSI的实现。流水化意味着吞吐率大，规则化则意味着版图流片成功率大。以上所说的脉动阵列特点是一种理想的特点，工程上为了扩大脉动阵列的用途，会引入一些弛豫，比如允许使用邻近（靠近但不是相邻）互联，使用数据广播操作，以及在系统中使用不同的胞元，尤其是边界上的胞元往往和网络内部胞元不太一样。幻灯片2给出了脉动阵列的keywords，大家可以在看完这一章，看懂这一章之后好好来品味这些keywords所代表的含义。虽然还没开始脉动设计技术的讨论，但是通过前面的铺垫，大家应该知道这么一点：脉动阵列是高度流水化和规则化的多处理器网络（注意，处理器/胞元/PE为同一个东西，均指脉动阵列的一个处理单元）。既然脉动阵列是高度规则的，那么脉动阵列所完成的功能是不是也应该是规则的呢？这是脉动入门的第一道坎，一定要记住：不是任意的算法都可以用脉动阵列来实现，只有规则的迭代算法，才能用投影技术设计出脉动结构。问题又来了，怎么判断一个迭代算法是不是规则的？FIR是规则迭代吗？矩阵乘法是不是规则迭代？其他等等…….判断一个迭代算法是否规则，首先画出该算法的依赖图（DG），关于DG是什么，在第一章、敲门砖——入门的准备的内容有讲到，这里我们假设迭代算法的DG是已知，只讨论如何根据规则DG设计出脉动结构。比如三阶FIR滤波器和2x2矩阵乘法的DG如下图1和图2所示，01234x0x1x2x3x4w0w1w2ij图1三阶FIR依赖图，y(n)=w0*x(n)+w1*x(n-1)+w2*x(n-2)0000a11a21a22a12b11b12b22b21c12c22c11c21ikj图22x2矩阵乘法C=AxB请大家根据第一章中对DG的解说来验证这两个DG，并总结出一些根据规则迭代公式画出DG的做法；这两个DG也正是课本上例子。规则DG的判据：如果依赖图的任一节点沿某个方向的边存在，则称依赖图是规则的；通俗的说，依赖图的所有节点具有相同形式的边。例如图1的每个节点都可以看成具有三条边，一条从左向右[1,0]T的权值边，一条从下到上[0,1]T的输入边，一条斜向右下角[1,-1]T的输出边。图2的每个节点也有三条边，分别是[1,0,0]T方向的输入b，[0,1,1]T方向的输入a和[0,0,1]T方向的输出“c”。说起来，这个判据也不是绝对的严格，大家体会体会吧，也许等你大致弄明白脉动的设计方法之后，你会理解现在所说的这些话。这里值得注意的是，我们用[0,0,1]T之类的符号表示方向，比如在图二中，清楚的标出了坐标系i-j-k，那么[0,0,1]T就表示向上的一个方向，又比如在图一中是以i-j构成坐标系，那么[1,-1]T就表示斜向右下角的方向。幻灯片3给出脉动阵列的设计步骤，大家可以“先死记硬背”着。接下来的内容将以3阶FIR和2x2矩阵相乘为例，详细讨论如何来导出课本上所列出的各个设计结果。题外话：我自己在学习这一章的时候，看到这里一直是晕晕乎乎的状态，根本不解脉动阵列是什么东西。但是在例子的学习中，突然开窍了，也明白了所有前面这些内容的意思，所以在以下例子的讨论中，大家一定要咬紧牙关，不论你是在和我一起学习，还是你在自学，只要你开动脑筋开足马力去研究这些课本上这些例子，肯定能开窍。例一、3阶FIR滤波器的脉动阵列设计，DG如图1所示。脉动阵列设计的方法有很多，比如代数法、参数法、变换法和投影法等等。我们所讨论是投影法，也是最直观的一种方法。在立体几何中，所谓的投影是什么？ijAoB图3矢量A在坐标轴上的投影如图3示，矢量A在i轴和j轴上的投影，以及矢量A在矢量B方向上的投影，矢量在某个方向上的投影对应的数学运算就是内积。如图1的3阶FIRDG，表示了所有（无限次）迭代的节点依赖关系，为了在硬件上进行实现，必须将DG映射到实际电路，也就是说必须将DG中的节点和边分别映射为具体的硬件处理单元和互联关系（或者是带延时的互联关系）。在我们要讨论的脉动设计技术中，这种映射是通过投影来实现的，具体而言，如图4示P013B1S01245678910图4B1脉动阵列映射图（输入广播，结果移动，权重保持）我们把DG图所在的i-j空间投影到一维脉动阵列空间。一维脉动阵列是“这么样”的一个2维空间，一个维度是PE空间，也就是说PE是线形的，另一个维度是时间；同理二维脉动阵列是一个3维空间，其中两个维度形成PE空间，显然PE就是平面网络，可能是矩形也可能是三角形或六边形等，另外一个维度是时间。如图4，蓝色坐标轴P是PE轴，红色坐标轴S是时间轴，图中的水平蓝线和竖直红线清楚的显示了节点（黄色）是如何投影到PE轴和时间轴的，这种投影的物理意义是：所有在同一条竖直红线上的节点在同一个周期被调度执行，比如从左边起的第一列三个节点投影到S轴的0位置，那么这三个节点将在周期0被调度执行，同理第二列的三个节点将在周期1调度执行，也就是说一个节点投影到S轴的哪个位置，就表示在那个周期被调度执行。现在我们知道了每个节点调度时刻是怎么来计算的，那么节点要调度到那个PE上执行呢？在这个例子中使用了一维脉动阵列，线形的PE网络，类似像时间轴投影的过程，所有节点向P轴投影，投影的位置就是节点运行所在的PE位置，比如从下到上三条水平蓝线上的节点分别被投影到PE0、PE1和PE2三个硬件处理器上运行。说到这，大家也许有些明白了。设计脉动结构，其实就是对DG中的各个节点进行调度，也就是说xxx节点安排在xxx周期调度到xxx处理器上运行。其实本质上就是节点调度的问题，只是这种调度不是任意的，要符合一定的规则，这样才能保证所得脉动阵列功能是正确的。仔细思考下面这个问题：约定一个PE在一个周期内只能执行一个节点的计算任务，也就是说，不能在同一个周期内将多于一个的节点映射到同一个PE。从数学意义上说，对一维脉动阵列，时间轴不能和处理器轴平行；对二维脉动阵列，时间轴不能和处理器平面平行。开动脑筋好好想像一下，比如一维脉动阵列中，如果时间轴和处理器轴平行，那么一串被调度到同一个周期的节点，也将同时被安排到同一个PE来执行，这和我们前面的约定“一个PE一个周期只执行一个节点的计算任务”矛盾；同理，推广到二维脉动阵列，如果时间轴和处理器平面平行，又将如何呢？你来说说？课本上将上述所说的情况定为“可行性限制条件”，也就是说，我们在构造脉动空间时，必须保证时间轴不能和处理器轴或处理器平面平行。这一点的物理意义非常明显，大家多思考一下即可明白。回到对图4的脉动设计，我们构造了这样一个脉动空间，它的时间轴与i轴平行，它的处理器轴与j轴平行，i-j指的是DG空间的坐标轴，而S-P指的是脉动空间的坐标轴，在图4的例子中，构造的脉动空间恰恰好与DG空间“重合”。注意这只是个偶然，因为还可以构造很多其他形式的脉动空间，千万不要以为DG空间就是脉动空间，不要两者傻傻分不清楚。脉动硬件电路构造：1.从图4的处理器轴，可以看出所需的线形脉动网络包含3个PE，0周期左边起第一列节点调度到这三个PE执行，1周期轮到第二列节点，2周期是第三列节点，这样一直延续下去，在硬件上可以先画出三个PE单元，如下图PE0PE1PE22.接下来，需要把DG中节点的边映射为各个PE之间的互联关系。同时看图1的DG和图4的脉动空间映射，对于[1,0]T方向的权值w边（水平向右），权值边连接相邻的两个水平节点，将该边投影到S上，跨越一个周期，将改变投影到P上，位于同一PE，这就表示，权值边在硬件上是同一个PE上延时一个周期的连线，如下图示PE0PE1PE2w0w1w2DDD再来看[0,1]T方向的输入x边，投影到S没有跨度，投影到P，是从低序号PE到高序号PE的边，反映到硬件上就是PE0PE1PE2w0w1w2DDD...,x2,x1,x0最后，在看[1,-1]T方向的输出y边，投影到S，跨越一个周期，投影到P，从高序号PE到相邻的低序号PE，反映到硬件上就是0PE0PE1PE2w0w1w2DDD...,x2,x1,x0y0,y1,y2,...DD至此，就完成整个DG到脉动空间的映射过程。建议大家牢记一点，时刻在脑海中想像其硬件的图景，清楚每一步自己都在干些什么，每一步是在硬件上又意味着什么，不要仅仅把上述的内容看出生硬的步骤！！！3.得出脉动结构图，结合DG中节点的具体内容，即可画出最终电路。图1节点的内容是一个乘法加法的级联单元，最终电路图如下示，其中虚线所圈为节点的具体内容，*+w0w1w20...,x2,x1,x0y0,y1,y2,...**++DD也许大家发现，这里给出的最终电路和课本P142图7-4的电路不太一样，其实它们是同一个电路，大家在构造最终电路时，结合实际情况进行一些合理的修改是没问题的。对于图4的映射过程，我们是通过观察直接构造出脉动阵列，但是对于更为复杂的映射有时会显得力不从心。下面使用一个不同于B1映射的脉动空间，但这次将用严格的数学形式来描述整个过程；用数学形式来描述映射过程是非常强大的，在稍后矩阵乘法的例子中将看到，我们很难在画出形象的映射图，而只能靠“数字”来指导如何画出脉动结构。观察图5的脉动空间，这里所选择的处理器轴P和图4的不一样，所形成的脉动空间S-P也不同于图4。013B2S45678910P0120120120图5B2脉动阵列映射图（输入广播，权重移动，结果保持）“严格的”脉动硬件电路构造：1.首先要用矢量来表示脉动空间的两个坐标轴P和S，这里令10S，11P，显然P和S是不平行的（数学上两个非零矢量是否平行，则它们的叉乘为0，即0SP），满足“可行性限制条件”。任一个节点ij在P轴和S轴上的投影，在数学上就是点乘，即节点ij在iSj周期被调度到iPj处理器执行。例如图5中左下角第一个节点，坐标为00，将在101000000iSj周期被调度到101010010iPj处理器执行；又比如左上角第一个节点，坐标为02，将在101002002iSj