（计算机应用技术专业论文）基于令牌加固的自恢复容错控制器设计研究.pdf

基于令牌加固的自恢复容错控制器设计研究摘要随着集成电路的特征尺寸进入纳米量级，持续降低的工作电压、急剧升高的工作频率以及明显提高的集成密度等原因，导致软错误率快速攀升。作为集成电路关键的应用领域之一，也是微处理器的核心部分，控制器对于软错误的容忍能力直接决定了微处理器芯片乃至整个系统的健壮性。另外，集成电路设计规模和设计复杂度的不断上升，使得传统的自动测试设备成本持续增加，对控制器的测试尤为困难。因此，具有自恢复、内建自测试等容错性能的控制器设计研究越来越受到人们的关注。软错误主要分为单事件翻转( s e u ) 和单事件瞬态( s e t ) 两类。本文对容s e u控制器的设计展开了研究，主要工作如下：首先，对c h a i t i n s 染色算法加以改进之后编程实现，用于有限状态机的拆分，程序可自动生成供综合、仿真之用的各种自恢复结构的v e r i l o g 及其他文件。其次，将三模冗余( t m r ) 和双模冗余( d m r ) 两种容错结构分别与令牌控制逻辑相结合，提出两种令牌加固( h a r d e n i n gt o k e n ) 容错结构，即三模冗余令牌结构( t m r t o k e n ) 和双模冗余令牌结构( d m r t o k e n ) 。它们对发生在状态寄存器的s e u 可以通过自恢复机制实现容错；当令牌寄存器发生s e u 时，t m r t o k e n结构由于将令牌寄存器复制了三份，通过v o t e r 单元可以过滤掉其中一个备份的s e u 从而保证令牌输出正确，而d m r t o k e n 结构的c e l e m e n t 单元则利用两个备份寄存器内容的不一致性阻塞s e u 对令牌输出的影响。最后，对b y p a s sp i p e l i n e ( b p ) 、t m r t o k e n 和d m r t o k e n 三种自恢复结构在容错性能、面积开销两方面进行了实验对比。结果表明t m r t o k e n 和d m r t o k e n 有效解决了b p 结构无法容忍令牌寄存器发生s e u 的问题。与b p相比，t m r t o k e n 和d m r t o k e n 的时延几乎没有增加，而增加的面积也分别在5 和3 以下。关键词：软错误：单事件翻转；有限状态机：拆分：三模冗余；双模冗余t h es t u d yo ns e l f - r e c o v e r i n gf a u l t - t o l e r a n tc o n t r o l l e rd e s i g nb a s e do nh a r d e n i n gt o k e na b s t r a c ta st h ef e a t u r es i z eo fi n t e g r a t e dc i r c u i t s ( i c s ) d e c r e a s e st on m ，t h ew o r k i n gv o l t a g ei sd r o p p i n gc o n s t a n t l y , t h ew o r k i n gf r e q u e n c yi si n c r e a s i n gd r a m a t i c a l l y ,a n dt h ei n t e g r a t e dd e n s i t yi sr i s i n gd r a s t i c a l l y c o n s e q u e n t l y , t h es o f te r r o rr a t e( s e r ) b e c o m eh i g h e ra n dh i g h e r a so n eo ft h ec r i t i c a la p p l i c a t i o n so ft h ei c s ，c o n t r o l l e r sp l a ys i g n i f i c a n tr o l e si nm i c r op r o c e s s o r s ，w h o s ec a p a c i t yo fs o f te r r o rt o l e r a n c ed i r e c t l yd e t e r m i n e st h er o b u s t n e s so fm i c r op r o c e s s o r s ，e v e nt h ew h o l es y s t e m o nt h eo t h e rh a n d ，t h ee v e r i n c r e a s i n gs c a l ea n dc o m p l e x i t yo fi cd e s i g nm a k et h ec o s to fa u t o m a t i ct e s te q u i p m e n t si sm o r ea n dm o r ee x p e n s i v e ，a n dt e s t i n gc o n t r o l l e r si sh a r de s p e c i a l l y t h e r e f o r e ，t h ed e s i g no fc o n t r o l l e r sw i t hs e l f - r e c o v e r ym e c h a n i s ma n db u i l t - i ns e l f - t e s tf u n c t i o ni sd r a w i n gm o r ea n dm o r ea t t e n t i o n t h e r ea r et w ot y p e so fs o f te r r o r s ，s e u ( s i n g l ee v e n tu p s e t ) a n ds e t ( s i n g l ee v e n tt r a n s i e n t ) a n dt h er e s e a r c ho fs e ut o l e r a n tc o n t r o l l e r sd e s i g ni sd e v e l o p e di nt h et h e s i s ，t h em a i n w o r ko fw h i c hi ss h o w e da sf o l l o w s i n i t i a l l y , c h a i t i n sa l g o r i t h mi si m p r o v e dt os p l i tf s m s ，a n dt h ea l g o r i t h mi si m p l e m e n t e db yc + + p r o g r a mw h i c hc a ng e n e r a t ev e r i l o ga n do t h e rf i l e so fv a r i o u ss e l f - r e c o v e r ys t r u c t u r e sf o rs y n t h e s i sa n ds i m u l a t i o n t h e nt m r t o k e na n dd m r t o k e n ，c o l l e c t i v e l yr e f e r r e dt oa sh a r d e n i n gt o k e ns t r u c t u r e s ，a r ep r e s e n t e dc o m b i n i n gt h et o k e nl o g i cw i t ht m r ( t r i p l em o d u l a rr e d u n d a n c y ) a n dd m r ( d o u b l em o d u l a rr e d u n d a n c y ) r e s p e c t i v e l y b o t hp r e s e n t e ds t r u c t u r e sc a nt o l e r a t es e u si ns t a t er e g i s t e r sb yt h es e l f - r e c o v e r ym e c h a n i s m i fa ns e uh a p p e n si no n ec o p yo ft o k e nr e g i s t e r s ，t h ev o t e ro ft m r t o k e nw i l lf i l t e ri tb e c a u s et h eo t h e rt w oc o p i e sk e e pr i g h t ，w h i l ed m r t o k e nw i l lp r e v e n tt o k e no u t p u t sf r o mt u r n i n ge r r o ra c c o r d i n gt ot h ei n c o n s i s t e n c yo ft w oc o p i e s f i n a l l y , b y p a s sp i p e l i n e ( b p ) ，t m r - t o k e na n dd m r t o k e na r ec o m p a r e do ns o m ea s p e c t ss u c ha ss o f te r r o rt o l e r a n tp e r f o r m a n c ea n dt h ea r e ao v e r h e a d t h er e s u l t sa p p e a lt h a tt h ep r e s e n t e ds t r u c t u r e sc a nt o l e r a t es o f te r r o r si nt o k e nr e g i s t e r s ，w h i c hc a n n o tb ea c h i e v e db yb p m o r e o v e r ，t h e i ra d d i t i o n a lt i m ed e l a yi sn e g l i g i b l ea n dt h ea r e ao v e r h c a di s1 e s st h a n5 a n d3 r e s p e c t i v e l y , c o m p a r e dw i t hb p k e y w o r d s ：s o f te r r o r ；s e u ；f s m ；s p l i t t i n g ；t m r ；d m ri i插图清单图1 1自恢复控制器的工作原理3图2 1通用的状态机结构6图2 2 另一种状态机结构6图2 3各种软错误所占比例7图2 4卷回操作示意图7图2 5简单的自恢复状态机结构图j 8图2 6简单的自恢复状态机卷回操作示意图8图2 7b y p a s sp i p e l i n e 结构示意图9图2 - 8正常情况下b p 结构运行过程1 0图2 9状态寄存器发生s e u 时b p 结构运行过程1 0图3 1消除回环1 1图3 2拆分前状态机的状态转移图1 1图3 3拆分后状态机的状态转移图1 1图3 4算法3 1 流程图13图3 5c h a i i t i n s 染色算法示例m = 3 ) 1 3图3 - 6c h a i i t i n s 染色算法示例( n - 2 ) 1 3图3 7算法3 2 流程图15图3 8t m r 结构示意图1 5图3 9v o t e r 结构示意图15图3 1 0d m r 结构示意图1 6图3 1 1c e l e m e n t 的结构和功能1 6图3 1 2f l i p f l o p 的组成1 6图3 1 3b p 结构示意图( 含令牌控制逻辑) 1 7图3 1 4b p 结构令牌寄存器出错时的运行过程1 7图3 1 5h a r d e n i n gt o k e n 结构示意图1 8图3 1 6h t 结构子状态机示意图1 9图3 1 7h t 结构检错逻辑示意图1 9图3 18 加固前的令牌控制逻辑1 9图3 1 9t m r t o k e n 令牌寄存器的f l i p f l o p 2 0图3 2 0d m r t o k e n 令牌寄存器的f l i p f l o p 2 0图3 2 1t m r t o k e n 结构令牌寄存器发生s e u 2 1图3 2 2d m r t o k e n 结构令牌寄存器发生s e u 2 1图4 1软件编译和硬件综合的类比2 2图4 2综合的步骤一2 3图4 3d c s h e l l 界面2 5图4 4d c s h e l l t 界面2 5图4 5n c v e r i l o g 仿真器的用户界面2 8图4 6选择存储目录2 8图4 7创建c d s 1 i b 库文件2 8图4 8编译设计文件2 8图4 9选择信号显示2 8图4 1 0n c v e r i l o g 仿真波形2 9v i图4 1 l图4 1 2图4 1 3图5 1图5 2图5 3图5 4图5 5图5 6图5 7图5 8图5 9图5 1 0h s p i c e 界面一3lh s p i c e 选择信号界面3lh s p i e e 显示波形界面3lk i s s 2 文件格式3 2t r a n s i t i o n 类3 2s t a t et r a n s i t i o nt a b l e 类3 3g r a p h 类3 3n o d e 类3 3顶层模块的宏定义3 4对令牌寄存器l a t c h 的s e u 注入结点3 5b p 结构与h t 结构令牌控制逻辑的h s p i c e 仿真效果对比3 5t e l 脚本文件一3 6s y n o p s y s d c s e t u p 文件3 6v i i表3 1表3 - 2表4 1表5 i表格清单拆分前的状态转移表1 2拆分后的状态转移表1 2d c 常用命令2 7b p 及两种h t 结构面积开销对比( 单位：陋2 ) 3 6v i i i独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得金目垦王些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签字：子心纠签字日期：沙件甲月1 3 日学位论文版权使用授权书本学位论文作者完全了解金月墨王些太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金目墨王些态堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位论文作者签名：孑心名斗签字日期：汐c 1 年v 月1 3 日学位论文作者毕业后去向：工作单位：通讯地址：导师签名：嘲签字日期：夕刃秽9 月岁日电话：邮编：致谢光阴荏苒，转瞬又是三年。一样的校园，一样的离别，不一样却是自己。衷心感谢我的导师梁华国教授。我所取得的每一点进步，都凝聚着梁老师的汗水和心血。您对我的殷切期望和悉心关怀，时刻激励着我努力拼搏、不断进取；您敏锐独到的学术见解、精益求精的工作态度以及对我们的严格要求不仅使我在读研期间受益匪浅，更将对我今后的工作和生活产生深远影响。衷心感谢黄正峰老师在学术上的耐心指导、在生活上的细致关怀，感谢你一直对我懒惰任性的大度包容!衷心感谢曹航老师在工作学习、为人处事方面的谆谆教导，您的耳提面命我将铭记终生!李扬师姐的欢声笑语，给我们枯燥寂寞的研究平添了许多轻松和快乐；往届师兄师姐对我工作的肯定，激励我拿出更多的热情与耐心帮助需要帮助的人；与师弟师妹们频繁的合作与讨论，激发了我的灵感，开阔了我的思路，在此由衷地表示感谢! 特别要感谢董少周带我初尝音乐的美妙，以及祝沈财师兄和毛蔚、郭凯两位师弟陪我一次又一次在跑道上挑战极限!感谢欧阳一鸣副教授、易茂祥副教授、王伟、刘军、陈田、詹文法、刘杰等老师以及王保青、宋灏龙、覃敏东、朱兵、张岚、刘娟等同学为我的研究、学习及生活提供了许多支持与帮助!感谢父母对我理解和支持!感谢所有关心和爱护我的亲人和朋友!最后，衷心感谢为评阅论文而付出辛勤劳动的各位专家学者。i i i作者：孙科2 0 0 9 年4 月第一章绪论1 1概述1 1 1 研究背景和意义根据信息产业部2 0 0 8 年1 月发布的集成电路产业“十一五”专项规划，2 0 0 5年我国集成电路( i c ，i n t e g r a t e dc i r c u i t s ) 市场规模达3 8 0 0 亿元，预计到2 0 1 0 年将增至8 3 2 0 亿元，然而2 0 0 5 年我国的集成电路自给比例只有1 6 t 1 】【2 】。这意味着国内市场所需大部分i c 产品需要进口，对具有自主知识产权的i c 产品尤其是高技术核心芯片( 如控制器) 的需求极为迫切。但是，随着i c 技术的迅猛发展，我国的i c 国产化之路面临着许多新问题。一方面，随着i c 的特征尺寸进入纳米量级，持续降低的工作电压、急剧升高的工作频率、明显增加的集成密度等原因，使得电路对于粒子辐射、电源和互连噪声、电磁干扰的敏感度加剧，导致瞬态故障引发的软错误率( s e r ，s o f te r r o rr a t e ) 快速攀升。目前计算机系统8 0 9 0 的失效都是软错误引起的l j j ，且据相关文献预测从1 9 9 2 年到2 0 1 1 年，软错误率将上升9 个数量级【4 】。需要强调的是，微处理器中的不同部件对于软错误的敏感性差异很大。控制器作为微处理器的最核心部分，它对于软错误的敏感性直接决定了微处理器芯片乃至整个电子系统的健壮性。针对d l x 、a l p h a 等处理器的故障注入实验表明，控制器发生软错误导致指令无法完成的比例占到6 9 t5 。另一方面，i c 设计规模和设计复杂度的不断增加，使得传统的自动测试设备a t e 成本不断增加。国际半导体组织预测，一台高速测试仪器需要1 千多万美元，测试成本将会占到制造芯片成本的半以上。另外，由于新的设计风格和创新技术不断涌现，大量的芯核嵌入到个芯片当中，有限的管脚难以承受庞大的测试任务。尤其对控制器的测试十分困难，往往控制器位于芯片核心位置，周围分布大量的受控部件，这样外部测试难以进入。而内建自测试却能够解决这一难题，测试完全在片上执行，不仅能够克服对芯片管脚的依赖，而且能够缓解对高性能a t e 的需求。近年来，“神舟 系列载人飞船以及“嫦娥系列探月卫星的陆续升空，在标志着我国航天事业实现了跨越式发展的同时，也对于自主研发的高可靠控制器提出了更加迫切需求。因此，具有自恢复及内建自测试等容错性能的高可靠控制器的设计与制造成为迫在眉睫的研究课题。1 1 2 容错控制器研究现状目前国内外的容错控制器研究，主要分为空间冗余和时间冗余两大类。空间冗余技术的代表性方案有：基于可编程器件的可重构容错方案、信息冗余方案、时序单元加固方案；时间冗余技术的代表性方案有：基于软件冗余的线程级容错方案、基于时间冗余的回卷恢复方案。( 1 ) 基于可编程器件的可重构容错方案。在芯片部分电路失效后，对故障单元进行隔离，对正常单元进行资源整合，完成芯片的快速在线重构。其发展趋势是可进化硬件( e v o l v a b l eh a r d w a r e ) 【6 1 。目前，可进化硬件的研究在三方面存在瓶颈：进化计算速度、进化结果评估、进化硬件规模。( 2 ) 信息冗余方案【7 】在微处理器芯片s u nu l t r a s p a r ci i 、i b mp o w e r p c a 1 0 、a l p h a 2 1 2 6 4 、i n t e li t a n i u m 中都得到了应用。信息冗余通常对于单位出错的情形比较有效，但是处理多位同时出错的情形则开销极大。( 3 ) 时序单元加固方案【8 】可以在时序单元内部构建多冗余的容错微结构，通过多模结构之间的逻辑交织互锁和状态反馈，针对单事件翻转( s e u ，s i n g l ee v e n tu p s e t ) 进行防护。也可以结合时间冗余技术，针对单事件瞬态( s e t ，s i n g l ee v e n tt r a n s i e n t ) 并t l s e u 同时进行防护。该类方法立足于定制具有容错功能的时序单元，可以有效阻塞软错误，但是硬件开销、功耗、延迟较大，如果在关键路径上使用该方案会影响控制器性能。( 4 ) 基于软件冗余的线程级容错方案。微处理器芯片从单核单线程、单核多线程、多核多线程发展到片上网络，出现了利用同时多线程处理器( s m t ,s i m u l t a n e o u sm u l t i t h r e a d i n g ) 进行容错计算的思路【9 】。a r s m t 的实质是时间冗余技术，但是主线程和冗余线程之间的资源竞争会降低性能。( 5 ) 基于时间冗余的回卷恢复方案。该方案已经在芯核级【l 叭、流水线级【1 1 1 、指令级 t 2 1 等不同层次得到应用。回卷恢复方案主要问题在于检查点开销过大和回卷恢复时间过长。文献 13 1 4 15 】提出b y p a s sp i p e l i n e 控制器结构是一种较为突出的时间冗余方案，该结构通过状态机拆分形成子状态机，再用它们进行状态备份完成自恢复操作，硬件代价较小，卷回速度快。但其最大的缺点是，不能对令牌寄存器进行检错和恢复，一旦令牌寄存器出现s e u 整个控制器将陷入混乱。国内方面，国防科技大学设计了容软错误的微控制器f t 5 1 ，f t 51 基于异步电路的时空三模冗余微结构，可以有效对软错误进行防护。与未经加固的版本相比，f t 5 1 的额外面积开销为8 0 6 ，额外性能开销为19 到l3 3 i l 引。中科院计算所自主设计的自修复芯片即将投片，并尝试以“龙芯”系列c p u 为载体，在微结构级向分支指令后插入冗余指令【1 7 】。湖南大学提出多线程回卷恢复架构，开发了回卷恢复试验床w i n d a r 1 8 】，主要是在软件级进行回卷恢复研究。哈尔滨工业大学提出了基于硬件实现的线程级处理器容错方案：基于微线程的粗粒度超标量容错结构【l9 1 。哈尔滨工程大学提出了容错单芯片多处理器的设计思想 2 们。1 1 3 内建自测试技术研究现状经典的内建自测试方案主要可分为三类：测试扫描方案( t e s t p e r s c a n ) 、测试时钟方案( t e s t p e r c l o c k ) 以及多扫描链测试方案。测试扫描方案主要在2被测试电路中构造出一条扫描链，测试模式应用串行移入扫描链，具有测试硬件开销低等优点，但是随着电路规模和扫描链长度的增加，测试应用时间难以忍受【2 2 】。测试时钟方案是在测试的每个时钟周期应用一个完整的测试模式有时也称为并行测试方案，其主要的优点是测试时间快，但其硬件开销也相当的大口3 i 。为了平衡测试应用时间以及测试硬件开销多扫描链的测试方案被业界广泛采用1 2 4 1 2 ”，例如在c a d e n c e 、s y n o p s y s 等公司的e d a 工具中都有相应的实际应用产品。同时，国内多家科研院、所及高校研究机构开展集成电路的测试研究工作。针对国外对我国测试设各主要性能指标有出口限制，国内现有测试设备的存储量不足的问题，中科院计算所李晓维、韩银和等人提出了一系列激励压缩和响应压缩方法【2 6 】，并应用于龙芯高性能处理器设计，突破了这些限制。另外清华大学的向东和冯建华教授、东南大学的胡晨教授、电子科技大学的谢永乐教授、湖南大学的邝继顺教授等，先后开展了对集成电路内建自测试的方法研究。i 2研究内容、拟解决的关键问题及创新之处12 1 研究内容( 1 ) 通过状态机拆分，构建自恢复控制器控制器可以建模为有限状态机( f s m ，f i n i t es t a t em a c h i n e ) 。和传统的卷回恢复机理不同，本研究通过有限状态机拆分，让子状态机间相互备份，无需额外设立备份寄存器，在节省硬件开销的同时，缩短了恢复时间。图1 ，1自恢复控制器的工作原理图1 - 1 为自恢复控制器的工作原理。原状态机拆分为n 个子状态机后，通过令牌( t o k e n ) 逻辑进行控制。持有令牌的子状态机代表控制器当前状态，未持有令牌的子状态机充当备份。令牌在于状态机之间传递，保证同一子状态机不能连续两个周期持有令牌。检错逻辑( e h e e k e r ) 选取当前状态进行检查。如检查到软错误则通知令牌逻辑调整令牌传递过程，让令牌重新回到出错前一个周期持有令牌的子状态机，重新执行相关操作，从而完成自恢复。图2 为拆分后状态机的工作原理示意图，图中n = 3 ，s 、s b 、s c 是分别代表拆后的三个子状态机。( 2 ) 构建可靠的令牌控制逻辑令牌控制逻辑( 图1 1 中t o k e n ) 是本课题中容错控制器的关键部分。它在正常条件下负责令牌在各子状态机间的调度，并指示检错电路的检测对象；在子状态机出现软错误后，负责将令牌还给出错前持有令牌的子状态机，并重新执行随后的令牌调度。如果令牌控制逻辑发生软错误，整个控制器将陷入混乱，无法正常工作。因此，构建可靠令牌控制逻辑对整个控制器来说至关重要。( 3 ) 实现检错电路的完全自校验状态机的自恢复过程由检错电路( 图1 1 中c h e c k e r ) 触发，因此检错电路的输出信号必须准确可靠。因此，实现检错电路的完全自校验，保证其输出不以软错误影响对控制器的自恢复过程具有重要意义。1 2 2 拟解决的关键问题本文所研究的自恢复控制器工作原理如图1 1 所示。自恢复控制器由以下三个部分组成：( 1 ) 子状态机( s a 、s b 、s c ) ；( 2 ) 令牌控制逻辑( t o k e n ) ；( 3 )检错逻辑( c h e c k e r ) ；对应恢复控制器的三个部分，本文拟解决的关键问题在于：( 1 ) 寻找有效算法生成拆分最佳的状态机拆分方案，使硬件开销、时间延迟达到最小，并为实现自恢复及内建自测试创造条件；( 2 ) 寻找有效的容错结构，构建可靠的令牌控制逻辑；( 3 ) 实现检错逻辑的完全自校验。1 2 3 本论文的创新之处( 1 ) 编程实现改进的c h a i t i n s 算法，用于拆分有限状态机本文对c h a i t i n s 染色算法加以改进之后编程实现，用于拆分状态机。程序可自动生成供综合、仿真之用的b p 、t m r t o k e n 和t m r t o k e n 自恢复结构的v e r i l o g 文件以及所需s y n o p s y s d c s e t u p 文件和测试向量。( 2 ) 利用三模冗余、双模冗余等容错结构，构建可靠的令牌控制逻辑本文将三模冗余( t m r ，t r i p l em o d u l a rr e d u n d a n c y ) 和双模冗余( d m r ，d o u b l em o d u l a rr e d u n d a n c y ) 两种容错结构分别与令牌控制逻辑相结合，提出两种令牌加固( h a r d e n i n gt o k e n ) 容错结构，即三模冗余令牌结构( t m r t o k e n ) 和双模冗余令牌结构( d m r t o k e n ) 。它们对发生在状态寄存器的s e u 可以通过自恢复机制实现容错；当令牌寄存器发生s e u 时，t m r t o k e n 结构由于将令牌寄存器复制了三份，通过v o t e r 单元可以过滤掉其中一个备份的s e u 从而保证令牌输出正确，而d m r t o k e n 结构的c e l e m e n t 单元则利用两个备份寄存器内容的不一致性阻塞s e u 对令牌输出的影响。41 3论文结构安排本文其他章节结构安排如下：第二章首先简要介绍了有限状态机的基本概念以及s e u 与s e t 、卷回操作、自恢复机制等容错方面基本知识；接着详细描述了简单自恢复结构、b y p a s sp i p e l i n e 结构等一些典型的自恢复容错结构以及运行过程。第三章首先申明了状态机拆分的原则，在此基础上引入c h a i t i n s 染色算法加以改进之后用于状态机拆分；之后详细介绍了t m r 、d m r 两种容错结构的容错原理；随后将两种结构与令牌控制逻辑相结合，进而提出t m r - t o k e n 与d m r t o k e n 两种h a r d e n i n gt o k e n 容错结构。第四章简单描述了综合及仿真的概念，并简要介绍了综合软件d e s i g nc o m p i l e r 和仿真软件n c v e r i l o g 以及晶体管级仿真软件h s p i c e 的使用方法。第五章详细阐述了本文的实验方案，并通过各步骤的实验结果在容错性能、时间延迟、面积开销等方面对b y p a s sp i p e l i n e 结构和d m r t o k e n 、t m r t o k e n两种h a r d e n i n gt o k e n 结构进行了对比分析。第六章总结了本文的工作，并对下一步的研究进行了展望。第二章b y p a s sp i p e l i n e 自恢复结构2 1有限状态机有限状态机( 简称状态机) 是设计时序逻辑电路的重要工具。本课题中对高可靠性控制器的综合问题最终可以归结为状态机的设计与优化。通用的状态机结构图如图2 1 所示，其中灰色块r 代表状态寄存器( 为简洁起见，本文图中所有时序逻辑中圆角矩形表示，并省略了时钟输入信号；而组合逻辑则用矩形表示) ，用于存储当前状态；白色块表示组合逻辑，其中万表示次态函数，其输入为i n p u t s ( 输入) 与c u r r e n ts t a t e ( 现态) 的组合，允表示输出函数，其输入为c u r r e n ts t a t e ( m o o r e 型) 或i n p u t s 与c u r r e n ts t a t e 的组合( m i n i 型) 。图2 1通用的状态机结构传统的综合工具经常把状态机的次态函数万与输出函数五放在一起，表示成图2 所示的结构。图中分别由万和元计算出状态机的次态n e x ts t a t e 及输出o u t p u t s ，由r 存储当前状态。下文所述的其他状态机结构，均是在图2 - 2 的基础上改进而成。图2 - 2 另一种状态机结构2 2瞬态故障、软错误、s e u 与s e t瞬态故障( t r a n s i e n tf a u l t s ) 是由于i c 受到来自太空的宇宙射线以及来自包装材料的口粒子和中子的轰击而造成的【2 8 1 。与我们熟知的永久性故障( p e r m a n e n tf a u l t s ) 不同，瞬态故障产生的错误是瞬时的，可以在短时间消失，因此瞬态故障产生的错误又称软错误( s o f te r r o r ) 。很多文章将瞬态故障和软错误等同使用。传统观念认为这些射线与粒子能量很低，不会引起地面上的集成电路发生功能错误。但是，随着i c 的特征尺寸进入纳米量级，持续降低的工作电压、急剧升高的工作频率、明显提高的集成密度等原因，使得i c 受到较低能量粒子干扰的可能性越来越大。软错误率( s e r ，s o f te r r o rr a t e ) 持续攀升。如上文所6述，目前计算机系统8 0 9 0 的失效都是软错误引起的，而且根据预测从1 9 9 2年至u 2 0 1 1 年，软错误率将上升9 个数量级。图2 - 3 各种软错误所占比例软错误主要分为单事件翻转( s i n g l ee v e n tu p s e t ，s e u ) 和单事件瞬态( s i n g l ee v e n t t r a n s i e n t s e t ) 两类。s e u 是指时序逻辑由于粒子撞击而发生的状态翻转，而s e t 指的是组合逻辑受粒子轰击时产生的噪声脉冲。s e u 发生的频率很高，如商用m i p sr 3 0 0 0 微处理器在5 0 0 公里地球近地轨道上大约每分钟发生一次s e u l 2 9 。而s e t 只有被时序逻辑采样到才会引发i c 的功能错误，而且在传递到时序逻辑之前可能会由于逻辑覆盖( 1 0 9 i c a lm a s k i n g ) 、电子覆盖( e l e c t r i c a lm a s k i n g ) 和时间窗覆盖f t i m e w i n d o wm a s k i n g ) 等因素减少了引发软错误的可能性hj 。另据统计，时序逻辑的s e u 引发的s e r 是组合逻辑的s e t 的近五倍，如图2 - 3 所示【3 4 】。因此，s e u 是引发软错误的主要因素。- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一图2 4 卷回操作示意图2 3检查点、卷回操作与自恢复机制所谓卷回操作( r o l l b a e k ) 就是将系统恢复到几个时钟周期以前的某个正确状态。这就要求系统在某些时钟周期边缘把正确状态存储起来。被存储的状态通常被称为检查点( e h e e k p o i n 0 。系统如检测到当前状态发生错误，就执行次卷回操作，用检查点覆盖系统当前的错误状态。这种卷回操作在一些数据库系统已经有多年成功运行的历史【3 0 】。像这样系统在发生软错误后，可以利用检查点和卷回操作自动恢复到正确状态的机制，本文称之为自恢复机制( s e l f r e c o v e r ym e c h a n i s m ) 。图2 - 4 中描述了一个卷回操作的实例。在第2 个周期发生了一个错误，它在第3 个周期就被检测出来。随后，卷回操作通过用第2 个周期初存储的检查点覆盖当前错误状态的方法将系统状态恢复到第2 个周期初的正确状态。然后，第2 个周期里执行的操作又被重新执行。2 4简单的自恢复结构图2 5 所示的结构是一种可以进行卷回操作的自恢复结构。为实现卷回操作，此结构在传统状态机( 图2 2 ) 的基础上增加了两个状态寄存器r l 、r 2 ，一个触发器e f ，一个多路选择器m u x 以及检错逻辑c h e c k e r ( 虚线框内为增加的部分) 。寄存器r l 与r 2 作为备份寄存器，组成一个先入先出结构，分别用于存储一个周期前和两个周期前r o 的内容( 即检查点) 。检错逻辑c h e c k e r 用于检查存储在r o 中的当前状态。为避免因复杂的c h e c k e r 电路占用关键路径而影响系统性能，增加了一个错误信号触发器e f 用于存储c h e c k e r 的结果( 这里假设c h e c k e r在一个时钟周期内检测出错误) 。m u x 根据e f 的输出信号选择r o 或者r 2 的内容传递给艿和旯，所以e f 的内容将决定是否进行卷回操作。图2 - 5 简单的自恢复状态机结构图图2 - 6 是上述结构的卷回操作时序图。正常情况下( 图中的前三个周期) ，r o 存储的当前状态未出错，c h e c k e r 电路的检测结果( 即图4 中的e r r o r ) 为o ，r i与r 2 中存储的分别是一个周期前和两个周期前r o 的内容( 如第2 个周期所示) 。多路选择器m u x 选择的r o 的内容作为组合逻辑的输入。第3 个周期，r o 存储的当前状态s 3 出错。第4 个周期，错误状态岛展递至 j r l ，而r o 进入一个未定义状态，由c h e c k e r 检测出的错误信号传递给e f ( e r r o r 变为1 ) ，多路选择器m u x 根据e f 信号选择r 2 的内容s 2 ( 即第2 个周期的正确状态) 作为组合逻辑块的输入。第5 个周期，由次态逻辑艿计算出的正确状态s 3 就会传递到r o 。此时，状态机卷回到两个周期以前未出错时的状态，从而完成一次自恢复操作。n114气6c l o c k 几八几八八几几，丽蕊r o硒 ) 互k d 冱飓 ) c 互挺d 互e 一八_ 一_ _ _ _ _ _ _ _ _ 一图2 - 6 简单的自恢复状态机卷回操作示意图图2 6 所示的卷回操作类似于w i n d o w sx p 操作系统的系统还原点技术。在系统出错时可以从检查点执行卷回操作，因为检查点事先保存了以前若干个时刻的正确工作状态和相关信息。二者区别在于：前者采用硬件备份。由硬件完成出错判断和卷回操作，而后者采用软件备份，由操作系统完成出错判断和卷回操作。因此前者速度更快，实时性更好。另外这种卷回操作可以和撮新的有限状态机优化技术诸如：有限状态机拆分技术、等价类相容类归并技术、检错倒错编码技巧相结合，并且无缝嵌入到现有的逻辑综合工具中，在i c 设计中直接、迅速地发挥作用。2 5b y p a s sp i p e l i n e 自恢复结构图2 - 5 所示简单的自恢复状态机虽然能够执行卷回操作，实现了自恢复机制，但它在原有状态机的基础上增加了两倍以上的时序逻辑( r ，、r 2 及e f ) 以及额外的组合逻辑( c h e c k e r 和m u x ) ，面积及功耗开销巨大。在图2 - 5 所示结构基础上，a n d r e h e r t w i g 等人提出了b y p a s sp i p e l i n e 结构，本文简称为b p 结构，如图2 7 所示。为简洁起见，图中省略了的每条连线上的”，”以及三个时序逻辑部件( r r 及r c ) 的时钟输入( 下同) ，令牌控制逻辑也没有画出。图2 7b y p a s sp i p c l i n e 结构示意图拆分之后，三个子状态机的状态集合构成原状态机状态集合的一个划分，这样每一个周期只会有其中一个于状态机寄存器存储当前状态。其余两个就可以充当备份寄存器存储以前的正确状态，如当前状态发生错误，状态机就可以卷回到若干个时钟周期以前的正确状态。无需增加额外的备份寄存船来实现卷回操作。由于三个子状态机的状态集合均是原状态机状态集合的子集，它们所需的寄存器位数会相应减少。同时，拆分之后原状态机组合逻辑被三个更为简单的子状态机组合逻辑取代，关键路径明显缩短。硬件及时间开销比图2 - 5 所示简单的自恢复状态机大为降低。2 6b y p a s sp i p e l i n e 结构的运行过程图2 - 8 与图2 - 9 分别说明了正常情况下以及状态寄存器出错时，b p 结构的运行过程。图中t o k e n 指示的持有令牌的子状态机，在图2 - 9 中，第3 周期子状态机c 从子状态机b 得到令牌，而当前状态s 拔生错误( 记为岛) ，第4 周期令牌重新回到b ，使得状态机卷回到存储在r b 中的状态s 2 ，而不是如图2 - 8 那样将令牌转移到子状态机a 。第5 周期，c 收到由b 重新计算出的正确状态s 3 并再次获得令牌，从而完成了一次自恢复过程。m “几几几几几几几i o k p nabaan 五) q p 玉) c ) e 】o d q x dn 田圈卜图2 - 8 正常情况下b p 结构运行过程n1456几几几几几n 几 二二互二二凇r r 圈h 圈一_ 曩r几图2 - 9 状态寄存器发生s e u 时b p 结构运行过程第三章h a r d e n i n gt o k e n 自恢复结构3 1状态机拆分的原则为了实现自恢复和内建自测试，必须对原状态机进行拆分。拆分时遵循的原则是：( 1 ) 拆分后的n 个子状态机的状态集是原状态机状态集的一个划分；( 2 ) 状态跳变只能发生在子状态机之间不能发生在某个子状态机内部按以上原则拆分时经常会出现原始状态机中含有从一个状态到同一个状态的跳变( 如图3 1 左图中的s - ) ，我们称之为回环。如果不加处理，此状态分配到任何个子状态机都会违背第( 2 ) 条拆分原则。针对这种情况，拆分前可以通过增加等效状态的方法消除回环( 图3 1 右圈中的s 即为s l 的等效状态) ，然后再进行拆分。驴 咱伊s 洁图3 1 消除回环以图3 2 所示的状态机为例，我们将其拆分成三个子状态机。拆分后状态机的状态转移圈如图3 - 3 所示。三个子状态机a 、b 、c 的状态集分别用白、灰、黑三色表示，同颜色的状态属于同一个子状态机。图3 - 2 中s o 、s 7 两个状态含有回环，图3 3 中分别增加了等价状态s s 9 。图3 - 2 拆分前状态机的状态转移图图3 - 3 拆分后状态机的状态转移凹表3 - 1 和表3 - 2 分别是图3 - 2 所示状态机拆分前后的状态转移图。表中p s 、n s 分别代表现态( p r c s c n ts t a t e ) 、次态( n e x ts t a t e ) ，i n 、0 u t 分别代表输入与输出。表3 - 2 中用白、灰、黑三色分别表示属于子状态机a 、b 、c 的状态。3 2c h a i t i n $ 染色算法及其改进32lc h a i t i n s 染色算法图3 3 所示的拆分结果是针对小型状态机手工拆分而成的。如果要拆分含有几十甚至上百个状态的大型状态机，必须寻找有效的算法编程实现。31 节所述拆分原则本质上就是一种染色算法，即用n 种颜色对图中所有顶点进行染色，相邻顶点之间颜色不能相同。满足这样要求的算法有很多，其中c h a i t i n s 染色算法比较有代表性。与其他算法相比，c h a i t i n s 染色算法时间复杂度小，仅为o ( n ) ( n 为图中所含的顶点数) ，其伪代码描述如下。表3 - 1 拆分前的状态转移表! ! 塑! !望! ! ：s 。：；：sos 6o! ! ! _ ! 一s 0s 4o! ! ! ! 一s ，0s 41。，!。：；：j一s 。0s 71。，