D
2011-3-20
清华大学微电子学研究所 陈弘毅
7
二 迭代边界(续)
• 环路、环路边界与迭代边界
– 环路：开始与结束于同一节点的有向路径
• 右图例子：A0 B0 A1 B1 A2 B2 。。。 下标表示迭代编号 • 环路一次迭代时间的下限可由其有向边描述的优先顺序关系确定 例： A0 B0 A1 B1 。。。一次迭代时间下限为6u.t.。它是决定 环路每次迭代最低执行时间的因素之一 • 定义：第L个环路的环路边界TLoopBond是指TL/wL ，其中TL是环路运行 时间， wL是环路中延迟数 • 例 1：右上图的环路边界是TLoopBond = (2+4)/1 = 6 例 2：右下图的环路边界是TLoopBond = (2+4)/2 = 3
– 其中 L是DSP系统一组环的集合
• 例1 a) 一个环
b) 两个环
T = TLoopBond = 3
• 例 2：三个环，节点计算时间用ns标出
T = max{6/2, 11/1} = 11
2011-3-20
清华大学微电子学研究所 陈弘毅
10
二 迭代边界(续)
– 几点说明
• 环路必须有延迟元件
VLSI 数字信号处理
(课号：81020082)
2011-3-20
清华大学微电子学研究所 陈弘毅
1
前言
• 目标
– 联系两个领域：计算机架构、数字信号处理(DSP) – 结合两个层次：数学算法、VLSI实现 – 面向多种应用：语音、音频、图像、视频、通信、密码等
• 内容
– 重点：信号、图像等数字处理应用VLSI系统的设计方法 – 寻求面积－功耗－速度之间的优化 (折中 ) – 方法：给定算法－找出架构集合－选定优者－建立硬件模 型－设计芯片
• DFG中执行计算时间最长的无延迟路径 • 环路是 DFG中的一部分，环路关键路径不一定是 DFG关 键路径
清华大学微电子学研究所 陈弘毅 12
– 关键路径
2011-3-20
二 迭代边界(续)
– 迭代周期、采样周期、时钟周期之间联系
• 实时处理：要求迭代周期＝采样周期 • 根据情况
– 流水线：时钟周期=迭代周期，即时钟周期=采样周期 – 并行处理：时钟周期(慢 )迭代周期，时钟周期采样周期 – 折叠：时钟周期(快)迭代周期，时钟周期采样周期
• 并行处理(Paralleling)
– 成倍复制处理硬件，在一个系统时 钟周期内同时处理若干个样点，计 算出多个结果输出 – 有效的采样速率被并行程度所增加
– 在不需要提高采样率时，这两种 方法可用于通过降低电源电压降 低功耗
2011-3-20 清华大学微电子学研究所 陈弘毅 14
三 流水线与并行处理(续)
2011-3-20 清华大学微电子学研究所 陈弘毅 3
一 引言
• DSP系统
– DSP算法是执行一段无终止(non-terminating)的运算程序 – 系统实时 (Real-time)需要
• 实时指系统的硬件/软件必须且仅需满足应用速度的要求 • 用 VLSI或芯片实现是趋势
– DSP芯片的性能
• 流水线
– 用流水线减少关键路径：以3阶FIR数字滤波器为例
• 框图 (BD)
– 关键路径 Tc为一个乘法器、 两个加法器时间Tc = TM + 2TA – 采样周期和采样率
• 插入流水线锁存器减少关键路径
– 从 TM + 2TA 减到 TM + TA x(n-1) x(n-3) – 关键路径插入一个延 迟，构成二级流水线 – 采样周期可以缩短， 采样率可以提高 – 注意算法结构(BD)的变化 y(n-1) = ax(n-1) + bx(n-2) + ax(n-3) 处理后的样点输出比原来延迟了一拍，即推后了一次迭代
• • • • • • • • •
2011-3-20
硬件资源占用：规模或面积 执行速度：吞吐率或时钟速率 功耗：完成给定任务的能耗 精度：有限字长效应(量化噪声和舍入噪声的因素) 语音：合成、编解码(声码器)、识别；音频：编解码 图像：编解码、识别；视频：编解码 通信：调制与解调、信道编码、检错纠错 导航：波束成形 信息安全：对称密码、非对称密码、Hash函数、随机数、 数字签名
– 采样周期 – 迭代周期
• 输入信号样点间隔的时间 • 取决于应用需要：语音、图像等各不相同 • 完成一次迭代的时间；系统处理一个输入样点、产生一 个输出样点的时间 • 取决于时钟周期和产生输出样点数 • 吞吐率：每秒处理的样点数，为迭代周期的倒数
– 时钟周期
• DSP系统工作所用的时钟周期 • 取决于 DFG的关键路径
2011-3-20 清华大学微电子学研究所 陈弘毅
y(n-1)
15
三 流水线与并行处理(续)
– 数据调动情况：从连续的样点输入序列来看
(迭代 )
(节点 1经 D后 )
任何时刻都有1个样点输入、以及前一个样点被计算出来输出
– 流水线系统的讨论
• 关键路径的减少
– 关键路径指DFG中以下四种无延迟路径中最长的路径：
– 为什么要除以延迟数？因为
» 存在两组独立的优先顺序约束，一组偶迭代和 一组奇迭代
– 环路边界
» 系统能够设置两套硬件并行处理
边延迟数提供了并行实现的空间
2011-3-20 清华大学微电子学研究所 陈弘毅 8
二 迭代边界(续)
例 3：右图下
– 右图下的环路边界与右图上的环路边界相同 存在两组独立的优先顺序约束， 每组 A与 B 迭代编号交错 TLoopBond = (2+4)/2 = 3
• 教材：
– “ VLSI数字信号处理系统——设计与实现”，K.K.Parhi 著，机械出版社，2004。定价：65元。出版社电话： 88378991、 88378994 – ―VLSI Digital Signal Processing Systems – Design and Implementation‖, Keshab K. Parhi, John Wiley & Sons, 1999。机械出版社影印本定价：79元
– 迭代边界
• 环路边界：环路边界是在一次迭代内的平均执行时间
• 迭代边界：关键环路的环路边界T
– 给出该环路迭代周期的下限 – 在延迟元件最大限度减少关键路径的情况下， Tc TL/wL – 给出 DFG所有环路迭代周期的下限 – 在延迟元件最大限度减少关键路径的情况下， Tc T
• 既使 DSP系统无限提高计算能力，迭代周期迭代边界 • 计算迭代边界的算法(略)
2011-3-20 清华大学微电子学研究所 陈弘毅 5
一 引言(续)
– 数据流图，DFG(Data-Flow Graph)
• DFG只示出一次迭代过程 • 节点
– 表示算法中计算(或功能 )的执行 – 包含关联的计算时间： (数字)
D
• 有向边
– 表示节点间通信关系 – 包含关联的非负延迟Z-1或 D
A0 B1 A2 B3 A4 B5。。。 A1 B2 A3 B4 A5 B6。。。
例 4：下图ຫໍສະໝຸດ TLoopBond = (3+6+21)/3 = 10
2011-3-20
清华大学微电子学研究所 陈弘毅
9
二 迭代边界(续)
– 迭代边界
• 关键环路：具有最大环路边界的环路 • 迭代边界：关键环路的环路边界T
2011-3-20
清华大学微电子学研究所 陈弘毅
6
二 迭代边界
• 路径与关键路径
– 路径：数据在任意两节点间经有向边和中间节点的通路。对无延迟路 径，关心所用时间，所以无延迟路径的长度指所有节点计算时间的总 和 – 关键路径：DFG中在不包含延迟单元的路径中执行计算时间最长的路 径 Tc。右图例中，Tc= 6u.t. 下图例中有三条无延迟路径：
– 最长路径矩阵(LPM ) – 最小环路均值(MCM)
2011-3-20 清华大学微电子学研究所 陈弘毅 13
三 流水线与并行处理
• 引言
– 处理一个新样点最少所需要的时 间由关键路径Tc决定。则采样周 期 Ts Tc – 可以通过两种方法来提高采样率
• 流水线(Pipelining)
– 在数据通路中插入流水线锁存器 (寄存器、延迟元件)来减少有效的 关键路径 – 在 DSP系统中达到提高时钟频率 (或采样速度)
• 4 2 1， 4u.t. • 5 3 2 1， 5u.t. • 6 3 2 1， 5u.t.
(1) 1 (1) 2
(1) 3
2D
(2) (2) (2)
• 与迭代有关的问题
则关键路径为Tc=5u.t.
4 5
O D O
6 O – 迭代：DFG中所有节点执行一次 – 迭代周期Tit是处理一个输入样点并输出一个结 果所需时间 – 时钟周期Tclock ：系统按拍工作的周期，由关键 路径 Tc决定。系统时钟频率f则为Tclock的倒数 – 采样周期Ts：根据实时要求必须满足TsTit(Tc) 采样率fs则为Ts的倒数，必须满足 fs f
2011-3-20 清华大学微电子学研究所 陈弘毅 16
三 流水线与并行处理(续)
• 流水线的优缺点
– 优点：减少Tc ，提高系统的时钟频率fclock，从而fs可以提高 – 缺点
» 增加锁存器硬件开销 » 增加迟滞时间(Latency)：迟滞时间指从第一个样点输入系统到系 统输出处理完的第一个样点所需要的延迟数
– 若环路延迟数wL = 0，则 TL / 0 = ，不可计算，环路冲突 – 换言之，必须是因果系统： 非因果系统无法硬件实现TL/wL