4.重定时

游弋的灵魂之重定时----------------------------------------------------------------------------------------------------------------------前面的三章我们介绍了VLSI-DSP硬件架构一些最重要的基本概念，比如迭代边界，之后简单讨论了一下最常见的两项技术：流水线和并行处理。从这一章开始，将隆重推出四件神兵利器，这里要讲第一件，游弋的灵魂之重定时（retiming）。谁是游弋的灵魂？这个疑问暂且记在心里，看完这章就得到答案了。接下来的内容分两节：1.延时（也就是寄存器）是如何在系统中游弋的？2.重定时的两个典型用法：流水（pipeline）重定时和割集（cutset）重定时。讲解：第一节、重定时的来由、做法及性质很多时候，我们想改变原始系统中延时的数量和分布，以改善系统的某些性能（如面积、速度和功耗）。具体的，流水线就是改变系统延时数目的一个特例。加入流水线后，系统中的延时数目增加了，所付出的主要代价就是面积变大，当然这带来了更快的运行速度。反过来，有时不需要那么快的运行速度，而是想减小面积，可能需要“撤去某些流水线”，以减少延时的数目。注意：延时的多少等同于寄存器的多少。为了能在各个性能指标之间进行灵活的折衷，就希望能制定一套如何来增加或减少系统延时数目以及改变系统延时分布的方法，重定时技术就应运而生了。所谓的重定时就是一种，在保持系统的功能不变的前提下，改变系统延时数目和分布的方法。重定时在同步电路设计中有很多应用，包括缩短系统的时钟周期、减少系统中寄存器的数目、降低系统的功耗和逻辑综合的规模。以上具体的四种应用我们暂时不拿出来讲，大家可以参照书上的相关文献进行深入的学习，这里要讲解的是重定时最基本的做法和性质，有了这些基本知识，要深入去学习重定时的某项应用就轻松多了。重定时基于那么一个简单的条件——系统的时不变性（time-invariantsystem），也就是说时不变系统才可使用重定时（更严格的说是，时不变计算节点才可进行重定时）。首先看看时不变系统的定义：如果系统的输入输出关系不随时间而改变，那么这个系统就称为时不变系统。这样就意味着输入信号的延时会导致输出信号的延时，如若不然，就是时变系统。用数学公式表示为其中T表示一个时不变系统，公式的意义是，输入x(n)延时k个周期将导致输出y(n)也延时相同的k个周期。——参考胡广书《数字信号处理》第一册，1.5节离散时间系统的基本概念。----------------------------------------------------------------------------------------------------------------------练习：给定系统其中n=0，分别判断系统的时不变性。答案：1）因为但是显然，所以，公式1）所示的系统不满足时不变性，是一个时变系统。2）令，则有因为而且也就是说简化为所以，公式2）所示系统满足时不变性。注：对信号系统不是很熟的同志可以看看相关的书籍，直接跳过这里的讲解也是没有太大问题的。之所以从时不变系统开始讲，是为了能明白重定时的本质而已。----------------------------------------------------------------------------------------------------------------------例子：将延时D看成是一个算子，则下图所示的系统ABx1(n)x2(n)w(n)y(n)D可用公式表示为对于时不变系统而言，输出延时k个周期，也相当于输入延时k个周期，所以有对应系统结构为ABx1(n)x2(n)w(n-1)y(n)Dw(n)更进一步，有对应的系统结构为ABx1(n)x2(n)w(n-1)y(n)DDEnd在时不变系统中，延时算子用D表示，Dk表示延时k个周期，k为非负整数，D0（k=0）表示没有延时。假设系统为y(n)=T[x(n)]，对y(n)延时一个周期表示如下推而广之，对y(n)延时k个周期，有下图所示四种重定时的情况动画图：1）单输入单输出节点，2）单输入多输出节点，3）多输入单输出节点，4）多输入多输出节点。对于1）单输入单输出节点，Dk可以从一条输入边移动到一条输出边，反之亦然；2）单输入多输出节点，Dk从一条输入边同时移动到多条输出边，且每条输出边都增加相同的k个延时，反之，每一条输出边同时提供一个Dk，才能将其“合并”移到输出边；3）多输入单输出节点类似2）的情况；4）多输入多输出节点，每一条输入边同时提供一个Dk，才能“合并”移动到每一条输出边，反之，每条输出边要同时提供一个Dk，才能“合并”移动到每一条输出边。大家仔细看动画，总而言之，任一节点的每一条输入边都减少一个Dk，则其每一条输出边必增加一个Dk；反之，每一条输出边都减少一个Dk，则其每一条输入边必增加一个Dk。下面以课本的IIR滤波器为例，来说明如何使用重定时来缩短时钟周期和减少寄存器数目两个问题。IIR的迭代公式如下直接根据迭代公式画出DFG如图一A)，假设加法节点计算时间为1u.t.，乘法节点计算时间为2u.t.。仔细观察图一A)的DFG，存在两条等长的关键路径，都是*++，长度为1+1+2=4u.t.。1）要得到更快的运行速度，必须想办法斩断这两条关键路径。利用重定时可以改变系统中延时的数目和分布，显然只要能在关键路径*++上放上若干延时将其斩断，同时又能保证系统的其他部分不产生比*++更长的关键路径就大功告成了。具体做法是，将两个乘法节点输入边的延时个分出一个来，如图一B)红色D所示；然后将这两个红色的延时重定时（也就是移动）到乘法节点之后的输出边上，如图一C)虚线所指的移动路径；最后得到如图一D)所示的新结构。新结构存在三条等长的关键路径，两条为*，另一条为++，长度为2u.t.，显然新DFG运行频率比旧DFG运行频率快一倍。+*+*y(n)x(n)(1)(1)(2)(2)ab+*+*y(n)x(n)(1)(1)(2)(2)DabD+*+*y(n)x(n)(1)(1)(2)(2)2D3Dab+*+*y(n)x(n)(1)(1)(2)(2)D2DabA)B)C)D)图一、y(n)=a*y(n-2)+b*y(n-3)+x(n)原始DFG及其重定时版本DDDD2D2DDD2）另一方面，如果系统不需要那么高的运行频率，而是想尽可能减少实现的面积，那么就属于寄存器最小化问题。具体做法是，先将两个乘法节点输入边的延时分出两个来，如图二B)所示；然后移动到乘法器之后，得到图二C）的结构；继续将这些延时往前移，注意此处涉及到的加法节点只有一条边，故而两个输入边的延时“合并”，在加法节点的输出边上出现红色2D的延时。比较图二A)和D）两个结构，新结构相当于把原始结构的4个延时减少到2个延时，当然了新结构的关键路径为+*+，长度为4u.t.，速度上没有改善。+*+*y(n)x(n)(1)(1)(2)(2)ab+*+*y(n)x(n)(1)(1)(2)(2)ab+*+*y(n)x(n)(1)(1)(2)(2)2D3Dab+*+*y(n)x(n)(1)(1)(2)(2)2DabA)B)C)D)图二、y(n)=a*y(n-2)+b*y(n-3)+x(n)原始DFG及其重定时版本DD2D2D2DD2D从上面这个IIR滤波器的例子，可以看出重定时是缩短系统时钟周期和减少系统寄存器数目的利刃。值得注意的是，重定时作用远不如此，比如重定时可以用来减少开关动作降低系统功耗：在具有大电容的节点输入端插入寄存器能够减少这些节点的开关动作率，从而导出低功耗解决方案。——重定时的低功耗设计，作为思考题，大家可以发贴说说自己的见解。至此，大家对重定时应该都有一个直观的理解了，知道如何“手动”地对系统进行简单的重定时以改善某些性能指标。但是，实际系统往往有成百上千，甚至上万个节点，要想“手动”重定时，给出1）时钟周期最小，2）寄存器最少，3）两者混合的某个折衷，三个不同的系统重定时方案，估计比登天还难。其实，重定时是一个改变系统延时的数目和分布的一个规则，利用重定时能导出满足特定单个目标或多个目标的系统实现方案，换句话说重定时设计其实是一个优化求解的问题，而且往往是大规模的。要解决那么一个大规模优化问题，应该用计算机和优化算法来处理，需要我们去做的是，把重定时数学建模为一个可优化的问题，以及给出特定的目标函数。。。（这里说多了，但不知道大家有没有优化计算、优化搜索这些概念，其实也不是很难，推荐一个工程领域的优化工具modefrontier，大家感兴趣可以看看，此外近年来兴起的智能计算也可参考参考）重点内容来了：重定时的数学模型及其性质如图的一个节点Ax1x2xny1y2ym......，共有n条输入边和m条输出边。直观的重定时做法是，如果所有的输入边每一条都减少k个延时，那么所有的输出边每一条必增加k个延时；反之，所有的输出边每一条都减少k个延时，则所有输入边每一条必增加k个延时。为了进行自动重定时（让计算机来处理），必须告诉计算机每一个节点所需进行的重定时情况，总而言之，无非是那么三种情况（k为非负整数）：1）对每一条输入边增加k个延时，同时在每一条输出边上减去k个延时；2）对每一条输出边增加k个延时，同时在每一条输入边上减去k个延时；3）不进行任何输入输出边的延时个数调整。这么一来，只需为每个节点赋予一个整数值k（可正可负，也可为0）。如果k0，表示情况1），每条输入边增加k个延时，同时每条输出边减去k个延时；如果k0，表示情况2），每条输出边增加-k（也就是k的绝对值）个延时，同时每条输入边减去-k个延时；k=0，就是情况3），什么也不干。总结起来就是，输入边加上k个延时，输出边减去k个延时，k为可正可负可为零的整数。在任一个多节点系统中，可以为每个节点赋予一个整数值，用于指定每个节点需要进行何种情况的重定时操作。UVUV如上图示，U和V两个相连节点的情况，分别为每个节点赋予一个整数值r(U)和r(V)，边的权值就是边上延时的数目，左图原始的DFG中的一条边，右图为重定时之后的系统的相应边。根据上面所规定的做法，边e为节点U的输出边，所以边e的权值需要减去r(U)个延时，同时边e又是节点V的输入边，所以需要再加上r(V)个延时，所以重定时之后新边的延时为这就是重定时方程的由来了。不过话说回来，因为一开始我们并不知道为每个节点赋予什么样的值才是合理的或者说是最佳的。假设随便设定一些整数值，如果发现DFG中某条边的重定时延时w_r(e)是个负值，那么说明前面所设定的节点值是不合理的，自然界就没有延时为负数的情况，而且没法解释其物理意义。所以规定，只有当DFG中所有边的w_r(e)都是大于等于零时，所设定的节点值才是合法的，所进行的重定时才是可以实现的。再以课本上的IIR滤波器为例，重新画出DFG如右1324(1)(1)(2)(2)2D3Dab，为了方便计算节点直接用序号表示。总共四个节点，假设为每个节点所赋之值为r(i)，i=1，2，3，4。共有5条边，进行重定时之后的边的权值计算如下:这是一个多元一次不等式方程组，求解这个方程组所得的解，就是合法的重定时实现。另外，可以设定多个目标，比如系统时钟周期和寄存器个数等，在此不等式方程组的约束条件下，搜索出使得规定目标最小化的解。题外话：关于优化求解这个话题我们以后再详细讨论，因为涉及到一些优化方面的内容，我需要弄懂并找到好的方法之后才能和大家讨论怎么来做，当然了也欢迎各位踊跃提出自己处理这个问题的好方法。我个人拟用modefrontier来处理，貌似matlab的lmi也能求解一些简单的情况，课本上也给出了一些求解的方法，感兴趣的同志可以去看，然后发贴讨论。上面详细的讨论了重定时来由来和做法，下面就是重定时的性质了。每一种方法都有其自身的一些特殊性质，明白这些性质将进一步加深我们对重定时的理解。性质一重