（通信与信息系统专业论文）noc总线编码技术研究.pdf

摘要 摘要 深亚微米工艺给v l s i 电路设计者带来了许多新的挑战，片上通信已成为片上 系统( s o c ，s y s t e m o n c h i p ) 性能提升的瓶颈。随着集成电路特征尺寸的缩小、供 电电压的减小、互连密度的增大、时钟速度的加快，全局片上通信存在如下三个 主要问题：由寄生电容和耦合性电容造成的高功耗，由电容性串扰所产生的大传 输延时和由深亚微米噪声所引发的低可靠性。作为未来s o c 的发展方向，片上网 络( n o c ，n e t w o r k o n c h i p ) 各节点间的低功耗、高速和可靠通信是关键。因而， n o c 总线设计必须考虑上述三个问题。 对于基于深亚微米总线的片上通信，目前的研究工作主要集中于总线编码技 术。通过增加一些冗余信息，总线编码可以很好地消除串扰影响，同时可以提供 一些差错控制特性以对抗噪声干扰。基于片上网络，本文从总线编码角度出发， 主要从以下三个方面进行研究： 第一，论述了深亚微米总线的一些特点，以及总线功耗、延时和可靠性模型。 对现有的总线编码技术，包括低功耗码、串扰避免码和差错控制码进行了分析， 为设计新的编码方案奠定基础。 第二，为了能够同时处理功耗、延时和可靠性问题，本文基于统一编码框架 论述了一种新的联合码s e c d a e d s d a e c + d a - p 码，即基于不等能力保护码 和串扰避免码的综合码。针对n o c 信息包结构，该联合码对信息的不同部分提供 了不同级别的保护能力，即为信息头部的路由信息提供了更强保护能力，同时还 联合串扰避免码以降低传输延时。通过采用s m i c0 1 3 u r nc m o s 工艺的仿真结果 表明，与未编码方案相比，在同等可靠性要求下，对1 0 m m3 2 b i t 并行总线采用该 联合编码方案，可以获得3 8 2 5 的功耗改善和1 5 8 9 倍的速度提升。 第三，在基于包交换的n o c 中，目前的总线编码设计主要采用基于整体编码 的设计方式。由于路由节点要对所转发的信息包进行整体解码以得到路由信息， 从而使得片上通信整体功耗和延时受路由路径的影响非常大。针对n o c 信息包结 构，本文采用了一种针对包头局部编解码的分组混合编码设计方式，并基于该混 合编码设计方式讨论了一种h c t r i p l e h s i a o d u p 码。由仿真结果可以看出， h c t r i p l e h s i a o d u p 码在速度增益、功耗收益和面积开销方面的改善趋势要优于 其它基于整体编码设计方式的编码方案。当平均h o p s 为4 时，h c t r i p l e - h s i a o d u p 摘要 码的速度增益和功耗收益分别为1 7 和4 2 。 关键词：片上网络，低功耗码，串扰避免码，差错控制码，混合编码设计方式 h 一 丝兰坐竺! _ - _ _ _ _ l _ 一一 a b s tr a c t d e 印s u b m i c r o ( d s m ) p r o c e s s e sp r e s e n tm a n yc h a l l e n g e st ov e r yl a r g es c a l e i n t e g r a t i o n ( v l s i ) d e s i g n e r s ，a n do n c h i p c o m m u n i c a t i o nh a sb e c o m eam a j o r p e r f o m l a l l c eb o t t l e n e c ko fs y s t e m o n c h i p ( s o c ) w i t hs h r i n k i n g f e a t u r es i z e ，s c a l i n go f s u p p l yv o l t a g e ，i n c r e a s i n gi n t e r c o n n e c td e n s i t ya n df a s t e rc l o c kr a t e s ，g l o b a lo n c h i p 0 0 】：n m u i l i c a t i o ns u f f e r sf r o mf o l l o w i n gt h r e em a j o ri s s u e s ：h i g hp o w e rc o n s u m p t i o n d u e t ob o t hd a r a s i t i ca n dc o u p l i n gc a p a c i t a n c e ，l a r g ep r o p a g a t i o nd e l a yd u et oc a p a c i t i v e c r o s s t a l ka n di n c r e a s e ds u s c e p t i b i l i t yt oe r r o r sd u et od e e ps u b - m i c r o n ( d s m ) n o i s e f m l 】r es o c sw mf o l l o wt h en e t w o r k - o n - c h i p ( n o c ) p a r a d i g m ，w h e r ee n e r g y e f f i c i e n t ， t l i 出s p e e da n dr e l i a b l ec o m m u n i c a t i o nb e t w e e nv a r i o u ss o cc o m p o n e n t s l sv i t a l ，a n d n o cb u sd e s i g n e r sm u s tt a k et h et h r e ep r o b l e m sa b o v ei n t oa c c o u n t a sf o rt h ed e e ps u b - m i c r o nb u sb a s e do n c h i pc o m m u n i c a t i o n ，c u r r e n tr e s e a r c h w o r km a i n l yf o c u s e so nb u se n c o d i n gt e c h n i q u e s b ya d d i n g s o m er e d u n d a n t m f b n n a t i o n b u se n c o d i n gc a ne l i m i n a t ec r o s s t a l kw e l l ，a n da l s op r o v i d es o m ee r r o r c o l 内的lf e a t u r e st oc o m b a tn o i s e b e 百n sw i t hn o c - b a s e db u se n c o d i n gt e c h n i q u e s ，t h i s t h e s i ss h o w s0 1 1 1 r e s e a r c h e so nt h ef o l l o w i n gt h r e ea s p e c t s ： f i r s t l v d i s c u s s e ds o m ef e a t u r e so fd e e ps u b m i c r o nb u s e s ，m o d e l o fp o w e r c o n s u m p t i o n ，d e l a ya n dr e l i a b i l i t y t h e n ，a n a l y z e dt h ee x i s t i n gb u s e n c o d i n gt e c h n i q u e s r s u c ha sl o wp o w e rc o d i n g , c r o s s t a l ka v o i d a n c ec o d i n ga n de r r o rc o n t r o lc o d i n g ) ，w m c n l a yaf o u n d a t i o nf o r f u t u r eb u sc o d i n gs c h e m e s s e c 0 n d l y i no r d e rt oa d d r e s st h e t h r e ep r o b l e m ss i m u l t a n e o u s l y , t h i st h e s i s p r o p o s e dan e wc o m p r e s s i v ec o d i n gs c h e m es e c - d a e d s d a e c + d a p , w h i c h j o i n t s u 】 1 e q u a le r r o rp r o t e c t i o nc o d ea n dc r o s s t a l ka v o i d a n c ec o d e b a s e do nt h eu n i t e dc o d i n g 丘a m e w o r k a c c o r d i n gt op a c k e tf o r m a to fn o c ，t h ep r o p o s e dc o d i n gs c h e m ep r o v i d e s u n e q u a le r r o rp r o t e c t i o na b i l i t i e sf o r d i f f e r e n tp a r t so ft h ep a c k e t ，w h e r e i nr o u t i n g i n f o m a t i o ni nh e a d e rp a r th a sm u c hm o r ea b i l i t yf o re r r o rc o r r e c t i o n a n dt h i sc o d i n g s c h a n eh a sc i 0 s s t a l ka v o i d a n c ef e a t u r et or e d u c ed e l a y , t o o w h e na p p l i e dt oa10 - r r m l 3 2 - b i tp a r a l l e lb u si ns m i co 13 u r nc m o st e c h n o l o g yw i t h o u ta n yl o s si nr e l i a b i l i t y , t h es i i n u l a t i o nr e s u h ss h o wt h a tt h ep r o p o s e ds c h e m eh a s38 2 5 p o w e rc o n s u m p t i o n i i l a b s t r a c t 一 i m p r o v e m e n ta n da1 5 8 9s p e e d - u po v e rt h e u n c o d e db u s t h i r d l y , i np a c k e t s w i t c h i n gb a s e dn o c ，c u r r e n tc o d i n gs c h e m e sm a i n l ya i ma t o v e r a l lc o d i n gb a s e dd e s i g nm o d e i no r d e rt og e tm er o u t i n gi n f o r m a t i o n ，n e e d d i n gt o d e c o d et h er e c e i v e dp a c k e ti n t e g e r a l l yi n r o u t e rn o d e ，w h i c hm a k er o u t i n gp a t h i n f l u e n c et h eo v e r a l lp o w e rc o n s u m p t i o na n dd e l a yo fo n - c h i pc o m m u n i c a t i o nv e r y m u c h t a k i n gp a c k e tf o r m a to fn o ci n t oa c c o u n t ，t h i st h e s i sa p p l i e dah y b r i dc o d i n g d e s i g nm o d ew h i c hb a s e do np a r t i a lc o d i n gf o rh e a d e rp a c k e t b a s e do nt h eh y b r i d c o d i n gd e s i g n m o d e ，t h i st h e s i s t h e n p r o p o s e d a j o i n tc o d i n g s c h e m e h c t r i p l e h s i a o d u p a sm a n i f e s t e db yt h es i m u l a t i o nr e s u l t s ，h c - t r i p l e - h s i a o - d u p h a sm u c hb e t t e ri m p r o v e m e n tt r e n di na s p e c t so fs p e e d - u p ，e n e r g y - s a v i n g a n d a r e a - o v e r h e a do v e ro t h e rc o d i n gs c h e m e sw h i c hb a s e do no v e r a l lc o d i n gd e s i g nm o d e w h e nt h ea v e r a g eh o p sa r e4 ，h c - t r i p l e - h s i a o - d u pa c h i e v e s1 7s p e e d - u pa n d4 2 e n e r g y - s a v i n go v e rt h eu n c o d e db u s k e y w o r d s ：n e t w o r k o n c h i p ，l o wp o w e rc o d e ，c r o s s t a l ka v o i d a n c ec o d e ，e r r o rc o n t r o l c o d e ，h y b r i dc o d i n gd e s i g nm o d e i v 图目录 图目录 图1 1 门延时、线延时与集成工艺特征尺寸的关系1 图1 2 通用编码系统框图3 图1 3d s m 的分布式r c 总线模型3 图1 - 4 分裂编码框图7 图1 5m i l l e r 效应8 图2 1 对8 - b i t 数据字进行b i c 编码。1 3 图2 2 对最大耦合p = l 的禁用过渡模式1 8 图2 3 对大总线进行o l c ( 8 ，4 ) 分裂编码1 9 图2 4 边界比特重叠码编码框图2 2 图2 5 禁用模式边界比特重叠编码2 4 图3 1 统一总线编码框架3 2 图3 2 联合l p c 和e c c 码。3 3 图3 3d a p 和d s a p 码的编译码框图3 4 图3 4d a p b i 码的编译码框图3 5 图3 5n o c 存储转发路由策略的信息包结构3 6 图3 - 6s e c d a e d s d a e c 对n o c 信息包的纠错能力3 7 图3 7 联合( 8 ，2 4 ，6 ) s e c d a e d s d a e c 码和d a p 码的编码框图。3 8 图3 8s e c d a e d s d a e c + d a p 码的译码流程图3 9 图3 - 9s m i c0 1 3 u r nc m o s 工艺下的7 层金属分布4 0 图3 1 0 并行总线在第4 金属层排列情况4 1 图3 1 1 相对于3 2 - b i t 未编码总线的速度增益4 4 图3 1 2 相对于3 2 - b i t 未编码总线的功耗收益4 5 t 图目录 图3 1 3l = 1 0m i l l ，五= 3 2 4 9 2 时，功耗，面积和延时间的权衡4 6 图4 14 x 4 n o cm e s h 网络拓扑结构4 8 图4 2n o c 路由结构中的编码方案4 9 图4 3 三重码编译码框图5 0 图4 4h c t r i p l e h s i a o d u p 编码框图51 图4 5 对数据部分的h s i a o d u p 译码流程图5 2 图4 - 6 速度增益s p e e d - u p 与平均h o p s 的关系5 3 图4 7 功耗收益e n e r g y - s a v i n g s 与平均h o p s 的关系5 4 图4 8 面积开销a r e a o v e r h e a d 与平均h o p s 的关系5 5 表目录 表目录 表1 1 第k 根线( 中间线) 的归一化安全延时上界9 表1 2 边界线延时1 0 表2 1 构造最大团以得到最大容量1 c 码码簿q 的归纳算法1 6 表2 2o l c ( 8 ，4 ) 码的码字与数据字的对应关系1 9 表2 3 禁用模式码码字产生算法2 0 表2 43 、4 和5 b i t 禁用模式码码簿21 表2 5 ( 5 , 4 ) f p c 码的码字与数据字映射关系2 3 表2 6 对2 、3 、4 和5 - b i t 总线的f t c 码簿2 5 表2 7f t c 码码字产生归纳算法2 5 表2 8 ( 9 ，4 ，3 ) b s c 码的编码过程2 7 表2 - 9 噪声污染下的( 9 ，4 ，3 ) b s c 译码过程2 7 表2 1 0f o c ( 5 ，4 ) 码数据字与码字的映射关系2 8 表3 1 对k - b i t 输入数据字进行( ，z ，k ，p ，d ) 码编码时所需的最小总线加3 0 表3 2 基于统一编码框架得到的一些联合码3 5 表3 33 2 - b i t 总线的各种编码方案性能比较4 3 表4 1 ( 8 , 2 4 ) - b i t 信息包的各种总线编码方案脾1 2 1 2 厶匕f i v , 比较5 2 i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：塑查旦塑日期：劲如年歹月朋 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：越盆盈 导师签名： 跬姻 日期：o f o 年媚万日 第一章绪论 第一章绪论 在过去几十年，集成工艺在摩尔定律( 即集成电路上的晶体管数目每1 8 个月 翻一番) 的指引下取得了极大的发展。随着深亚微米( d s m ，d e e ps u b m i c r o n ) 时 代的来临，大规模集成电路( v l s i ，v e r yl a r g es c a l ei n t e g r a t e ) 设计者可以设计出更 快和更复杂的电路，这使得基于片上系统( s o c ，s y s t e m o n c h i p ) 、片上网络( n o c ， n e t w o r k o n - c h i p ) 和芯片级多处理器( c m p , c h i p 1 e v e lm u l t i p r o c e s s o r ) 的产品成为 可行【1 1 。本文主要研究基于片上互联的片上通信，片上互联是由同一金属层上的一 组并行、对齐和相似线所组成的片上总线构成。本章首先介绍了深亚微米工艺下 片上互联所遇到的问题，随后讨论了目前已有的解决措施和深亚微米总线模型， 最后是本文的组织结构。 1 1 深亚微米工艺下的片上互联 在d s m 工艺下，线间距会非常小，同时为了维持合理线性线电阻关系，d s m 总线会有高特征比( 即高宽比) 。因而，线间耦合会越来越严重，总线的分布式特 性也会更加显著。耦合和分布式特性使得全局片上总线遭遇了如下三个主要问题： 1 ) 由寄生电容和电容性耦合造成的高功耗，即功耗问题【2 】【3 】；2 ) 由电容性串扰产生 的传输延时，即延时问题【3 】- 【习；3 ) 受d s m 噪声影响而发生的传输错误，即可靠性 问题【6 】【7 1 。随着集成电路特征尺寸的缩小、供电电压的降低、互连密度和时钟频率 的增大，这三个问题将变得愈发严重。 营 捌 莨 霉 集成工艺( n m ) 图1 1 门延时、线延时与集成工艺特征尺寸的关系 电子科技大学硕士学位论文 在微处理器和s o c 设计中，功耗已经成为性能提升的一个主要限制因素，其 中片上互联消耗了很大的功耗。通过研究表明，高达4 0 的功耗是由于线功耗引 起的【引。在5 0 n m 工艺下，全局互联占了至少2 0 的线功耗，因而迫切需要低功耗 技术来减少全局互联功耗 9 1 。随着器件尺寸的急剧缩小，门级延时也迅速减小。而 由于耦合串扰的影响，片上互联延时并没有相似的变化趋势。图1 1 是2 0 0 3 年国 际半导体技术路线图所提供的关于门级延时、线延时相对子集成工艺的关系，其 中门级延时( g a t ed e l a y ) 随着集成工艺的缩小在不断减小，而线延时( g l o b a lw i t h r e p e a t e r s ) 却在不断增加【1 0 1 。在许多大规模设计( s o c ，n o c 和c m p 设计) 中，由 于长宽全局线的使用，互联延时占了逻辑延时的大部分。例如，在9 0 n m 工艺下， 典型的门延时是3 0 p s ，而适中规模芯片上的互联延时是几n s 1 1 。由于电源栅极摆 动、电磁干扰、线问串扰和高能粒子的影响，片上传输极易发生错误，随着电压 幅度的减小，可靠性问题将更加严重。n o c 作为未来s o c 的发展方向，各个节点 间的低功耗、高速和可靠通信是关键，因而片上总线设计必须考虑上述三个问题 的影响【1 l 】。 1 2 目前的研究情况 由于其灵活性和综合处理能力，总线编码被认为是解决全局互联功耗、延时 和可靠性问题的有效手段。目前的总线编码类别包括：1 ) 减小自过渡和耦合过渡的 低功耗码( l p c ，l o wp o w e rc o d e s ) 1 1 2 乃j ，2 ) 减小串扰延时的串扰避免码( c a c ， c r o s s t a l ka v o i d a n c ec o d e s ) 1 4 h 1 6 】，3 ) 改善传输可靠性的差错控制码( e c c ，e r r o r c o n t r o lc o d e s ) 【6 】。从通用通信系统出发，可以将d s m 总线看作一个有功耗、延时 和噪声特性的通信信道，因而可以将通信理论中的许多设计方法用于低功耗、高 速和可靠片上总线设计中【1 2 1 。在图1 2 所示的通用编码系统中，信源编码负责数 据压缩，而信道编码通过增加冗余信息以对抗噪声干扰，并可以在保证同等可靠 性前提下降低信号幅度以减小功耗。在d s m 总线中，l p c 码和c a c 码相当于信 源编码，而e c c 码是信道编码。目前的总线编码都只是单独处理了功耗、延时和 可靠性中的某一方面，从图1 2 所示通用编码系统出发，可以得到一个统一编码框 架，从而可以基于该框架联合l p c 、c a c 和e c c ，以得到一些具有综合处理能力 的编码方案。下面将介绍一个深亚微米总线模型，并基于该总线模型讨论了总线 功耗、延时和可靠性的解析模型，从而为总线编码方案设计提供数学基础。 2 第一章绪论 1 3 总线模型 t x 图1 - 2 通用编码系统框图 假定1 1 根并行总线位于同一金属层，对于d s m 片上总线模型，可以用图1 3 所示的带线间耦合电容的分布式r c 网络来等价 1 5 1 1 6 1 。其中，厂、c 上、和c ，分别是 单位线长上的电阻、对地电容和线间耦合电容，是供电电压，和白是驱动器 的电阻和电容。基于图1 3 所示的总线模型，下面将讨论总线的功耗、延时和差错 模型。 1 3 1 功耗模型 图1 - 3d s m 的分布式r c 总线模型 假定数据在总线上的传输是在时间周期丁内完成，即新数据在t = 0 时从发端 发送，在t = 丁时刻在接收端进行采样，这样我们就可以认为在数据被接收时总线 上的电压已经稳定在最终状态了。为了计算时间间隔 o ，邪内的总线功耗，定义 和杉，分别为t = o 和f = t 时第i 根线上的初始和最终电压，线上电压由巧7 变为巧，称 3 电子科技大学硕士学位论文 为一个过渡。a v , = 形，- z , 是线f 上的过渡电压，杉，= k - a v j 是线j 相对线f 的 过渡电压，, 1 - s 弘( k ) 等是第根线对第f 根线的归一化电压改变。对于刀根 并行总线，一个总线周期的初始和最终电压矢量分别为v 7 = k ，嘭，嘭】t 和 v ，= k ，曙】t 。 在过渡周期 o ，丁】内，第f 根线上的功耗可以由如下公式给出 1 4 】： 互= k ，4 c ( 矿，一) ( 1 1 ) 其中，岛为位置f 上为1 ，其余元素为0 的n 维列矢量，c 是，z ，l 电容矩阵，其定 义如下： c 2 1 + 名一名 一名1 + 2 力 0 一见 oo o 一五 1 + 2 旯 o o o 0 1 + 力 ( 1 2 ) 其中，力2 邑，c ，和q 分别是总的线间耦合电容和对地电容。参数兄与集成工艺、 具体的几何分布和金属分层有关，其值会随着集成工艺的缩小而增大。互可以写 成如下形式 1 】： 置= ( 1 + 2 2 一名4 ，4 一兄4 n ) c ：形三巧，( 1 - 3 ) = e + e ： 其中，群= q 屹k ，耳= ( 2 - 4 一4 n 。) 力q 形，。根据公式( 1 - 3 ) ，线上功耗 由对地电容功耗彰和对线间耦合电容功耗彰两部分组成，其是有效电容c ，的函 数。线i 上的有效电容c ；定义如下： c ，= ( 1 + 2 2 - a 4 。，一一旯4 f + 。) c ： = 【1 + 旯( ( 1 一蘸，一。) + ( 1 4 ，) ) 】 ( 1 4 ) = c 【j + c i + c m j 4 第一章绪论 可以看出，e 鲋由三部分组成：线f 对地总电容q ，对左边邻线的总耦合电容 c f w ，= a ( 1 - 4 ，f - 。) q 以及对右边邻线的总耦合电容吒。，= 咒( 1 4 川) q 。由于d s m 总线的线间耦合电容q 远超过对地电容q ，因而可以忽略c 。值，使得e 矿，的所有 可能取值为o g ，1 c ，2 c ，3 c ，和4 c ， c f w ，吒， o ，l g ，2 c ，) 。 当 喀f _ ，= 1 和4 ，f + 。= 1 时，即中间线及其邻线同方向过渡，e 矿，有最小值 r a i n ，) = q 。而当屯一。= 一1 和4 一。= - 1 时，即中间线和其邻线反方向过渡，e 矿， 有最大值m a x e 矿，) = ( 1 + 4 3 , ) c l 。每过渡周期的总线总功耗为： e = ：。e ( 1 5 ) = ( v ，) 7 c ( 矿，一v ) 每一总线周期的平均功耗与所传数据的统计特性有关，下面将针对两种情况 进行讨论。当所传数据是随机且联合广义平稳时，假定( 尼) ，i = 1 ，2 ，z 是第i 根总 线在第尼个周期所传比特，定义随机序列矢量三( 尼) = ( 尼) ，乞( 后) ，厶( j | ) r 。对于第尼 个过渡，第舛艮总线过渡前后的电压分别为形= ( 尼) 和k ，= v d a l ；( k + 1 ) 。刍gi , n 第根线上比特序列的互相关为： r ( ，) = g ( 七) l ( 七+ 厂) ( 1 6 ) 其中，占( ) 是期望运算。总线上所传比特序列的自相关矩阵为： r ( 厂) = r ，( ，) ? 产，= 占 三( 尼) r ( 后+ ，) ( 1 - 7 ) 每一总线周期的平均功耗为 1 4 】： 缸e ( 尼) _ v 品t r c a ) ( 1 8 ) 其中，护( ) 是矩阵的迹，a 是玎刀过渡活动矩阵，其定义如下： 么：尺( o ) 一型掣塑 z ( 1 9 ) 彳中的元素为： a i ，2 r ，( o ) 一限。，( 1 ) + b ，( 1 ) 】2 = 占 ( 尼) t ( 尼) 卜兰! 生! 竺! 互! 垄二二堕三! 幽1 - 1 。 电子科技大学硕士学位论文 当对总线采用总线编码时，所传数据的统计特性不呈现随机且联合广义平稳。 若在第七个时钟周期的输入数据矢量为d ( 七) = 吐( 七) ，d 2 ( k ) ，以( 七) r ，则经过编码 模块b 后得到属于有限集合 ，w 2 ，) 的码字w ，其中w o ，1 r “，忙1 ，m ， m 是增加的冗余比特数目，m 是所用编码方案的码簿容量。对于第k 个过渡，过 渡前后所传输的数据矢量l ( k ) 和l ( k + 1 ) 是上述有限集合中的元素。当l ( k 一1 ) = w 时，l ( k ) 的所有可能取值组成集合瓦。由于每一周期都要传输n b i t 数据，因而l 应该有2 ”个元素。定义过渡矩阵t = i t , ， 笛：。，其元素为： 幻= 心w j e x p w ， 假定输入数据d ( k ) 是独立同均匀分布的，则总线上所传数据l ( k ) 具有一阶齐 次马尔科夫过程特性。由w 过渡到的条件概率为： 骅刚h 传芝兰m 过渡概率矩阵p 定义如下： p = 最】艺爿= p ( 三( 后) = ml ( k 一1 ) = w ) 易：。 ( 1 1 3 ) 由过渡矩阵丁的定义，有p = 。采用总线编码后的每一总线周期平均功耗 为【1 4 】： e 一- - 响t ( p e ) ! ( 1 1 4 ) 其中，是h a d a m a r d 积运算，! 是元素值都为1 的m 维列向量，6 0 是过渡概率矩 阵尸相应于特征值1 的左特征向量，即巧尸= 醪。功耗矩阵e 具有如下形式： 研e ( w ，m ) 】 ( 1 - 1 5 ) 6 第一章绪论 e ( w ，- ) 是由公式( 1 - 5 ) 得到的过渡w 一也功耗。 d ( 蠡) ； ： ； - - 1 一c 当总线编码用于宽总线时，一般采用图1 。4 所示的分裂编码方案来减小编码复 杂度，即将宽总分成1 3 组宽度更小的总线，然后对各组小总线分别进行编科1 7 - 【2 。 对于分裂编码，每一总线周期的平均功耗包括各组小总线的自身功耗以及它们之 间的耦合功耗。若所用编码方案的码簿w = ，心，w m ，则定义吸。和暖口分别 为码簿w 中第一比特和最后一比特为口的所有码字组成的集合，同时定义如下形 式的吆，磁口，以。和1 4 口： 缘= 三i 主毳：筹 ，碰口= 三i 主荔：筹) c - 6 ， = 西 a 。、1 磋，一，吆) ，皿口= d i a g ( h ：口，吃，磁) ( 1 1 7 ) 每一总线周期各组总线间的平均耦合功耗为 2 2 】。 2 4 】： b = 元酊 日l 。p 巩+ 皿。p 皿o 】三 ( 1 - 1 8 ) 其中，和p 的定义等同公式( 1 - 1 4 ) 。采用分裂编码时，每一总线周期的总平均 功耗为： 耳= ，如+ ( 刀一1 ) 7 ( 1 1 9 ) 电子科技大学硕士学位论文 f 宁 cfr c l + 2 c r z ( 1 的 c ，c ， 一酗 1 3 2 延时模型 由于d s m 总线间的高度耦合会产生m i l l e r 效应2 5 1 ，各线上的相对过渡极大地 影响了总线传输延时。图1 5 所示是数据在d s m 总线上传输时所产生的m i l l e r 效 应，其中k 是相邻线上的相对电压增益。考虑如下过渡 ，0 ，0 ，0 】一 ，1 ，1 ，1 】和 【，1 ，0 ，1 一 ，0 ，1 ，0 ，由于线上数据过渡方向相同，第一种过渡情况的k = 1 ， 其中间线只需对对地电容c ，进行充电。而第二种过渡情况的线上数据呈反方向过 渡，其k = 一1 且中间线需要对总电容c + 4 c ，进行充电。因而，第二种情况的中间 线传输延时( 即最差延时) 是第一种情况的4 倍左右。根据图1 3 所示的d s m 总 线模型，由于线间高度耦合，每一总线传输的线上延时与过渡前后的传输矢量 u 。= 【砰，u o r 和u = “y ，“， r 有关。通过采用e l m o r e 延时模型，第k 根总线 的传输延时可以近似为 2 6 h 2 8 】： 学= ( 1 + 2 装笼络k ：晨圳 吁 i( 1 + 2 ) a ：一勉。a k = ，z 其中，r r = r e + 鲁，q = l c l ，l 是总线长度，a 。= “一“；是第k 根总线上的比 特变化。由于“，u ； o ，1 ) ，从而使得a 。 - 1 ，0 ，1 ) 。根据公式( 1 - 4 ) 给出的有效 电容定义，可以将公式( 1 - 2 0 ) 中的中间线延时写成【l j ： 瓦( “。，“) = c , s 气 ( 1 2 1 ) = ( 1 + 2 2 - 2 d k t 一1 一允皖。t + 1 ) 其中，r o 是无串扰情况下的线上延时。可以看出，中间线的线延时与，。呈线性 关系，其取值是由中间线及其邻线的过渡情况决定的，因而线延时和线上自过渡 及线间相对过渡密切相关。第k 根总线传输延时的一个安全上界为： 第一章绪论 其中，a o = 槲= 0 。 警郇m i 陪”酬) ( 1 - 2 2 ) 表1 1 第k 根线( 中间线) 的归一化安全延时上界 l 。i + 五1 2 。- a 。一。一a 。+ 。i 线和过渡 k lkk 4 - 1 第k 根总线归一化传输延时的安全上界 i l色“1 o 个 五 j ， 且 t 五 土 五 j ，to 个 j ， 0 个1 、 2 2 j ，、l 2 2 个 t t1 、l j ，上1 1 、t l + 五 上j ， 1 + 五 tr 1 + a j ，、ll + 五 个 l + 2 五 j l + 2 五 个tj ， 1 + 2 五 j ， tt 1 十2 五 t 上 j ， 1 + 2 五 上j ，个 1 + 2 五 tj ， 1 + 3 五 土t l + 3 五 一ri l + 3 五 上 t l + 3 五 个上t 1 + 4 2 工一rll + 4 五 对于过渡u 。 - - - u ，总线传输延时乃 。，“) 是各根总线延时的最大值，其值 9 电子科技大学硕士学位论文 为： 乃( “。，“) - m a x 瓦( “。，”) ( 1 - 2 3 ) r = i z n 对总线上的所有过渡，可以根据它们的延时情况进行分类，从而将其分成集 合，d o ，d 1 ，砬，d 3 ，d 4 的并集，它们的定义为： 表1 - 1 给出了第k 根总线( 中间线) 关于色。，。，的延时上界， k = 2 ，3 ，n 一1 。其中，t 表示由0 过渡到1 ，j ，表示由1 过渡到0 ，一表示不发生 变化。中间线的所有可能归一化延时取值为0 ，1 ，1 + 2 ，1 + 2 2 ，1 + 3 2 和1 + 4 2 , ，每一个 取值都相应于一组过渡 “b ，“；，蚝o + 。】j “，“，n + ，】。对于边界线1 和n ，它们只 有一根邻线，表1 2 给出了边界线的延时取值情况。 表1 2 边界线延时 互! 兰：! 竺 q 线和过渡 1 或n2 或n 一1 边界线1 或一的延时 a 12 o 个 o j ， 0 1 、t l j ， j ， 1 1 1 + 五 j ， l + a tj l + 2 五 j ，t l + 2 名 可以看出总线最差延时为( 1 + p ) ，p = 4 ，3 ，2 ，1 ，0 r o = 吩q ，其值取决于线上自 过渡和相邻线上的耦合过渡情况。根据公式( 1 - 2 4 ) 将总线上的所有过渡情况按传 输延时进行分类，通过消除那些延时很大的过渡情况，串扰避免编码( c a c ) 可 l o 田 筮昵 踟 厉 第一章绪论 以减少自过渡和耦合过渡，最终可以减小p 值以得到更小的最差延时。 1 3 3 差错模型 由于电源栅极摆动、电磁干扰、总线串扰以及粒子碰撞的影响，n o c 总线极 易发生暂态错误。由于目前知识所限，很难得到一个精确的d s m 噪声模型，所以 我们假定d s m 噪声为一个幅度为，方差为砖的高斯噪声2 9 1 ，研究表明误比特 率同时取决于露和供电电压，其值为： t 厂 e = q ( 导) ( 1 - 2 5 ) 其中，q ( ) 定义如下： 胁去 砂 ( 1 2 6 ) 假定各比特错误相互独立且很小，则k - b i t 未编码总线的误码率近似为= k e 。 1 4 本文的组织结构 从基于n o c 的总线编码出发，本文研究了如何综合处理d s m 工艺下的总线 功耗、延时和可靠性问题。本文余下部分组织如下：第二章基于d s m 总线功耗、 延时和可靠性解析模型分析了l p c 、c a c 和e c c 的编码原理以及相应的一些实际 编码方案。第三章从统一编码框架出发，考虑n o c 信息包结构以及不等能力保护 码( u e p , u n e q u a le r r o rp r o t e c t i o n ) 的特点，提出了一种联合u e p 和c a c 的综合码 s e c d a e d s d a e c + d a p 码，它可以为信息头部的路由信息提供更强保护能 力，同时又可以对抗串扰延时的影响。在基于包交换的n o c 中，目前的总线编码 主要采用基于整体编码的设计方式，片上通信的整体功耗和延时受路由路径的影 响非常大。针对n o c 信息包结构，第四章介绍了一种针对包头局部编解码的分组 混合编码设计方式，同时采用基于s e c d e d 的h s i a o 码和基于复制码的c a c 码 来改善片上通信性能，从而得到联合码-