（电路与系统专业论文）基于编码的片上网络数据传输可靠性研究与设计.pdf

1ij， b y w a n y u p e n g a d v i s e d b y p r o f e s s o rw un i n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n g j a n u a r y , 2 01 0 一 ， 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 作者签名：盈查煌 日 期：丝 旦：至：兰 片上网 成为片上网 并配合控制 本文的 用v e r i l o g 的片上网络 本文首 出了进行片 方式分别实 统开销等方 提出了一种 能力。最后 永久性故障 路由机制， 本文设 错路由器、 关键词：片 基于编码的片上网络数据传输可靠性研究与设计 a b s t r a c t a st e c h n o l o g ys c a l e st o w a r dd e 印s u b m i c r o n , n e t w o r ko nc h i pi n t e r c o n n e c t sa r eb e c o m i n g m o r ea n dm o r es e n s i t i v et oa v a r i e t yo fn o i s es o u r c e s ，s ot h a tt h er e l i a b i l n yb e c o m e sam a j o rb r a n c h o fn o c r e s e a r c h c o d i n gb a s e de r r o rc o n t r o ls c h e m e sa r ec o n s i d e r e de f f e c t i v ef a u l tt o l e r a n tm e t h o d s a tp r e s e n t t h i sp a p e rf o c u s e so nt h er e s e a r c ho ff a u l tt o l e r a n ts c h e m e sf o rd a t at r a n s m i s s i o no nt h en o c d a t al i n k t h en o ct o u t e r sw h i c ha d o p tf a u l tt o l e r a n ts c h e m e sa r ei m p l e m e n t e dw i t hv e r i l o gh d l ， s i m u l a t e da n ds y n t h e s i z e db ys y n o p s y se d as o f t w a r e t h ep e r f o r m a n c ea n a l y s i so ft h ef a u l tt o l e r a n t s c h e m e sa r ea c c o m p l i s h e di na4x42 d - m e s hn o cc o m p o s e db yt h ef a u l tt o l e r a n tr o u t e r s f i r s t , t h i sp a p e rd i s c u s s e st h em a i nr e s e a r c hc o n t e n t so fn o cc o m m u n i c a t i o nr e l i a b i l i t ya n dt h e s t a t eo f t h ea r t o nt h i sb a s i s ，w ep r o p o s et h ek e yt e c h n o l o g i e so f n o cc o m m u n i c a t i o nr e l i a b i l i t y f o r t r a n s i e n te r r o r s ，w ea d o p tc o d i n gb a s e dh o pb yh o pa n de n dt oe n de r r o rd e t e c t i o na n dr e c o v e r y s c h e m et od e s i g nt w ok i n d so ff a u l tt o l e r a n tr o u t e r s w ea l s oe v a l u a t et h et w of a u l tt o l e r a n ts c h e m e s i nt e r m so ff a u l tt o l e r a n tp e r f o r m a n c e ，p o w e ra n da r e ao v e r h e a d s e c o n d l y , t h i sp a p e rp r e s e n t san e w c o d i n gs c h e m ei no r d e rt os o l v et h em a j o rs o u r c eo ft r a n s i e n te r r o r su n d e rd e e ps u b - m i c r o np r o c e s s t h en e wc o d i n gs c h e m ea c h i e v e sj o i n tc r o s s t a l ka v o i d a n c ea n de r r o rd e t e c t i o no nd a t al i n k t h i r d l y , w ei m p r o v ef a u l tt o l e r a n tr o u t e r sa n dr e a l i z ei t sc a p a b i l i t yo fp e r m a n e n te r r o rd e t e c t i o na n dl o c a t i o n , w h i c hs u p p o r td y n a m i cm u t i n gm e c h a n i s mb a s e do nn e t w o r km o n i t o rp r o p o s e db yo u rg r o u pt os o l v e t h ei s s u eo fp e r m a n e n te r r o r so nd a t al i n k s ac o m p r e h e n s i v ef a u l tt o l e r a n ts c h e m ei sd e s i g n e di nt h i sp a p e r , w h i c hd e a l sw i t hb o t ht r a n s i e n t a n dp e r m a n e n te r r o r so nn o cd a t al i n k s t h i ss c h e m ep r o v i d e sar e f e r e n c ef o rd e s i g no ff a u l tt o l e r a n t r o u t e r , c o d i n gf o rr e l i a b i l i t yo nn o c d a t al i n ka n df a u l tt o l e r a n tn o ca r c h i t e c t u r e k e yw o r d s ：n e t w o r ko nc h i p ，r e l i a b i l i t y , t r a n s i e n te r r o r , p e r m a n e n te r r o r , f a u l tt o l e r a n t , c o d i n g 位论文 第一章绪论1 1 1 片上网络通信的可靠性问题1 1 2 片上网络通信可靠性的研究内容。2 1 2 1 故障分类与建模。2 1 2 2 容错对象与方式2 1 2 3 编码方案。3 1 3 国内外研究现状3 1 3 1 国外相关研究。3 1 3 2 国内相关研究。4 1 4 课题背景和研究内容5 1 4 1 课题背景5 1 4 2 研究内容。5 1 5 论文的组织结构6 第二章可靠性研究的关键技术与基础7 2 1 网络拓扑结构7 2 2 交换机制8 2 3 容错机制。9 2 3 1 前向纠错9 2 3 2 检错重传一9 2 4 容错路由算法1 l 2 5 故障模型1 2 2 6 错误控制编码1 2 2 6 1 线性编码的定义1 2 2 6 2 常用线性编码1 3 第三章针对瞬时故障的容错机制研究与设计1 4 3 1 数据包格式定义1 4 3 2 点到点检错重传容错路由器设计与实现1 5 3 2 1 点到点检错重传路由器的模块划分1 5 3 2 2 端口控制器设计1 7 3 2 - 3 数据缓冲区1 9 3 2 4 编解码器设计2 0 3 2 5 重传缓冲区2l 3 2 6 状态控制器设计2 l 3 2 7 路由计算模块设计2 3 3 2 8 仲裁器设计2 4 3 2 9 交换开关2 5 3 3 端到端检错重传容错路由器设计与实现2 6 基于编码的片上网络数据传输可靠性研究与设计 3 3 1 端到端检错重传路由器的模块划分 3 3 2 本地输入、输出端口总体设计 3 3 3 编码与重传控制器设计。 3 3 4 解码控制器设计 3 4 检错重传机制容错能力验证与性能分析3 2 3 4 1 容错能力验证3 2 3 4 2 平均延时分析3 4 3 4 3 功耗开销分析3 6 3 4 5 面积开销分析3 7 第四章片上网络可靠性编码的研究与设计一3 8 4 1 串扰问题与解决方案3 8 4 1 1 串扰模型3 8 4 1 2 物理层的解决方法3 9 4 1 3 基于编码的解决方法3 9 4 2c a c 码与可靠性编码的结合4 0 4 3 联合编码设计4 1 4 3 1 编码方案4 l 4 3 2 编码器设计4 4 4 3 - 3 解码器设计4 5 4 3 4 编码方案比较分析4 6 第五章针对永久性故障容错路由器设计与分析4 8 5 1 基于监控器的动态路由机制4 8 5 2 支持动态路由机制的容错路由器设计5 0 5 2 1 支持动态路由机制的路由器模块划分5 0 5 2 2 端口控制器5 1 5 2 3 状态控制器与链路状态表5 2 5 2 4 路由计算模块与路由表5 3 5 3 路由器性能开销分析5 4 5 3 1 容错能力验证与性能分析5 5 5 3 2 面积功耗开销分析5 7 总结与展望。5 8 参考文献5 9 致谢6 4 在学期间的研究成果及发表的论文6 5 南京航空航天大学硕士学位论文 图表清单 图2 1 片上网络拓扑结构图7 图2 2 端到端检错重传结构1 0 图2 3 点到点检错重传结构l l 图3 1 数据包格式1 4 图3 22 d m e s h 点到点检错重传路由器结构1 5 图3 3 点到点检错重传路由器模块划分图1 6 图3 4 端口控制器电路框图。l7 图3 5 虚切通交换方式的数据存储示意图18 图3 6 数据接收流程图。1 9 图3 7 存储器原理图2 0 图3 8 偶校验编、解码电路结构。2 0 图3 9t m r 结构2 l 图3 1o 数据发送流程图2 2 图3 1 1 路由计算模块电路框图2 3 图3 1 24 x 42 d m e s h 拓扑结构节点地址编码。2 4 图3 1 3 交换开关示电路框图2 5 图3 1 42 d m e s h 端到端检错重传路由器结构2 6 图3 15 端到端检错重传路由器模块划分图2 7 图3 1 6 编码与重传控制器电路示意图2 8 图3 1 7 确认包和重传请求包格式2 9 图3 1 8 编码与重传控制器f s m 状态转移图3 0 图3 19 解码控制器31 图3 2 0 解码控制器f s m 状态转移图。3 l 图3 2 l 三种网络失效情况对比3 2 图3 2 2 两种端到端检错重传机制路由器网络的失效情况对比3 3 图3 2 3 两种检错重传机制的延时比较3 4 图3 2 4 相同注入率下两种容错机制的延时对比3 5 图4 1 线间电容模型。3 8 图4 2 最坏情况的串扰3 9 图4 3 双轨码和d a p 码4 0 图4 4 联合编码流程。4l 图4 5 联合编码器电路示意图4 5 图4 6 解码算法流程图。4 5 图4 7 联合解码电路示意图4 6 图5 1 基于监控器的动态路由机制结构4 9 图5 2 网络监控器模块划分4 9 图5 3 改进后的容错路由器模块划分5 0 v 基于编码的片上网络数据传输可靠性研究与设计 图5 4 改进后的端口控制器 图5 5 链路故障监控状态转移图 图5 6 改进后的路由计算模块与路由表。 图5 7m p e g - 4 解码器通信流到4 x 42 d m e s hn o c 的映射。 图5 8 链路发生永久性故障后的吞吐量和包平均延时变化5 6 图5 9 随故障链路数目变化的网络吞吐量比较。5 6 表3 1 偏移量编码2 3 表3 2 发送方向d i r 编码2 4 表3 3 点到点检错重传路由器的功耗开销3 6 表3 4 端到端检错重传路由器的功耗开销。3 6 表3 5 点到点检错重传路由器的面积开销3 7 表3 6 端到端检错重传路由器的功耗开销。3 7 表4 1 联合编码校验位真值表。“ 表4 2 各种联合编码码字位宽比较4 6 表5 1 跳数与路由表位数对应关系5 4 表5 2 容错路由器的功耗开销。5 7 表5 3 支持容错路由器的面积开销5 7 论文 q o s服务质量( q u a l i t yo f s e r v i c e ) c a c 防串扰编码( c r o s s t a l ka v o i d a n c ec o d e s ) b e r 误比特率( b i te r r o rr a t e ) t m r 三模冗余( t r i p l em o d u l er e d u n d a n c y ) o c p 开放核协议( o p e nc o r ep r o t o c 0 1 ) a r q 自动请求重传( a u t o m a t i cr e p e a tr e q u e s t ) 学硕士学位论文 绪论 1 1 片上网络通信的可靠性问题 随着集成电路技术的快速发展，传统的总线或点对点互连结构在可扩展性、通信效率、功 耗等方面的问题越来越严重，通信成为其突出的性能瓶颈【l 】。于是，业界将目光聚焦于运用网 络技术来解决芯片中器件互连的问题上，从而使片上网络( n e t w o r ko nc h i p ，n o c ) 成为了学术 界的研究热点。它可以方便的集成大量成熟的第三方知识产权( i n t e l l e c t u a lp r o p e r t y , i p ) 核，实 现从物理层到应用层的完整网络通讯协议，构成规模更大、功能更加复杂的片上系纠2 翔。 目前，国内外对n o c 的研究处于蓬勃发展时期，先后有卮t h e r e a k 4 1 、n o s t r u m t 5 1 、 x p i p e s n 、m a n g o t 7 1 等多种体系结构的n o c 被提出，开展n o c 相关技术的研究，对于电子系 统的微型化、高可靠性、低功耗以及简化设计流程具有十分重要的意义。 目前对于片上网络的研究主要包括：拓扑结构、路由算法、路由器结构、服务质量e q u a l i t y o fs e r v i c e ，q o s ) 等方面。其中，q o s 参数可分为传输带宽、可靠性、吞吐量等。随着制造工 艺的进步，片上网络越来越紧凑，保证片上网络的可靠性是设计人员不可回避的问题。 随着芯片集成度的增长，以及错误检测和恢复( “自我修复”) 重要性的增加，片上通信的 可靠性成为一个重要问题。应用于现在嵌入式系统的a s i c 是安全关键系统与消费相关产品的 一个组成部分，这使得容错成为芯片设计的一个关键点。芯片尺寸的不断缩小导致了串扰的增 强、较高的场效应和更多的泄漏电流，这些都会使芯片产生更多的瞬时故障和永久性故障嘲。 瞬时故障是指在数据传输中，由于串扰对于长传输线的影响或者宇宙射线、电磁干扰、工艺的 不稳定等原因造成一个或多个比特错误。永久性故障通常是由于生产过程中或芯片运行过程中 对某些模块产生的物理上的损坏。在电路设计过程中是很难完全消除和避免这些故障的，或者 代价是非常昂贵的，因此必须使用一定的容错机制。由于片上网络对于资源、功耗、延迟以及 面积等的约束，传统的容错机制不再适合n o c t 引，而必须研究专门的针对n o c 的容错机制和容 错算法。 n o c 采用基于数据包交换的通信方式，这给片上可靠性设计带来了新的挑战。一个数据包 由包头和包负载组成。数据包头主要包含一个唯一的数据包编号、源节点地址与目的节点地址、 路由信息等。数据包的负载包含实际数据。瞬时故障可以破坏数据包头或负载。在前者，目的 节点地址中的一个比特翻转，会使得数据包路由至错误的目的地址。在后者，瞬时错误会影响 包负载的正确性，从而使数据包失效。永久性故障可以使链路或路由器失效，造成数据包堵塞， 导致整个系统的瘫痪。 基于编码的片上网络数据传输可靠性研究与设计 1 2 片上网络通信可靠性的研究内容 在分析和研究了大量国内外文献的基础上，总 的研究主要集中在以下几个方面。 结出目前学术界对片上网络通信可 1 2 1 故障分类与建模 失效方式在逻辑级和行为级按不正确的信号值来描述，表达形式为故障模型。因此，故障 是这样一种模型：它通过电路或系统中信号所衍生的变化，即电路的逻辑行为来描述失效效应。 在电路检测中采用故障模型而不直接采用失效方式，主要优点有以下几个方面。 ( 1 ) 故障分析问题成为逻辑分析问题而不是物理分析问题，同时由于不同的失效方式可能 建模为同一个故障模型，大大降低了故障分析的复杂性，易于进行数学分析和处理。 ( 2 ) 一些故障模型与工艺无关，这样同一个故障模型可以用于多种工艺的测试生成，测试 和诊断方法即使工艺改变也保持有效。 ( 3 ) 对于逻辑行为难于分析的失效方式，基于故障的测试开发可能有效。 因此，建立故障模型是片上系统电路测试与可靠性研究的基础。 通常好几种缺陷可映射成一种故障模型，这是一种多对一的映射，一个缺陷也可用于多个 故障模型来描述【l o 】。在n o c 研究领域中，故障通常分为瞬时故障和永久性故障两类，这两种故 障根据其在n o c 结构中发生的位置、时间、影响范围又可以分成多种类型，故障模型的建立对 分析n o c 的可靠性以及设计相应的容错机制至关重要。 1 2 2 容错对象与方式 对于n o c 的可靠性研究，根据其研究的网络结构对象的不同，可以分为两种：路由器的可 靠性和通信链路的可靠性。路由器的可靠性研究针对发生在n o c 路由器内部的故障，链路的可 靠性研究针对在路由器之间的通信链路上的故障。 路由器内部的故障可能发生在路由器的任何组件中。如果故障出现在实现路由算法的单元， 则可能导致数据向错误的方向路由；数据存储单元中发生的故障，可能导致数据失效或者之前 存储的数据被错误的覆盖；如果故障出现在仲裁单元，可以导致多个输入数据同时向同一输出 端口输出等情况；在交换开关单元发生故障，输出数据可能会出现误码；内部信号线上的故障 则可能导致数据无法继续传输或者传输时序混乱。 通信链路的故障发生在路由器与路由器之间的数据传输过程中，产生的主要原因是深亚微 米( d e e p s u bm i c r o n ，d s m ) 工艺下互连线对片上干扰源敏感程度的提高，n o c 路由器间的互 连线更容易受到串扰、电磁干扰和电源噪声的影响。链路故障，尤其是链路上的瞬时故障，已 经被认为是当前n o c 结构中的主要故障，并且在n o c 可靠性研究领域得到了极大的关注【l 。 2 南京航空航天大学硕士学位论文 对于路由器内部故障的容错，根据路由器内部的不同单元的特点，主要采用基于编码的检 错方式以及硬件冗余对现存数据进行备份的方式，这些机制可以解决瞬时故障以及永久性故障。 由于通信链路故障为n o c 的主要故障，因此通信链路的容错机制是学术界的研究热点。针 对n o c 通信链路中瞬时故障的容错机制，主要分为前向纠错、端到端的检错重传和点到点的检 错重传这三类。 对n o c 链路中的永久性故障，由于其不可能被修复或者替代，因此需要找到一条可以替代 的路径重新路由数据包，保证n o c 的通信不受影响。因此有学者提出采用电路冗余或者重构的 方法对永久性故障容错，但系统开销较大，更多的人倾向于采用一定的容错路由算法，避开故 障链路，从而达到容错的目的。也有人提出采用基于随机通信的容错算法，广播发送数据包， 达到同时解决瞬时故障与永久性故障的目的。 1 2 3 编码方案 目前，检错纠错编码被认为是为n o c 通信提供检错能力的有效方法。检错纠错编码即通过 时间或空间上的冗余码字达到检错纠错的目的。常用的检错n 错编码有奇偶校验码、汉明码 ( h a m m i n g ) 和循环冗余校验码( c y c l i cr e d u n d a n c yc h e c k , c r c ) 等。应用于n o c 之后，结合 不同的容错机制，编码方案的变化也多种多样。同时，也有大量的研究着手于检错：纠错编码与 低功耗编码的融合，在保证n o c 通信可靠性的同时，达到降低功耗的目的。随着深亚微米工艺 的到来，串扰对n o c 连接线的影响也越来越明显，成为影响功耗和可靠性问题的重要原因，防 串扰编码( c r o s s t a l ka v o i d a n c ec o d e s ，c a c ) 与检错纠错编码的结合也成为了保证n o c 通信可 靠性的一个重要研究方向。 1 3 国内外研究现状 片上网络的研究始于2 0 0 0 年，研究的初衷是探索片上系统通信部分的系统级设计方法【1 舶。 近些年，有越来越多的学者开始关注片上网络数据传输的可靠性问题，成为了n o c 研究的热点 之一。 1 3 1 国外相关研究 国外研究机构对片上网络通信的可靠性问题关注的较早，使得n o c 的容错机制研究成为 n o c 研究中的一个重要分支。其中，在n o c 容错机制研究方面影响较大的研究机构有瑞典皇家 理工学院( k n d 、斯坦福大学和华盛顿州立大学等。 k t h 的h e i k oz i m m e r 等人于2 0 0 3 年指出，邻近的路由器之间大量并行线的错误是瞬态的， 并且不固定发生在一根线上，因此传统的故障模型不能精确的描述错误的产生，提出了一个故 障模型的建模方法【1 3 】。并且指出采用编码技术来解决瞬态错误是目前最有效的方法。作者指出， 3 基于编码的片上网络数据传输可靠性研究与设计 采用编码方式来进行检错纠错，解码速度一定要快，因为解码一定要在路由器确定路由方向之 前完成。z i m m e r 等人对数据包分成几个部分分别编码，虽然增加了冗余度，但检错纠错能力更 强。同时指出，为了保证服务质量，数据包的包头必须严格保护。卡内基梅隆大学的t u d o r d u m i t r a s 等人在2 0 0 3 年建立了一个深亚微米技术下的故障模型，并提出了一个随机通信算法， 该方法充分利用了n o c 具有较大的传输带宽的特点，并且易于实现【1 4 l 。 2 0 0 4 年，宾夕法尼亚州立大学的m p i r r e t t i 等人提出了一种随机走动算法叫随机走动算 法，并分别与随机泛滥算法和带有方向性的泛滥算法进行比较，指出n 随机走动算法在多个方 面具有优势【1 5 】。而k t h 的a x e lj a n t s c h 等人在2 0 0 4 年指出，冗余总线编码一直是解决数据传输故 障的最有效的方法【1 6 1 。并且，随机通信会使网络中存在大量的冗余包，因此，更多的学者倾向 于使用检错纠错码的重传机制来解决瞬态错误。但是，基于编码的检错纠错重传方式会产生 较多功耗以及面积上的开销，设计时要考虑功耗与存储资源的限制。m u h a m m a da l i 等人提出了 一个应用于2 d - m e s h 的网络层检错重传方案，该方案仅仅使用一个应答包来响应预先定义的数 据包集合，而不是像传统的方式每收到一个数据包就发送一个应答包。而且，中间路由器 是没有缓冲区的。作者指出，该方法与其他方法相比，具有大的吞吐量以及较低的丢包率和较 小的包开销1 1 。 2 0 0 6 年，宾夕法尼亚大学的d o n g k o o kp a r k 等人研究指出，前向纠错与端到端检错重传的共 同缺点就是：如果包头发生错误，即使错误在目标节点能够被纠正，但这个目标节点可能已经 不是真正的目标节点，所以一定需要重传，产生了附加的传送【1 3 】。因此，对于包头的保护至关 重要，可以对包头采用点到点的检错重传，而对包负载采用端到端的检错重传【1 9 】。 由于在深亚微米工艺下，产生瞬态错误的主要原因是串扰，因此，有研究人员关注于如何 降低串扰对数据传输可靠性的影响并同时降低传输线上的功耗，提出了适用于n o c 的防串扰机 制，如文献 2 0 ，2 1 ，2 2 。还有些学者提出了将防串扰编码与检错纠错码结合起来，能够有效的控 制瞬态错误，如文献 2 3 ，2 4 ，2 5 1 。 同时，很多文章指出，功耗与可靠性的关系是密切的，这主要体现在，当芯片由较低的电 压供电时，瞬态错误发生的概率就较大。因此，较好的容错能力可以使芯片工作在低电压状态， 使功耗进一步降低。部分学者同时关注低功耗与错误控制编码，将低功耗编码与容错编码结合 起来，如文献 2 6 ，2 7 。 1 3 2 国内相关研究 国内对n o c 通信可靠性问题的研究相对较少，目前对于n o c 通信可靠性研究取得一定成果 的研究机构有中科院计算所和哈尔滨工业大学等。 中科院计算所的的张磊、李华伟等人提出了一种带有端到端反馈的随机路由算法f 2 引。随机 4 南京航空航天大学硕士学位论文 路由可以有效地处理传输过程中的随机错误，并具有较高的转发速度。端到端的反馈机制保证 了传输的正确性，同时降低了传输功耗。随机路由算法结合了随机走动算法的低延迟和重传机 制的高可靠性，数据包在发送前随机挑选路由向量，可以有效地处理随机错误。实验结果表明， 该算法具有较短的延时、较低的功耗，并能提供高可靠的片上通信。 哈尔滨工业大学的周文彪等人针对片上网络通信结构的可靠性问题，提出一种低功耗的自 适应数据保护方案，通过对片上网络各个节点之间通信链路的实际产生错误数目的检测，自适 应地选择进行数据保护的跳距大小，使片上网络在保证数据可靠性的同时，系统的功耗得到最 优化【2 9 】。 中科院微电子所的岳培培等人提出一种适用于片上网络通信的容错机制，能够全面的处理 片上网络通信中出现的故障。该机制由针对瞬时故障的检错重传机制和永久性故障检测、诊断、 恢复机制组成。作者对容错中使用的路由器以及网络几口进行了物理实现。实验结果表明，该 容错机制能够比较全面的对故障进行处理，并且路由器的面积开销较小【3 0 1 。 1 4 课题背景和研究内容 1 4 1 课题背景 随着芯片工艺尺寸逐渐缩小和时钟频率越来越高，各种干扰源对数据传输的影响也越来越 大，即使通过e d i a 工具时序分析的线路，也常常会因为串扰或其他干扰源影响信号完整性，导 致网络失效。片上网络由于自身的复杂性和应用背景，它的数据传输可靠性将难以保证。通过 相关研究的对比，国外研究机构已经在容错机制的设计上取得了较多成果，国内的研究机构则 刚刚开始对片上网络容错方面的研究。 本课题的主要工作是进行n o c 通信可靠性的研究，在s y n o p s y s 公司的e d a 环境下使用 v e r i l o gh d l 语言设计以编、解码为检错纠错基础的容错片上网络结构，实现各种容错机制，并 对各种机制进行性能、功耗和面积开销等方面的分析，进而提出一种更有效的容错方案，提高 片上网络通信的可靠性。 1 4 2 研究内容 本课题的研究内容主要分为如下几个方面。 ( 1 ) 针对瞬时故障的片上网络容错路由器的设计与分析 参考宏观网络中基于编码的错误恢复机制，研究各种容错机制的原理，选取其中典型的机 制进行片上网络容错路由器的设计，构建容错n o c ； ( 2 ) 对比分析各种容错机制的性能、功耗与面积开销 利用s y n o p s y s 公司的e d a t 具，对所实现的各种容错n o c 进行仿真与综合，模拟故障的产 5 基于编码的片上网络数据传输可靠性研究与设计 生，验证各种机制的容错功能，从传输延时、面积开销与功耗开销等方面比较各种容错机制的 优劣； ( 3 ) 研究适用于深亚微米工艺下的检错纠错编码方案 根据深亚微米工艺下的主要瞬时故障源串扰，分析各种防串扰编码技术的复杂性，设 计一种优化的防串扰检错虐l 错编码。所设计的联合编码方案，在降低串扰影响的同时又可以应 用于基于编码的检查重传机制，有效地解决了片上网络数据传输中的瞬时故障问题，从而为n o c 通信提供更高的可靠性； ( 4 ) 实现能够解决永久性故障的容错n o c 路由器 通过设计与实现基于编码的检错重传机制，并提出更加合适的编码方案，解决了n o c 通信 链路中的瞬时故障。在此基础上，通过改进容错路由器结构，实现支持课题组所提出的基于全 局链路状态解决永久性故障的n o c 路由器，更加全面的保障n o c 数据传输的可靠性。 1 5 论文的组织结构 本文在第二章介绍了设计与实现片上网络容错路由器所需要考虑的关键技术。在此基础上， 第三章设计并实现了两种典型的基于编码的检错重传机制，并对两种容错路由器的具体的设计 做了详细的介绍，最后在延时、面积和功耗三个方面对两种容错机制进行了对比分析。第四章 针对深亚微米工艺下片上网络的主要干扰源，研究并提出了更加合适的编码方案，解决了对串 扰的预防以及对其他故障源产生的瞬时故障的检测问题。第五章在前四章的基础上，实现针对 永久性故障的容错路由器，配合课题组提出的对网络全局链路状态监控的n o c 结构，同时解决 瞬时故障和永久性故障的容错问题。 6 南京航空航天大学硕士学位论文 第二章可靠性研究的关键技术与基础 路由器是片上网络仿真平台的核心组件，其主要功能是进行数据包的转发，即从资源节点 接收数据包并转发到另一个路由器或资源节点，而具有容错功能的路由器的设计与实现是进行 n o c 数据传输可靠性研究的基础。本章将首先阐述片上网络容错路由器的结构以及需要考虑的 关键技术。 ，2 1 网络拓扑结构 设计片上网络容错路由器，首先确定路由器工作的网络拓扑结构，然后选择交换方式、容 错机制、容错算法、定义数据包格式等，最后才是划分模块、进行具体的电路设计。 n o c 拓扑结构定义系统中每个计算资源结点通过信道与其它计算资源结点的连接关系【3 1 l 。 通常，根据不同的通信任务，片上网络采用不同的拓扑结构。目前，片上网络研究中主要采用 的拓扑结构有三种，l l p 2 d m e s h ，t o m s ，和蝶形胖树( b u t t e r f l yf a tt r e e ，b f t ) 结构，如图2 1 所示。 ( 矗)2 h e s h 拓扑结构( b )岫拓扑结构 路由曩 口壹彝节点 k 。这个二进$ 1 j n 元组v 就被称为消息u 的码字。因此，与2 0 个可能的消息相 对应，就有2 0 个消息码字。这个2 。个码字的集合称为一个块的编码。要使一个块编码有效，这 2 。个码字必须是彼此不同的。一个二进制的码字是线性的，当且仅当对两个码字的模2 的和，仍 是一个码字1 4 2 1 。 2 6 2 常用线性编码 常用的线性编码有奇偶校验吗、汉明码等。奇偶校验码是在源代码的基础上增加一个校验 位，使各代码中含有l 的个数均为奇数( 称为奇校验) 或偶数( 称为偶校验) ，进而通过判别代 ? 一码中1 的总数的奇偶性来决定代码的合法性【4 3 1 。通过增加合法代码间的汉明距离，将可以提高 检错功能，进而可以获得纠错功能，建立在这一基础上的纠错码叫做汉明纠错码，汉明码非常 灵活，根据编解码器的设计，可以得到汉明码的若干不同版本：单个错误纠正编码( s e c ) 、 单个错误纠正和双重错误检测编码( s e c d e d ) 以及错误检测汉明码( e d ) 1 6 , 4 引。 对于我们设计的路由器，采用3 2 比特的数据线，根据瞬时故障模型，各个传输线的b e r 相 对独立，因此得到如下不同编码方案的剩余微片字错误率如下 4 4 1 ，其中为每根传输线的b e r ， 4 为码重为f 的汉明码。 无编码的情况： = 【1 一( 1 一) 3 2 】 ( 2 - 3 ) s 髓： e s = l - 壹, - - o k ( 1 一岛) 3 c 2 4 ) s e c d e d ： e d ： 奇偶校验码： = 善( 2 ，3 + 9 。j 嘞2 t + 1 0 一) 3 9 。2 h c 2 剞 3 8 = a , e ( 1 一占) 3 l = l = 辩卜h 尸捌 ( 2 _ 6 ) ( 2 7 ) 虽然奇偶校验码相比s e c 和s e c d e d 码不具有纠错能力，但配合所设计的检错重传机制可 以实现对瞬时故障的检测与恢复。e d 码虽然具有对更强的检错能力，但编码的冗余度较大，实 现复杂。在深亚微米工艺下，由于串扰的影响，传输链路上的瞬时故障主要为多重错误而并非 单重错误，奇偶校验码的检错能力较弱，但本文第四章所提出的编码方案将有效的避免由于串 扰产生的多重错误。因此，采用实现简单的奇偶校验码，能够降低设计的复杂度与系统开销。 1 3 基于编码的片上网络数据传输可靠性研究与设计 第三章针对瞬时故障的容错机制研究与设计 针对传输链路上的瞬时故障，需要采用基于编码的差错控制机制进行故障检测与恢复。本 章将设计并实现基于编码的点到点检错重传和端到端检错重传这两种不同容错机制的路由器。 首先定义数据包的格式，然后给出两种容错路由器结构的详细设计方案，采用s m i co 1 8 岬的 工艺库在s y n 叩s y s 公司的e d a 环境下完成了两种容错路由器的r t l 级模型，进行仿真