– 2级流水线：M=2 – 设 Vt=0.45V V0=5V – 根据计算 =0.58 – 考虑流水线锁存器 Cpip=1.1C – 电源可降为2.9V 功耗为原始的37%
2011-3-20
清华大学微电子学研究所 陈弘毅
31
三 流水线与并行处理(续)
– 并行处理用于降功耗
• 对 L级并行处理系统
2011-3-20
清华大学微电子学研究所 陈弘毅
42
四 重定时(续)
• 小结：重定时
– 在不改变系统的输入输出特性的前提下，改变电路延迟元件 的配置 – 重定时的重要性质
– 重定时技术
• 不改变环路中的总延迟数 • 不改变DFG的迭代边界T • 割集重定时
– 在割集的各反向边增减相同的延迟数 – k倍降速 (k-slow)技术
» 子图 1中节点取0 » 子图 2中节点取k
1 0
0
• 一般割集的重定时
1
0
• 节点重定时：非常有用
– 割集围绕节点 – 右下图例： r(1)=0, r(2)=1, r(3)=0, r(4)=0
2011-3-20
1 0
0
割集围绕节点的重定时 37
清华大学微电子学研究所 陈弘毅
四 重定时(续)
• 前馈割集重定时：流水线(无环路)系统，属割集重定时的特殊情况
• 可见：展开 并行处理
– 应用
• 发掘算法潜在的并发性，采用并行处理来降低迭代(采样)周期，(对 环路来说)向迭代边界T逼进 • 得到位/字级并行架构，位串行位并行或字串行、字串行字并行 • 展开 =环路展开(Loop Unrolling)，应用于汇编编程、编译理论
2011-3-20 清华大学微电子学研究所 陈弘毅 45
清华大学微电子学研究所 陈弘毅 36
四 重定时(续)
• 重定时技术
– 割集重定时：在割集的各反向边增减相同的延迟数
• 规则
– 重定时值r(V)
– 所有路径权重wr(p)0 – 在所有某向边增加 k个延迟数 – 在所有反向边减去 k个延迟数 – 右上图例：r(1)=0, r(2)=1, r(3)=0, r(4)=1
2011-3-20 清华大学微电子学研究所 陈弘毅 35
四 重定时(续)
• 关于重定时的一般化方法：定义、性质和求解
– 定义
• 重定时：将一个电路G映射到一个重定时电路Gr ，即 G Gr • 重定时值：每个节点V的重定时值r(V) 用来表征G Gr的重定时解 • 重定时方程：用来确定节点U到V的边UV(e)重定时后的权重
– 充放电电容不变，但是总负载电容增加L倍 – 关键路径不变，但是每个时钟周期处理L个样点 – 为保持原来的采样速率，L级并行处理系统的时钟周期增加为 LTseq (Tseq是原始时序电路的传播延时)。这意味着负载电容充 放电时间长L倍(即 LTseq)，则电源电压可以减低到V0 – 利用原始系统与并行处理系统传播延时的公式
五 展开(续)
• 展开的算法
– 符号
• x：表示对x向下取整，即取小于或等于x的最大整数 • x：表示对x向上取整，即取大于或等于x的最小整数 • a% b(或 amodb)：表示a除以b的余数，其中a和b是整数
• 节点 U：有 J个具有相同功能的节点Ui (i=0, 1, …, J-1) • 边：有 J条相应的边 即： J阶展开后的DFG总是包含了相当于原始DFG的 J倍 数量的节点和边
2011-3-20
清华大学微电子学研究所 陈弘毅
44
五 展开(续)
– 展开特点
• 上例变换后的两个公式描述的连续迭代是原式的一个二阶展开(2unfolding)版本 • 在 J阶展开系统中，每个延迟元件是J倍降速(J-slow)的
– 如果输入到一个延迟单元的信号是x(kJ+m)，则该延迟单元的输出是 x((k-1)J+m)=x(kJ+m-J)
2011-3-20 清华大学微电子学研究所 陈弘毅 29
三 流水线与并行处理(续)
• 功耗降低因子Βιβλιοθήκη 的求法– 利用原始系统与流水线系统传播延时的公式
– 根据：Tseq ＝ Tpip，有
• 流水线系统的功耗为
2011-3-20
清华大学微电子学研究所 陈弘毅
30
三 流水线与并行处理(续)
• 例1：简单数据通路
– 流水线用于降功耗：仅做宏观估计
• 原始时序系统(如 FIR滤波器)中的功耗
• 对 M级流水线系统
– 关键路径减少为原始的 1/M (fs可以提高M倍 ) – 在单个时钟周期要充放电的负载电容也减少为原始的1/M (但是总负载 电容不变 ) – 时钟速度 fs保持不变前提下降低功耗：在相同时间 Ts内，只需对原始电 容的 1/M部分充放电，意味着电源电压V0可以降低到V0 (0< <1)，即 功耗降低 2倍。称功耗降低因子
– J阶展开DFG的节点与边
– 构建一个 J阶展开DFG
• 对原始 DFG中的每个节点U，画J个节点U0, U1, …, UJ-1 • 对在原始 DFG中的每个延迟为w的边UV，画延迟为 wunf(i)=(i+w)/J的 J个边UiV(i+w)%J (i=0, 1, …, J-1)
2011-3-20 清华大学微电子学研究所 陈弘毅 46
– 由不等式组画出约束图，用最短路径求出所有节点重定时值解r
2011-3-20 清华大学微电子学研究所 陈弘毅 43
五 展开
• 引言
– 展开 (Unfolding)：是一种转换技术，它产生一个新的程序来 描述原有程序的多次迭代，J称展开因子，表示迭代次(阶 ) 数
• 例子：对DSP程序y(n)=ay(n-9)+ x(n)进行2阶展开 y(2k)=ay(2k-9)+ x(2k)= ay((2(k-5)+1)+ x(2k) y(2k+1)=ay(2k-8)+ x(2k+1)= ay((2(k-4)+0)+ x(2k+1)
2011-3-20 清华大学微电子学研究所 陈弘毅 33
三 流水线与并行处理(续)
– 流水线与并行处理结合降功耗
• 流水线与并行处理结合可以更有效降功耗
– 流水线减少在一个时钟内的充/放电电容 – 并行处理增加对原始电容充/放电时钟周期 – 并行流水系统传播延时 – 求解 的方程
• 功耗降低因子的求法
• 一般的重定时流程(略)
– 给出重定时目标：例如时钟周期c – 计算最小延迟路径权重 W(U, V)和最长路径的计算时间D(U, V)：可直接 从 DFG求出 – 由约束条件列出不等式组
» 可行性约束(权重非负 )：对 UV来说，要求 r(U)-r(V) w(e) » 关键路径约束 (权重非负)：对(U, V)之 D(U, V) c时，要求插入延迟，即r(U)r(V) W(U, V)-1
– 前馈割集的边都是同向的，则都加个 k延迟，无反向边 – 右图 4阶 FIR滤波器可以在割集 的两个同向边都加一个延迟
• k倍降速(k-slow)后的割集重定时
– 用 kD取代 D：如下图右，k=2
» » » » 是 Tclk不变的降速 隔 1时钟输入1样点，奇数时钟插入空操作 硬件利用率50% 时钟周期不变，Tclk=2 u.t. ，迭代周期加倍，Titer=4 u.t.
– 重定时前后的权重(即延迟数)：分别为 w和wr – G中所有节点按重定时值r(U)、 r(V)、。。。进行重定时 – G Gr的重定时解满足重定时方程
– 重定时性质：可由重定时方程导出
– 重定时流程(略)
2011-3-20
• 对于重定时的路径p= V0 V1 … Vk，其权重由下式计算 wr(p) = w(p)+r(Vk)-r(V0) 只与路径起始、终止节点的重定时值相关 • 重定时不改变环路中的总延迟数：因为环路之Vk=V0 • 重定时不改变DFG的迭代边界T：T=TL/wL ，因为环路的运行时间 和延迟数都不变化 • 所有节点重定时值r(V)都增加常数值j， 重定时映射G Gr不变
加
乘a
–2阶展开图中的边
» 无延迟边 AC 、 C B 、 D C都展开为连接相应节点的两条边 » 延迟 9D(w=9)的边 CD展开为两条边：延迟4D(wunf=(0+9)/2=4)的 边 C0 D1(D(0+9)%2＝ 1)和延迟 5D(wunf= (1+9)/2=5) C1 D0(D(1+9)%2＝ 0) 当 w<J时，展开原始DFG中延迟为w的边，相当于在J阶展开DFG中 生成了 J-w条无延迟的边和 w条延迟为1的边
• 例 3：前述简单数据通路，见下页图
– 2级并行＋2级流水：L= M= 2 – 设 Vt=0.45V； V0=5V – 根据计算：=0.4 – 考虑多路器和锁存器影响：Ctotal=2.35C – 电源可降为2V 功耗为原始的19%
2011-3-20 清华大学微电子学研究所 陈弘毅 34
四 重定时
• 割集重定时可以多次使用，以便取得优化的性能
2011-3-20 清华大学微电子学研究所 陈弘毅 40
四 重定时(续)
2011-3-20
清华大学微电子学研究所 陈弘毅
41
四 重定时(续)
例子：递归滤波器，下图， G Gr
• • • • 已知重定时值为：r(1)=0, r(2)=1, r(3)=0, r(4)=0 wr (2 1)=w (2 1)+r(1)-r(2)=0 wr (3 2)=w (3 2)+r(2)-r(3)=1 wr (4 2)=w (4 2)+r(2)-r(4)=1
三 流水线与并行处理(续)
• 流水线与并行处理用于降低功耗
– 流水线与并行处理的优点：提高速度、降低功耗 – CMOS电路的两个简化了的公式