2.迭代边界

第二章、芝麻开门之迭代边界这里贴美其名曰为芝麻开门，是向大家强调：这里所讲的内容就是打开宝库大门的咒语，如果大家把这贴的N多易混淆的概念弄清楚并理解透了，开门的咒语就算记住了。否则你很难打开这个宝库的大门。大家可不要小看这一章，里面充斥着多个错综复杂且易混淆的概念。当然这是对新手而言，对于有经验的工程师，这里的内容都已经是公认的常识。提前给大家打个预防针，这里先把这些“顽皮”的家伙列出来：1.递归DSP、非递归DSP和环路；2.关键路径；3.迭代周期（也称时钟周期）、采样周期和环路周期；4.关键环路、环路边界、迭代边界和采样边界（等价于吞吐率）。注：迭代边界和采样边界是主角。下面将按这个次序将它们一个个提出来进行剖析：1.递归DSP、非递归DSP和环路这段采用看图识字的方式，如下图a)FIR和b)IIR是我们最熟悉的DSP结构。对于a)FIR所有的数据都是前向（朝输出方向）流动，没有反馈回路；而b)IIR则不然，既有前向又有后向流动的数据，比如b）中红线所标记的环路，就是一个反馈环，将中间数据w(n)z^(-1)反馈回去与x(n)相加。所谓的递归DSP和非递归DSP，区别就在于是否存在那么一个环路，进行数据反馈。显然IIR结构是递归的，带反馈环路的DSP结构，而FIR是非递归的，不带反馈环路的DSP结构。反馈环路也能直接简称为环路，因为如果构成环路，就肯定具有反馈作用。提醒，在a)FIR结构中的那些看起来像环的不是真正的环路，要注意环路上的所有边必须是同一个方向的，比如都是逆时针，或者顺时针。习题1、判断一下哪些不是环路，原因是什么？答案：a）是环路，方向顺时针；b）显然不是环路，而是一条直路；c）也不是环路，虽然看起来像一个环，注意到没？ACDB是逆时针方向，而AB却是顺时针方向，所以不是环路；同理d）也不是环路，AB、DC是顺时针方向，而AC、DB却是逆时针方向。注意一条，环路的所有边必须方向一致，就不会判断错！2.关键路径关键路径真是太bt了，你能说出那个工程师不知道关键路径是什么吗？如果不知道也称不上是个合格的工程师。这里我们就当是复习，把关键路径严格的定义一遍。在DFG中，具有零延时（也就是纯粹组合逻辑）的所有路径中，具有最长运算时间的路径定义为关键路径。从这句话中，关键要捉住一点“零延时”，也就是说关键路径上的所有边都是没有延时的，比如课本上图2-2，即下图把符合零延时条件的路径列出，其中包括关键路径（不熟悉DFG的同志，可以看第一章的讲解）。路径：421、5321、6321以及这三条路径的一个片段，比如321、42、53、632等等。路径长度等于路径上所有节点计算时间之和，比如421长度为2+1+1=4u.t.，5321长度为2+1+1+1=5u.t.，6321长度为2+1+1+1=5u.t.。通过计算所有可能路径的长度，可以找出最长的路径是5321和6321，长度为5u.t.。关键路径是一个系统内计算时间最长的纯粹组合逻辑路径，如果系统的运行时钟周期小于关键路径长度，会造成什么恶果？那么关键路径上的节点尚未计算完毕（物理上就是信号还未稳定），下个时钟触发沿就来到了，造成寄存器锁存了不稳定的错误的数据，最后造成整个系统输出错误结果。因此，关键路径是决定系统时钟周期最小值的主要因素，系统时钟周期只能大于或等于关键路径长度。3.环路周期、迭代周期（也称时钟周期）和采样周期4.关键环路、环路边界、迭代边界和采样边界（等价于吞吐率）（大家注意，这里是3和4两个一起混合讲，我实在是做不到把他们分开）一个环路，如图ABDC3D(4)(1)(1)(2)D。前面我们讨论什么是环路是都没有去关注环路上节点的运算时间，也就是小挂号所括的数字，和边的权值，也就是路径上的延时个数，从这就要开始注意了。首先明确一点，一个可物理实现的环路至少包含一个延时，不包含任何延时的环路是不可能实现的，大家可以思考一下，这是为什么？关键路径是DA，长度为1+4=5u.t.。这个环路在计算时的运行时钟周期必须大于等于5u.t.，如此我们称环路中关键路径长度为该环路的环路周期，表示这个环路运算时所能接受的最小时钟周期。但是对于上图的环路，5u.t.并不是其极限的时钟周期，还可以进一步缩短，利用后面章节要介绍的重定时技术，可以在保持系统功能不变的情况下，改变边的权值（也就是延迟的数量和分布），从而缩短关键路径，进一步缩短环路周期。重定时后的环路图下图ABDC2D(4)(1)(1)(2)DD，此时关键路径就只有A节点，长度为4u.t.。在进一步，假设节点A可以拆分成两部分，每部分计算时间为2.u.t.，那么利用重定时，可得如下环路，A0BDCD(2)(1)(1)(2)DDA1(2)D这个环路的环路周期为2u.t.，这个所谓的2u.t.是这个环路理论上的极限速度了，也就是说，不存在任何方法可以突破这个周期限制。我们称一个环路理论上的最小时钟周期为该环路的环路边界，“边界”知道吧，不可逾越的界限。仔细体会整个过程，可以发现，环路边界可由公式求出，_lltloopboundw其中t_l是环路长度（也就是环路所有节点计算时间之和），w_l是环路所有边的权值之和（或延迟个数之和）。说起来也奇怪，如果是一条开环的路径，比如直线路径，ABDC(1)(1)(2)(4)，就不存在理论上的速度限制。假设节点是可拆分的，对以上这个开环路径，只要使用流水线技术，就可以把时钟周期缩短，而且是没限制的。但是对于环路则不然，由于其首尾相连的这种约束，做不到在环路中插入流水线（为什么？在第三章会与大家详细讨论什么是流水线以及如何应用流水线，而且还对流水线技术对功耗的影响进行分析，很好玩！），所以存在一个理论上的速度限制，这就是环路边界。迭代周期，也就是平时所说的系统时钟周期，这里我们先只考虑当时钟域的情况，假设系统只使用一个全局时钟，对于多时钟域的情况，大家自己去扩展，不存在困难。怎么来解释系统时钟周期，也就是迭代周期，定义为，系统进行一次完整运算所需的时间，或者是系统进行一拍运算所需的时间，这样能理解吗？（各位大哥大姐多多包涵这种定义，我想大家都知道我的意思，就不废话了）从前面的分析可知，如果系统不存在环路，那么可以用流水线技术来加快系统速度，缩短迭代周期。但是如果系统中包含一个或多个环路，那么就不能无限提速了。引用课本上的说法：递归的（也就是包含环路的）DFG存在一个基本极限，该极限表示了关于用硬件实现基本的DSP程序能够有多快，这个极限定义为迭代边界，这就是这章的主角了。因为系统的速度受制于环路，故而迭代边界“T_无穷”定义为max{}llLltTw其中，L表示DFG中所有环路的集合，t_l是环路l的运算时间，w_l是环路l的延时数目。习题2、计算下图迭代边界答案：上图包含三个环路，分别用红线标识。（看课本），计算出环路边界分别为4/2=2u.t.、5/3u.t.和5/4u.t.，最糟糕的环路边界为4/2=2u.t.，这个就是害群之马，DFG的速度被其所拖累，因此该DFG的迭代边界为2u.t.，同时我们称这个害群之马为“关键环路”，这有道理吧！曾几何时，我们讨论过，衡量系统速度不能只看其时钟速率（时钟周期），还需要考虑其吞吐率。吞吐率定义为单位时间系统所能处理的样本点个数，它的兄弟就是采样周期。采样周期是吞吐率的倒数，采样周期也小，吞吐率越大，反之采样周期越大，吞吐率越小。采样周期和迭代周期存在伙伴的关系，但它们是不同的两个“人”。下面根据系统的并行度来说说采样周期和迭代周期的这种伙伴关系：系统一次迭代只处理一个样本这种情况下，采样周期等于迭代周期，也就是一个周期采样一个样本并处理一个样本；系统一次迭代处理N个样本此时采样周期将是迭代周期的N分之一，这是一个并行处理的系统，可以在一次迭代中同时处理多个样本，所以采样的速度要是迭代速度的N倍，才能保证货源不缺；系统处理一个样本需要N次迭代这个系统就过分了，不仅是一次迭代处理不了多个样本，而且一个样本竟然还需要多次迭代才能处理完，这种系统成为“折叠后的系统”（这也是后面章节将要详细讨论，有其存在的价值，我保证很多人会爱上折叠）。此时采样速度要比迭代速度慢，表现在周期上就是，采样周期等于迭代周期的N倍。上面的分类讨论，大家清楚的认识到采样周期与迭代周期的关系了吧。对应迭代周期有一个迭代边界，理所当然，对应采样周期也有一个采样边界，用于衡量极限吞吐率的大小。哈哈，ok了，这一贴的内容就这些。课本上还有一个多速率DFG迭代边界的求法，我们先跳过，在后面章节中讨论到多速率系统的变换算法时再统一的进行讲解。题外话，在讲解这一章时，我压力很大。因为我想熟练的工程师，这些概念自然是不用说了，但是我需要做的是，让一个新手，就像我开始看这本书时一样，如何才能透彻的理解这些概念，知道这些概念的重要性，而不仅仅是将其看成是几句无关紧要的字句。最后我硬着头皮这么讲了出来，但是却不敢保证大家能清晰的看懂。所以希望大家能自己再详细的思考一番，甚至能把我所讲的内容中的错误找出来，进行纠正，那善莫大焉。下集内容预告：下一章，我们将进入一个打怪练级的阶段，给大家打打几个野怪，升升级。