一种低功耗抗串扰的自适应时空总线编码方法
刘 毅
①
②
①②
钟广德 杨银堂
*①①②
(西安电子科技大学微电子学院 西安 710071)
(宽禁带半导体材料与器件教育部重点实验室 西安 710071)
摘 要：深亚微米片上总线的功耗、布线面积约束和线间串扰是限制总线数据吞吐率的关键因素，为此该文提出一种自适应时空编码方法以降低总线的串扰延迟和功耗。该方法首先采用空间编码将总线分割为两个子总线，从而减小了恶性串扰发生几率；然后通过恶性串扰判决器分别判断子总线的原码数据及反码数据是否存在恶性串扰：对于任意子总线的原码数据与反码数据均存在恶性串扰的情况，传送屏蔽字；否则，选取无恶性串扰且动态功耗小的总线数据形式并传送。采用SPEC标准数据源对算法进行了评估，该方法在消除恶性串扰的同时使总线数据吞吐率提高了62.59%~81.62%，功耗比同类方法降低14.63%~54.67%，对于32位数据总线，仅需7根冗余线，在动态功耗、布线资源和性能方面获得了有效的优化。
关键词：总线编码；时空编码；串扰延迟；吞吐率；低功耗
中图分类号：TN402 文献标识码： A 文章编号：1009-5896(2011)-04-0945-06 DOI: 10.3724/SP.J.1146.2010.00895
A Low Power Adaptive Spatio-temporal Bus
Coding for Crosstalk Avoidance
Liu Yi
①
②
①②
Zhong Guang-de Yang Yin-tang
①①②
(School of Microelectronics, Xidian University, Xi’an 710071, China)
(Key Laboratory of Ministry of Education for Wide Band-Gap Semiconductor Materials and Devices, Xi’an 710071, China)
Abstract: The power consumption, wiring overhead and crosstalk in deep sub-micron on-chip buses are the main facts restricting the bus throughput. An adaptive spatio-temporal bus coding scheme is proposed to reduce crosstalk induced delay and power consumption in the buses. Firstly, on-chip bus is partitioned into two sub-buses by spatio coding to reduce the Worst-Case-Crosstalk (WCC). Then, decisions are made respectively in the two sub-buses whether the original code and inverted code should incur WCC through an arbiter CCA (Crosstalk Class Arbiter). In the case of both original and inverted codes in any sub-bus incurring WCC, a shielding pattern is transmitted; otherwise the WCC-free and energy saving code is transmitted. The proposed scheme is evaluated using the SPEC benchmarks. The results show that the proposed scheme improves the throughput by 62.59% to 81.62% over the un-coded approach and reduces the power consumption by 14.63% to 54.67% compared to the other similar schemes while eliminating the WCC with only 7 wires overhead for a 32 bit bus. The scheme achieves a good enhancement in dynamic power, wiring overhead, and performance.
Key words: Bus coding; Spatio-temporal coding; Crosstalk delay; ThroughPut (TP); Low power
1 引言
随着集成电路特征尺寸的减小，深亚微米(Deep Sub-Micron，DSM)及纳米工艺互连线间耦合电容引起的串扰效应更加严重，导致集成电路性能下降甚至功能出错，同时还会增加互连线的动态功
2010-08-24收到，2011-01-12改回
国家杰出青年基金(60725415)，国家自然科学基金(60476046，60676009)和中央高校基本科研业务费专项资金(K50510250004)资助课题
*通信作者：钟广德 zhongguangde@yahoo.com.cn
耗[1−3]。如何消除片上总线(全局互连线)中的恶性串扰成为提高芯片性能的关键。通过总线编码技术可以有效消除互连线间的恶性串扰，从而提高总线的工作频率和可靠性，进而提高总线的数据吞吐率(单位时间总线传送的有效数据量)。主要有两种实现思路：空间编码(spatio encoding)[4,5]，通过扩展总线位宽来消除恶性串扰；时间编码(temporal encoding)[6−9]，采用多周期传送数据以消除恶性串扰。编码处理后，总线可工作在更高的频率，使总线性能得到提高。值得注意的是：空间编码方法虽
946 电 子 与 信 息 学 报 第33卷
使总线工作频率提高约一倍，但其布线开销(冗余线)
会增加30%以上[4,5]；时间编码方法虽没有额外布线开销，但需双周期或多周期传送数据，数据吞吐率提高有限。此外，这两类方法均会增加相邻信号线上耦合电容带来的动态功耗[7,8]。
针对DSM总线的功耗、布线面积和线间串扰等约束给总线数据吞吐率提高带来的诸多限制，本文结合上述两种编码思想各自的优点，提出一种自适应时空总线编码算法(ASTC)：采用空间编码将总线分割为两个子总线、同时判断子总线数据的原码与反码是否存在恶性串扰以减少恶性串扰发生几率；采用低功耗自适应时间编码抑制恶性串扰，仅在发生恶性串扰的数据间插入屏蔽字，否则，对于原码与反码均无恶性串扰的子总线，按功耗小的数据形式发送，可以有效节约布线资源，降低总线信号的活动性，提高总线数据吞吐率。该方法可以在总线动态功耗控制、布线资源控制和提高数据吞吐率方面获得折衷的解决方法。
2 自适应时空总线编码原理及电路设计
2.1 编码思想
设CL为总线各位线的对地电容，CI为总线相
邻线间的耦合电容，
λ为耦合电容CI与对地电容CL之比。根据总线的三线模型[8,9]，对于不同的数据翻
转方式，受害线的有效电容可以分为5种情况，对
应的归一化串扰延迟系数如表1所示。其中，情况
4和情况5对应的传播延迟时间最长，称为恶性串
扰情况(Worst Case Crosstalk，WCC)。
表1说明，总线信号的传播延迟时间与相邻信
号变化有关。现有编码方法多通过空间或时间编码
技术杜绝情况4和情况5的发生，达到提高总线工
作频率的目的。而本文编码算法结合了时间编码和
空间编码各自的优点，具体体现在：首先采用总线
表1 3条相邻线不同的翻转方式对受害线总电容和延迟的影响
归一化
情况 有效电容 翻转方式 延迟
系数
1 CL (↑,↑,↑)(↓,↓,↓) 1 2
CL+CI (−,↑,↑)(−,↓,↓) 1+λ (↑,↑,−)(↓,↓, −)
3
CL+2CI (−,↑,−)(−,↓,−)(↑,↑,↓) 1+2λ
(↑,↓,↓)(↓,↑,↑)(↓,↓,↑)
4 CL+3CI (−,↑,↓)(−,↓,↑) 1+3λ
(↑,↓, −)(↓,↑, −)
5 CL+4CI (↑,↓,↑)(↓,↑,↓) 1+4λ
注：↑：0→1翻转 ↓：1→0翻转 −：无翻转 CI：线间耦
合电容 CL：接地电容 λ：CI/CL
分割和翻转编码算法降低总线信号的动态功耗，由于减小了总线信号的活动性，这一步骤还达到了减小恶性串扰发生几率的目的。然后再采用插入屏蔽字的时间编码方法消除恶性串扰，由于此前已经消除了一定比例的恶性串扰数据，总线的数据吞吐率得以提高。
2.2 自适应时空总线编码算法
空间编码采用屏蔽线将32位总线分割为低16位子总线(SUBBUSL)和高16位子总线(SUBBUSH)。某时钟周期t，SUBBUSL对应的原始数据(原码)为Dt[15:0]，反码为~Dt[15:0]，传送数
据为Bt[15:0]；
SUBBUSH对应的原始数据为Dt[31: 16]，反码为~Dt[31:16]，传送数据为Bt[31:16]。Dt[31:0]为时钟周期t总线的原始数据，Bt[31:0]和Bt+1[31:0]分别为时钟周期t和t+1总线传送数据(编码后数据)；state为状态控制信号，state=1时，原始数据保持，state为0时，原始数据更新；inv[0]和inv[1]分别为SUBBUSL和SUBBUSH传送数据形式的标识信号，‘0’表示原码传送，‘1’表示反码传送；flag为屏蔽字标识信号，‘1’表示当前总线
传送数据是屏蔽字，‘0’表示当前传送数据是有效
数据；“CCA”为恶性串扰判决器，用于判断当前信
号是否存在恶性串扰，“DPC”为动态功耗比较器，
用于比较子总线的原码数据与反码数据所消耗的动
态功耗的大小。
表2为ASTC编码算法伪代码。当子总线原始
数据的原码和反码都存在恶性串扰时，称为子总线
存在恶性串扰。子总线SUBBUSL和SUBBUSH的
编码过程类似，以下着重介绍低16位子总线
SUBBUSL的编码过程。
第1步 通过恶性串扰判决器“CCA”判断时
钟周期t总线原始数据Dt[31:0]低16位的原码
Dt[15:0]和反码~Dt[15:0]与SUBBUSL传送数据Bt[15:0]之间是否存在恶性串扰，如果存在恶性串
扰，则置“CCA”相应的输出状态位stateL1和
stateL2为逻辑‘1’，否则置为逻辑‘0’，SUBBUSH
进行相同操作；状态控制信号state=(stateL1 &&stateL2)||(stateH1&&stateH2)。 第2步 根据状态控制信号state的状态决定下一个时钟周期总线传送数据Bt+1[31:0]及其相应标
识信号(inv[1:0]和flag)的状态。 如果两个子总线中任意一个存在恶性串扰，即state=1，则在整个总线上插入32-bit全‘1’屏蔽字，标志位inv[1:0]保持不变，原始数据Dt[31:0]保持，设置flag=1，表示总线传送数据是屏蔽字；否则，两个子总线都不存在恶性串扰，即state=0，进 第4期 刘 毅等：一种低功耗抗串扰的自适应时空总线编码方法 947
表2 编码算法伪代码
Encoding: Input: Dt[31:0], Bt[31:0]; Output: Bt+1[31:0], state, inv[1:0], flag
第1步：
if(CCA(Dt[15:0],Bt[15:0])) if(CCA(Dt[31:16],Bt[31:16])) {stateL1=1; } {stateH1=1; } else{stateL1=0; }
else{stateH1=0; }
if(CCA(~Dt[15:0],Bt[15:0])) if(CCA(~Dt[31:16],Bt[31:16])) {stateL2=1; } {stateH2=1; } else{stateL2=0; }
else{stateH2=0; }
state=(stateL1&&stateL2)||(stateH1&&stateH2)； 第2步：
if(state=1)
{flag=1; Bt+1[15:0]=16hFFFF; Bt+1[31:16]=16hFFFF; } else {flag=0;
if((stateL1=0)&&(stateL2=0)) if((stateH1=0)&&(stateH2=0)){if(DPC(Dt[15:0],Bt[15:0])>8) {if(DPC(Dt[31:16],Bt[31:16])>8){inv[0]=1;
{inv[1]=1;
Bt+1[15:0]=~Dt[15:0]; }
Bt+1[31:16]=~Dt[31:16]; }
else else {inv[0]=0;
{inv[1]=0;
Bt+1[15:0]=Dt[15:0]; }
Bt+1[31:16]=Dt[31:16]; }
} }
else
else
{if(stateL1=0) {if(stateH1=0) {inv[0]=0;
{inv[1]=0;
Bt+1[15:0]=Dt[15:0]; }
Bt+1[31:16]=Dt[31:16]; }
else else {inv[0]=1;
{inv[1]=1;
Bt+1[15:0]=~Dt[15:0]; }
Bt+1[31:16]=~Dt[31:16]; }
} }
}
行如下操作：如果原码Dt[15:0]和反码~Dt[15:0]与Bt[15:0]均不存在恶性串扰(stateL1=0且stateL2 =0)，则通过动态功耗比较器“DPC”选取功耗较低的数据作为下一周期子总线传送数据B~t+1[15:0]；否则原码Dt[15:0]和Bt[15:0]或反码Dt[15:0]和Bt[15:0]其中之一存在恶性串扰(‘stateL1=0且stateL2=1’或者‘stateL1=1且stateL2=0’)，此时，选取无恶性串扰的数据作为下一周期子总线传送数据Bt+1[15:0]，即，如果stateL1=0，则传送原码Dt[15:0]，否则传送反码~Dt[15:0]；根据SUBBUSL传送数据的类型设置标识位inv[0]的状态，SUBBUSH进行相同操作；原始数据更新，设置flag=0，表示总线传送数据是有效数据。
动态功耗比较器“DPC”的原理为：如果总线在前后两个周期传送数据的海明距离越小，则总线
自身翻转消耗的能量也越小，通过“DPC”分析原
码Dt[15:0]与Bt[15:0]间的海明距离，如果Dt[15 :0]与Bt[15:0]的海明距离大于常数“8”，那么
SUBBUSL传送反码~Dt[15:0]消耗的能量较小，
否则传送原码Dt[15:0]消耗的能量较小。
解码算法如表3所示。如果flag=1，则表示当前接收的数据为屏蔽字，下一周期编码器的输出DOUTt+1[31:0]保持原状态DOUTt[31:0]不变；否则flag=0，低16位和高16位子总线分别根据相应的标志信号inv[0]和inv[1]的状态决定下一周期编码器的输出DOUTt+1[31:0]。
表3 解码算法伪代码
Decoding: Input: inv[1:0], flag, Bt[31:0]; Output: DOUTt+1[31:0]
if(flag=1) { DOUTt+1[31:0]=DOUTt[31:0]; } else
{if(inv[0]) { DOUTt+1[15:0]=~Bt[15:0]; } else { DOUTt+1[15:0]=Bt[15:0]; } if(inv[1]) { DOUTt+1[31:16]=~Bt[31:16]; } else { DOUTt+1[31:16]=Bt[31:16]; } }
2.3 编解码电路设计
图1为ASTC算法的电路原理图。图1(a)为编码电路，图1(b)为解码电路。32位总线被分割为低16位子总线SUBBUSL和高16位子总线SUBBUSH，在这两个子总线的边界处插入屏蔽线以使二者相对独立，两个子总线之间通过信号state来协调工作且共享标识信号flag，从而实现两个子总线的数据同步传送。图1中“CCA”和“DPC”分别为“恶性串扰判决器”和“动态功耗比较器”。“CCA”用于判断当前信号是否存在恶性串扰，“DPC”用于比较子总线的原码数据与反码数据所消耗的动态功耗的大小。Bt[31]为Bt[31:0]的第32位数据的复制，用于屏蔽flag信号对总线的影响，flag，inv[0]和inv[1]三者间通过插入屏蔽线消除恶性串扰，图1中其他信号的定义在前文已作说明。
图2为“CCA”的电路原理图，如果子总线传送数据时存在任意3条相邻的信号线，该3条信号线满足：中间线的信号发生翻转，且其相邻的两条线上信号的翻转方向与中间线上信号的翻转方向相反；或者其中两条相邻线上的信号发生相对翻转，另外一条线上的信号保持不变，则判为该子总线存在恶性串扰，“CCA”的输出为‘1’；否则该子总线不存在恶性串扰，“CCA”的输出为‘0’。图3为“DPC”的电路原理图，以低位子总线SUBBUSL为例，首先原码Dt[15:0]与Bt[15:0]按位进行异或
948 电 子 与 信 息 学 报 第33卷
图1 ASTC算法的电路原理图
图2 CCA电路原理图 图3 DPC电路原理图
运算，再通过加法器求出这两个数据总的相异的位数，即海明距离，最后通过比较器作如下判断：如果Dt[15:0]与Bt[15:0]的海明距离大于常数“8”， “DPC”输出为‘1’，SUBBUSL传送反码~Dt[15 :0]，否则“DPC”输出为‘0’，SUBBUSL传送原码Dt[15:0]。
3 实验及结果分析
本文采用Verilog HDL硬件描述语言设计了ASTC的编解码电路，并利用Synopsys公司的Design Compiler综合工具和SMIC 0.13 μm工艺对其进行了综合。根据文献[10]中的互连线的预测模
型，工艺参数λ的取值约在1到4之间。实验中，总线上的数据源是通过在Simplescalar模拟器[11]上运行SPEC95/2000CINT[12]基准程序而获得。
除了本文中提出的ASTC算法外，还对另外两种时空总线编码算法，即双周期时空总线编码(dual-cycle STBE)[8]和动态周期-反转编码(DYN- BI)[9]进行了实验与分析。
表4列出了以上3种时空总线编码算法的主要特征。表中第1列为编码算法；第2列表示编码后总线的串扰延迟，dual-cycle STBE将串扰延迟降到1+λ，ASTC降到1+2λ，DYN-BI本质上并没有抑制恶性串扰，而是缓解串扰对性能的不利影响；
第4期 刘 毅等：一种低功耗抗串扰的自适应时空总线编码方法 949
表4 各种编码算法的特征对比
面积(μm)
2
编码算法 串扰延迟 1+4λ 1+λ 1+4λ 1+2λ
总线位宽
动态功耗(μW/MHz) 关键路径延迟(ns)
En. De. En. De. En. De.
un-coded dual-cycle STBE DYN-BI ASTC
32 0 0 0 0 0 0 45 1523.83 2547.56 2.33 2.82 0.45 0.25 36 6360.06 1556.77 5.50 1.69 2.12 0.66 39 5090.40 1537.95 5.31 1.61 1.17 0.53
第3列为编码后的总线位宽，dual-cycle STBE的冗余线增加了13根(40.63%)，DYN-BI增加12.50%，ASTC增加21.88%，其中dual-cycle STBE的冗余线增加最多，由此引起的总线冗余面积最大；第4列和第5列为编码电路(En.)和解码电路(De.)的面积和动态功耗，dual-cycle STBE编解码电路面积和功耗较小(解码器除外)，但由冗余线引起的面积较大，因此总的面积冗余也较大；ASTC编解码电路的面积和功耗比DYN-BI小；第6列为编解码电路的关键路径延迟，dual-cycle STBE的延迟最小，ASTC的关键路径延迟比DYN-BI的小，这是因为DYN-BI的串扰分析电路较复杂，较小的关键路径延迟有利于提高电路的性能。与未编码的方法(un- coded)相比，这些时空编码方法都引入了一定的面积、功耗等冗余，但编码后数据消除了恶性串扰，提高了传送数据的可靠性，因此系统可工作在更高的时钟频率下，系统传送数据的效率会更高。
根据深亚微米总线模型[13]对以上3种编码算法的数据吞吐率和功耗作如下分析。
图4为λ分别取4和1时各种编码算法的数据
吞吐率提高率(相对未编码的情况)。由图4(a)知，对于不同的数据流，dual-cycle STBE数据吞吐率平均提高了70.00%，DYN-BI平均提高58.35%，ASTC提高62.59%到81.62%(平均为72.13%)，优于前两者。图4(b)为λ=1时的情况，dual-cycle STBE，DYN-BI和ASTC的数据吞吐率相对未编码的情况平均提高量分别为25.00%，16.44%和51.88%。此时，ASTC的吞吐率明显高于dual-cycle STBE和DYN-BI的吞吐率。以上实验结果说明，对不同的工艺参数λ和数据流，ASTC都能获得较高的数据吞吐率。
图5为各种编码算法传送不同数据时在总线上
2
进行了归一化，其中的归一化功耗(功耗已对CLVdd
Vdd为电源电压)。由图5可知，在这3种时空编码方法中，dual-cycle STBE的功耗较大，ASTC的功耗最小。在λ=4时，ASTC的功耗相对dual-cycle STBE和DYN-BI分别降低了54.67%和14.63%；在λ=1时，ASTC的功耗相对dual-cycle STBE和DYN-BI分别降低了53.78%和15.46%。
图4 各种编码算法的吞吐率
图5 各种编码算法在总线上的归一化功耗
950 电 子 与 信 息 学 报 第33卷
4 结论
本文在结合空间和时间编码各自优点的基础上，提出了一种自适应时空总线编码算法以降低深亚微米总线中的串扰延迟和功耗。该方法采用空间编码将总线分割为两个子总线、同时判断子总线数据的原码与反码是否存在恶性串扰以减少恶性串扰发生几率；采用低功耗自适应时间编码抑制恶性串扰，仅在发生恶性串扰的数据间插入屏蔽字；对于原码与反码均无恶性串扰的子总线，按功耗小的数据形式发送。此外，采用SPEC基准对算法的有效性进行了评估，该方法在消除恶性串扰的同时，可以在总线动态功耗控制、布线资源和数据吞吐率方面获得折衷的解决方法。随着工艺的发展，总线上的功耗和串扰将进一步增加，编解码电路面积、功耗却进一步减小，该时空编码方法将更为有效。
参 考 文 献
[1]
Halak B and Yakovlev A. Throughput optimization for area-constrained links with crosstalk avoidance methods[J].
IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2010, 18(6): 1016-1019.
[2]
Singh H, Rao R, and Agarwal K, et al.. Dynamically pulsed MTCMOS with bus encoding for reduction of total power and crosstalk noise[J]. IEEE Transactions on Very Large
Scale Integration (VLSI) Systems, 2010, 18(1): 166-170.
[3]
刘毅，杨银堂，梅伟锋，等. 一种NoC路由器间互连线的自适应驱动方法[J]. 西安电子科技大学学报(自然科学版), 2010,
37(1): 28-32.
Liu Yi, Yang Yin-tang, and Mei Wei-feng, et al.. Adaptive drive approach for interconnection lines between NoC routers[J]. Journal of Xidian University, 2010, 37(1): 28-32. [4]
Victor B and Keutzer K. Bus encoding to prevent crosstalk delay[C]. International Conference on Computer-Aided Design 2001, San Jose, CA, United States, 2001: 57-63. [5]
Duan C, Cordero C V, and Khatri S P. Efficient on-chip crosstalk avoidance CODEC design[J]. IEEE Transactions
on Very Large Scale Integration (VLSI) Systems, 2009, 17(4):
551-560. [6]
Kornaros G. Temporal coding schemes for energy efficient
data transmission in systems-on-chip[C]. Proceedings of the 7th Workshop on Intelligent Solutions in Embedded Systems, WISES 2009, Ancona, Italy, 2009: 111-118. [7]
Shen J S, Hsiungt P A, and Chang K C. A novel spatio-temporal adaptive bus encoding for reducing crosstalk interferences with trade-offs between performance and reliability[C]. 13th IEEE Asia-Pacific Computer Systems Architecture Conference, ACSAC 2008, Hsinchu, Taiwan, China, 2008: 1-8. [8]
Sainarayanan K S, Raghunandan C, and Srinivas M B. Delay and power minimization in VLSI interconnects with spatio-temporal bus-encoding scheme[C]. IEEE Computer Society Annual Symposium on VLSI: Emerging VLSI Technologies and Architectures, ISVLSI'07, Porto Alegre, Brazil, 2007: 401-406. [9]
Li L, Vijaykrishnan N, and Kandemir M, et al.. A crosstalk aware interconnect with variable cycle transmission[C]. Proceedings: Design, Automation and Test in Europe Conference and Exhibition, DATE 04, Paris, France, 2004, 1: 102-107.
[10] Nanoscale Integration and Modeling (NIMO) Group.
Predictive Technology Model. http://ptm.asu.edu/, 2010, 3. [11] Burger D and Austin T M. The simplescalar tool set, Version
2.0[J]. Computer Architecture News, 1997, 25(3): 13-25. [12] SPEC. SPEC CPU2000 Benchmark. http://www.spec.org/,
2010, 3.
[13] Sotiriadis P P and Chandrakasan A P. Bus energy reduction
by transition pattern coding using a detailed deep submicrometer bus model[J]. IEEE Transactions on Circuits
and Systems I: Fundamental Theory and Applications, 2003,
50(10): 1280-1295.
刘 毅： 男，1971年生，副教授，研究方向为高速、低功耗数字
集成电路设计方法.
钟广德： 男，1985年生，硕士生，研究方向为具有串扰抑制功能
的总线低功耗编码设计.
杨银堂： 男，1962年生，教授，博士生导师，研究方向为高速、
低功耗集成电路设计方法.
因篇幅问题不能全部显示，请点此查看更多更全内容