（计算机科学与技术专业论文）应用级checkpointing技术的研究与实现.pdf

国防科学技术大学研究生院博士学位论文 摘要 随着系统规模的不断扩大和c o t s 器件制造工艺的不断发展，高性能计算机 面临着严峻的可靠性挑战。应用级c h e c k p o i n t i n g 技术是应对这一挑战的关键技术。 但是，当前应用级c h e c k p o i n t i n g 技术面临着性能优势无法充分发挥以及不方便使 用的问题。 本文致力于高效易用的应用级c h e c k p o i n t i n g 技术的研究与实现，着重研究了 应用级c h e c k p o i n t 的优化保存问题，应用级c h e c k p o i n t 全局状态一致性问题，多 c h e c k p o i n t 的总开销最优化问题和应用级c h e c k p o i n t i n g 技术易用性问题。本文的主 要贡献可概括为以下几点： 1 、针对现有活跃变量分析方法不能对m p i 并行程序进行准确分析的问题，我 们定义了m p i 并行程序进程间和进程内的定值引用关系，并提出了m p i 并行程序 活跃变量分析方法叫，a m p 。l a m p 克服了传统活跃变量分析方法既不能区分同 一个变量在各进程上不同的活跃性、也不能分析跨进程定值引用关系的缺点，它 是优化应用级c h e c k p o i n t 数据量从而减小c h e c k p o i n t 开销的基础技术。 2 、深入研究了应用级c h e c k p o i n t 的优化保存问题。我们首先分析了m p i 并行 程序计算状态的组成，确定了对其中占主要部分的各进程计算状态进行优化的思 想：然后提出了一种基于l a m p 的应用级c h e c k p o i n t i n g 技术。实验结果表明该技 术能够有效减小c h e c k p o i n t 数据量和减小c h e c k p o i n t 开销。 3 、深入研究了全局c h e c k p o i m 数据的一致性问题。我们提出了一个基于编译 分析保持应用级c h e c k p o i n t 数据一致性的新方法。该方法不需要记录c h e c k p o i n t i n g 期间的e a r l y 或l a t e 消息，而是通过静态分析找出m p i 程序中安全的c h e c k p o i m i n g 区域的方法，在安全的c h e c k p o i n t i n g 区内保存应用级c h e c k p o i n t 时不需要记录任 何消息。实验证明该方法简单有效。 4 、深入研究了多个c h e c k p o i n t 的总开销最小化问题，提出了一种优化设置多 个c h e c k p o i n t 位置的方法。由于应用级c h e c k p o i n t i n g 开销主要来自写c h e c k p o i n t 文件的时间，我们首先将求解最小的c h e c k p o i n t 总开销近似为求解最小的 c h e c k p o i n t 总数据量。然后将多c h e c k p o i n t 的优化设置问题抽象为一个类似于0 1 整数规划的数学问题。最后给出了两种求解算法。 5 、针对应用级c h e c k p o i n t i n g 的易用性问题，我们设计并实现了一个源到源的 预编译器a l e c ，它可以非常方便地将普通的f o r t r a n 7 7 m p i 程序转换成具有高效 的应用级c h e c k p o i n t i n g 功能的容错程序。 第i 页 国防科学技术大学研究生院博士学位论文 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t w i t ht h ei n c r e a s eo ft h es i z eo fh i g h p e r f o r m a n c ec o m p u t e rs y s t e ma n dt h e d e v e l o p m e n to fc o t sm a n u f a c t u r i n gt e c h n o l o g y , h i g h - p e r f o r m a n c ec o m p u t e ri sf a c e d w i t hs e v e r er e l i a b i l i t yc h a l l e n g e a p p l i c a t i o n - l e v e lc h e c k p o i n t i n gi sa k e yt e c h n o l o g yt o d e a lw i t ht h ec h a l l e n g e h o w e v e r , a tp r e s e n t ，t h ep o t e n t i a lp r o f o r m a n c ea d v a n t a g eo f a p p l i c a t i o n l e v e lc h e c k p o i n t i n gc a nn o tb ee x p l o i t e df u l l ya n dt h i st e c h n o l o g yi sn o t e a s yt ou s e t h eg o a lo ft h i st h e s i si st oa d d r e s sa ne f f i c i e n ta n de a s y t o u s ea p p l i c a t i o n 1 e v e l c h e c k p o i n t i n gt e c h n o l o g yf o rh i g h p e r f o r m a n c ec o m p u t i n g w ef o c u so ns e v e r a l i m p o r t a n t i s s u e sa b o u ta p p l i c a t i o n l e v e l c h e c k p o i n t i n g ，i n c l u d i n gt h eo p t i m i z a t i o n m e t h o do fd a t as a v i n g ，t h ec o n s i s t e n c yi s s u ei n a p p l i c a t i o n 1 e v e lc h e c k p o i n t s t h e o p t i m i z a t i o nm e t h o df o rm i n i m i z i n gt h et o t a lc h e c k p o i n ts i z e a n dt h ee a s y t o u s ei s s u e p r i m a r yc o n t r i b u t i o n so ft h i sp a p e rc a nb es u m m a r i z e da sf o l l o w s ： 1 t oa d d r e s st h ep r o b l e mt h a te x i s t i n ga n a l y s i sm e t h o d sc a nn o td e a lw i t hm p i p r o g r a m sp r e c i s e l y , w ed e f i n e dt h ei n t r a a n di n t e r - d e f i n i t i o n u s er e l a t i o n s h i pi nam p i p r o g r a ma n dp r o p o s e dt h el i v e - v a r i a b l ea n a l y s i sf o rm p ip r o g r a m s ( l a m pf o rs h o r t ) l a m po v e r c o m e st h ed e f e c t so fc o n v e n t i o n a ll i v e v a r i a b l ea n a l y s i sm e t h o d st h a tt h e y c a nn o td i s t i n g u i s ht h ed i f f e r e n tl i v e n e s so ft h es a m ev a r i a b l ei nd i f f e r e n tp r o c e s s e sa n d c a nr i o ta n a l y z et h ei n t e r - d e f i n i t i o n - u s er e l a t i o n s h i pi nam p ip r o g r a m l a m pi st h e b a s i ct e c h n o l o g yf o ro p t i m i z i n gt h ec h e c k p o i n ts i z ea n dc h e c k p o i n to v e r h e a d 2 w 色d i s c u s s e dt h eo p t i m i z a t i o nm e t h o do fd a t as a v i n gf o ra p p l i c a t i o n - l e v e l c h e c k p o i n t i n gt h o r o u g h l y f i r s t l y , w ea n a l y z e dt h ec o m p o s i t i o no fa 口ip r o g r a m s c o m p u t a t i o ns t a t ea n dd e c i d e dt oo p t i m i z ep r o c e s s e s c o m p u t a t i o ns t a t ew h i c hi st h e m a i n p a r t o fc h e c k p o i n td a t a s e c o n d l y , w e p r o p o s e dan e wa p p l i c a t i o n l e v e l c h e c k p o i n t i n gt e c h n o l o g yb a s e do nl a m ee x p e r i m e n tr e s u l t ss h o w e dt h a tt h e t e c h n o l o g yc a ne f f i c i e n t l yd e c r e a s et h ec h e c k p o i n ts i z ea n dc h e c k p o i n to v e r h e a d 3 w - el u c u b r a t e dt h ec o n s i s t e n c yi s s u eo fa p p l i c a t i o n 1 e v e l c h e c k p o i n t s w e p r o p o s e dan e wm e t h o dt om a i n t a i nt h ec o n s i s t e n c yo fa p p l i c a t i o n 1 e v e lc h e c k p o i n t sb y c o m p i l i n ga n a l y s i s t h em e h t o dd o e sn o tn e e dt ol o ga n ye a r l yo rl a t em e s s a g e sd u r i n g c h e c k p o i n t i n g i tf i n d so u tt h es a f ec h e c k p o i n t i n gr e g i o n si nam p ip r o g r a mb ys t a t i c a n a l y s i s n om e s s a g en e e d st ol o gw h e nac h e c k p o i t n i n go c c u r si nas a f ec h e c k p o i n t i n g r e g i o na n dt h er e c o v e r yp r o c e s si ss i m p l e e x p e r i m e n tr e s u l t ss h o w e dt h a tt h em e t h o di s s i m p l ea n de f f i c i e n t 4 w ed i s c u s s e dt h eo p t i m i z a t i o no ft o t a lo v e r h e a do fm u l t i p l ec h e c k p o i n t s w e p r o p o s e da no p t i m a lp l a c e m e n to fm u l t i p l ec h e c k p o i n t s b e c a u s et h em o s to v e r h e a do f a p p l i c a t i o n - l e v e lc h e c k p o i t n i n gi st h et i m e o fw r i t i n gc h e c k p o i n tf i l e s ，w ef i r s t l y 第i i i 页 国防科学技术大学研究生院博士学位论文 s i m p l i f i e dt h ei s s u eo fm i n i m i z i n gt h ec h e c k p o i n to v e r h e a dt ot h ei s s u eo fm i n i m z i n g t h ec h e c k p o i n ts i z e ，t h e na b s t r a c t e dt h ep r o b l e mo fo p t i m a lp l a c e m e n to fm u l t i p l e c h e c k p o i n t si n t oam a t h e m a t i cm o d e l w h i c hi ss i m i l a rt ot h e0 1i n t e g e rp r o g r a m m i n g m o d e la n dl a s t l yw eg a v et w oa l g o r i t h m so ft h em o d e l 5 w r ea d d r e s s e dt h ee a s y - t o u s ei s s u eo fa p p l i c a t i o n - l e v e lc h e c k p o i t n i n g w e d e s i g n e da n di m p l e m e n t e das o u c e t o s o u r c ep r e c o m p i l e ra l e c w h i c hc a nt r a n s l a t ea f o r t r a n 7 7 m p ip r o g r a mi n t oi t sf a u l t t o l e r a n tv e r s i o nw i t he f f i c i e n ta p p l i c a t i o n l e v e l c h e c k p o i n t i n gf e a t u r ei nas i m p l ew a y k e y w o r d s ：h i g h - p e r f o r m a n c ec o m p u t i n g ， f a u l t - t o l e r a n c e ， a p p l i c a t i o n l e v e lc h e c k p o i n t i n g ，l i v e - v a r i a b l ea n a l y s i sf o rm p ip r o g r a m s ， c o n s i s t e n ti s s u e ，l a mp ，a l e c 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表l li n t e l 芯片制造工艺的发展情况和未来预测3 表1 2 高性能计算机的可靠性【9 】5 表1 3 各种r o l l b a c k - r c o v e r y 技术的比较1 2 表1 4 系统级c h e c k p o i n t i n gv s 应用级c h e c k p o i n t i n g 1 4 表2 一l 图2 - 9 中各分析块的活跃变量集合。3 8 表3 - 1 测试用例。5 3 表4 - l 并行程序中m p i 调用的使用规律。6 5 表4 2 测试结果7 0 表5 1 测试用例的规模和执行时间8 5 表5 2 数据量比较( m b ) 8 5 第1 v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1i n t e l ，a m d 和p o w e r 处理器在t o p 5 0 0 中所占的份额2 图1 2t o p 5 0 0 中机器的处理器数目统计图2 图1 3i n t e l 处理器电源电压的变化趋势3 图1 4i n t e l 公司的系列微处理器的功耗密度变化【8 】。4 图1 5 系统可靠性的理论预测【9 】。5 图1 6 故障、错误和失效三者的关系7 图1 7a b f t 示例8 图1 8 容错方法分类9 图1 - 9r o l l b a c k r e c o v e r y 技术分类10 图1 1 0 大规模系统中的i o ( 箭头表示c h e c k p o i n t 数据的流向) 9 1 1 4 图1 1 1 应用级c h e c k p o i n t i n g 技术的四个基本问题1 8 图1 1 2 论文章节组织图2 3 图2 1 对等模式的m p i 程序实例p e e rt op e e r 2 7 图2 2p e e rt op e e r 的执行流程2 8 图2 3 主从模式的m p i 程序实例m a s t e rs l a v e 2 8 图2 4m a s t e rs l a v e 的执行流程：2 9 图2 5 计算兀的f o r t r a n m p i 程序3 0 图2 6 点对点通信导致的进程间定值引用关系3 3 图2 7 集合通信导致的进程间定值引用关系3 3 图2 8 图2 5 中从第1 3 行到第2 0 行之间的流图3 5 图2 - 9m p i 并行程序活跃变量分析示例3 6 图2 1 0 活跃变量分析的数据流方程3 7 图3 1 活跃变量的数据结构4 0 图3 2 过程内活跃变量分析算法4 l 图3 3c a l l e ra n dc a l l e e 过程41 图3 4 一般算法的基本思想4 4 图3 5 选择合适的c h e c k p o i n t 位置的一般算法4 4 图3 - 6 简化算法示例4 5 图3 7 选择合适的c h e c k p o i n t 位置的简化算法4 6 图3 8c h e c k p o i n t i n g 发生在主过程中4 7 图3 - 9c h e c k p o i n t i n g 发生在子过程中4 8 第v 页 国防科学技术大学研究生院博士学位论文 图3 1 0 保存活跃变量的方法4 9 图3 1 1 恢复活跃变量的方法4 9 图3 1 2 跟踪第一类m p i 调用5 1 图3 1 3a l e c 的结构5 2 图3 1 4c h e c k p o i n t 数据量( g b ) 5 4 图3 15c h e c k p o i n t 和r e s t a r t 时间( s ) 5 5 图4 1 消息分类【8 l 】5 7 图4 2c h a n d y l a m p o r t 协议( 图a 中箭头表示信道，图b 中虚线箭头表示m a r k e r 消息) 5 9 图4 3 几类全局c h e c k p o i n t 的定义6 1 图4 4 通信线区6 3 图4 5 通信线延伸6 4 图4 6n p bc g 中的一个包含通信语句的循环6 6 图4 7 跨过程的m p i c f g 。6 7 图4 8 不明确通信区的上下边界6 8 图4 - 9 增加了安全区识别模块之后的a l e c 的系统结构6 9 图4 1 0a l c 数据量与s l c 数据量的比值7 0 图5 1cs t r u c t 的数据结构7 4 图5 2c h e c k p o i n t 间隔与程序的期望执行时间n 9 7 1 7 5 图5 3 模型( 5 1 ) 的求解算法7 7 图5 4 嵌套循环的层次7 8 图5 5 循环中的c h e c k p o i n t 位置的简化设置7 9 图5 6 在图5 4 中插入c h e c k p o i n t i n g 代码8 0 图5 7 第一个c h e c k p o i n t 在循环中的位置8 l 图5 8 适用于一个循环结构的简化算法8 3 图5 - 9 多个m a i n l o o p 的情况8 3 图5 1 0 适用于多个循环结构的简化算法8 3 图5 1 1 加上多c h e c k p o i n t 优化设置模块之后的a l e c 的结构8 4 图5 1 2a l c l 组相对于a l c 2 组数据量的百分比值8 6 图6 1a l e c 预编译器的完整结构8 8 图6 2l i n et a b l e 数据结构的主要内容8 9 图6 3s y s t e mt a b l e 数据结构的主要内容。8 9 图6 4b l o c kt a b l e 数据结构的主要内容9 0 图6 5m a t c h i n g 的数据结构91entry 第v l 页 国防科学技术大学研究生院博士学位论文 图6 6 活跃变量集合的数据结构9 2 图6 7i f 结构的条件表达式隐式的包含m y i d 9 2 图6 8 一个简单的f o r t r a n m p i 程序9 3 图6 9 经过a l e c 处理之后的程序。9 4 图6 1 0a l c t o o l 的结构框图9 5 图6 11a l c t o o l 效果图9 6 第v i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 廑周堡曼垒曼曼墼乜q i 堕! i 翌g 技盔鲍塑窥生塞塑 学位论文作者签名 赵孳聋 日期：加9 萝年7 月z 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期：芦9 宫 日期：抛8 年? 月z 日 1 年9 月1 日 l 国防科学技术大学研究生院博士学位论文 1 1 1 高性能计算的普及应用 第一章绪论 1 1 课题背景 高性能计算是解决国防建设和经济发展中重大应用问题的基础性、前瞻性与 战略性关键技术，广泛应用于核武器研究、生物信息技术、医疗和新药研究、计 算化学、g i s 、c a e 、气象预报、工业设计以及环境保护等与国家安全和国民经济 密切相关的各个领域。 随着竞争的加剧和应用的普及，高性能计算技术已是“旧时王谢堂前燕，飞 入寻常百姓家”，从少数军工部门和国家实验室普遍进入到工厂企业和大专院校。 科学研究、工业制造和商业活动中越来越多地使用高性能计算机来解决实际问题。 日本政府于2 0 0 7 年启动了一项超长期天气预报计划。借助于日本海洋科学技术中 心横浜研究所的“地球模拟器( e a r t hs i m u l a t o r ) ”对未来3 0 年内可能发生的台风、 暴风雪、干旱以及其它恶劣天气进行预测。计算结果可以帮助政府提前采取应对 灾害天气的相应措施，减小经济损失。在工业生产中，美国g m 、g e 、日本n i s s a n 等著名大公司拥有总计算能力超过l o 万亿次的高性能计算机用于新产品的研发。 美国b o e i n g 公司在上世纪9 0 年代就实现了无纸化设计，b o e i n g 公司己宣布利用 高性能计算机对航空发动机进行全物理过程的模拟仿真。高性能计算机也广泛应 用于商业领域，2 0 0 8 年6 月的t o p 5 0 0 中有7 6 台机器用于金融领域，总计算能力 达到8 8 4 万亿浏1 1 。g o o g l e 公司一直争取在o 5 秒时间内处理完用户请求【2 j 。为了 实现这一目标，g o o g l e 公司开发了一个大规模的集群系统g o o g l ec l u s t e r 。在2 0 0 3 年初，g o o g l ec l u s t e r 就拥有了超过3 0 ，0 0 0 个处理器，并且仍在不断扩展规模以提 高性能3 ，4 】。 近年来，随着高性能计算技术的普遍应用，高性能计算机的发展呈现出两大 趋势：一是广泛使用通用的、低成本的商用器件( c o m m e r i c a lo f f - t h e s h e l f , c o t s ) ， 以缩短研制周期和降低研制成本；二是系统规模持续增长，以满足科研和生产活 动对更高计算能力的不断追求。图1 1 显示了近5 年来i n t e l 、a m d 和p o w e r 三大 主流商用处理器在t o p 5 0 0 中所占的比重，可以看出这三大厂商基本上垄断了高性 能计算机的处理器市场。图1 2 显示了近5 年来t o p 5 0 0 中机器的处理器数目统 计情况，由此可见高性能计算机包含的处理器数在不断增加。 低可靠的c o t s 器件的广泛使用降低了高性能计算机各结点的可靠性，也降 低了系统的整体可靠性；而系统规模的大幅增长则会显著降低系统的平均故障间 第1 页 国防科学技术大学研究生院博士学位论文 隔时问( m e a n t i m e b e t w e e nf a i l u r e s ，m t b f ) 。 2 0 0 4 0 62 0 0 5 0 62 0 0 6 0 6 2 0 0 7 0 62 0 0 8 0 0 图l - l i n t e l ，a m d 和p o w e r 处理器在t o p 5 0 0 中所占的份额 图1 - 2 t o p s 0 0 中机器的处理器数目统计闰 1 12 高性能计算面临的可靠性挑战 可靠性是高性能计算领域的经典问题之一。随着高性能计算在应用领域的逐 渐普及，提高可靠性的需求越来越迫切；而高性能计算机所呈现出的发展趋势则 使得可靠性问题面临着更加严峻的挑战。 i 1 0 1c o t s 器件的工艺技术发展对可靠性的影响 c o t s 器件具有性价比高、市场规模大、兼容性好等优点，被广泛用于制造高 性能计算机。c o t s 器件都出自于实力雄厚的大型跨国公司。由于激烈的市场竞争， c o t s 器件的工艺技术一直按照摩尔定律飞速发展。表1 - l 显示了近l o 年来i n 把l 公刊芯片制造工艺的发展情况和未来预测。 第2 页 国防科学技术大学研究生院博士学位论文 表1 1i n t e l 芯片制造工艺的发展情况和未来预测 实际预测 工艺名称 p 8 5 8p x 6 0p 1 2 6 2p 1 2 6 4p 1 2 6 6p 1 2 6 8p 1 2 7 0 首次采用时间 1 9 9 92 0 0 12 0 0 4 2 0 0 52 0 0 72 0 0 92 0 l l2 0 1 3 线宽 1 8 0 n m 1 3 0 n m 9 0 n m6 5 n m4 5 n m3 2 n m2 2 n m1 6 n m 门长度 1 3 0 n m7 0 n m5 0 n m3 0 n m 2 0 n1 6 n m 状态实际生产使用开发中研究中 表1 1 清晰地显示了c o t s 器件的制造工艺朝着晶体管尺寸越来越小的方向 不断发展的事实以及进一步发展的趋势。而图1 3 所显示的i n t e l 处理器电源电压 的变化趋势则表明：在c o t s 器件的晶体管尺寸越来越小发展的同时，其工作电 压也不断降低。 v q 昱 百 2 j 们 ：枷倍f 降 x 。 2 5 v 弋 弋：之立一 、o 7 v 1 、o 6 v l 2 0 0 0 y e a r 图1 3i n t e l 处理器电源电压的变化趋势 当晶体管尺寸和工作电压都越来越小时，c o t s 器件会更容易受到电子噪声的 影响而发生故障。半导体电路是通过保持或者释放一定的电量来表示逻辑上的1 和o 。但是由于各种电子噪声的影响，比如不稳定的电源、闪电和宇宙射线等p j ， 可能会使半导体电路中的p n 结产生瞬时充放电，使其中存储的信息发生逻辑上的 翻转，例如原先存储的1 翻转成0 。在一定条件下，半导体p n 结点逻辑状态是否 会因电子噪声的影响而翻转与其工作电压和晶体管尺寸有关。工作电压低，保持 逻辑状态的电量就少，在相同的电子噪声环境下逻辑状态翻转的可能性就更大； 晶体管尺寸越小，逻辑状态发生翻转所需要的电量也就越少，那么相同的环境下 逻辑状态翻转的可能性也就更大。文献 6 】中预测在采用小于1 0 0 n m 的技术以后， 第3 页 国防科学技术大学研究生院博士学位论文 翻转逻辑状态所需的临界电量大约只需要几个飞库( f c ) ，仅合几万个电子。因而 半导体电路对宇宙射线的敏感程度急剧增加，一些具有较低能量的宇宙射线也能 够引发半导体电路逻辑状态的翻转。当集成电路的尺寸接近量子物理所描述的极 限时，单个电子都会对电子电路产生干扰。 另一个影响c o t s 器件可靠性的因素是功耗。图1 4 显示了i n t e l 公司的系列 微处理器的功耗密度变化。从图中可以看出，微处理器的功耗密度在不断增加， 大约每1 8 2 4 月增加一倍，这称为功耗的摩尔定律1 7 】。随着制造工艺的改进，内存 容量越来越大，速度越来越快。相应地，功耗也越来越高，现在主流的d d r 2 和 f b d 内存均已达到1 0 w 量级。由于c p u 和内存频率不断提高，这就要求和它们 配合的芯片组、总线和外围设备都需要工作在更高的频率下才能充分发挥其性能， 而更高的频率意味着更高的功耗。功耗增加会影响到器件可靠性，并缩短器件寿 命，从而影响系统的可靠性。在室温2 1o c 基础上，平均每增加1 0o c ，可靠性就 会降低5 0 。 n ) 奄 篁 母 ； 图1 4i n t e l 公司的系列微处理器的功耗密度变化【8 】 1 1 2 2 系统规模扩大对可靠性的影响 根据2 0 0 8 年6 月公布的t o p 5 0 0 的统计数据，世界上最快的前1 0 台高性能计 算机的处理器数目全都超过1 0 ，0 0 0 ，最少的也有1 3 ，7 2 8 ；而b l u eg e n e l 所拥有的 处理器更是高达2 1 2 ，9 9 2 个【l 】。从可靠性理论的角度看，如果单个部件的可靠性是 固定的，那么在没有额外容错措施的情况下，构成系统的部件越多系统的可靠性 就会越低。 假设结点故障率遵循指数分布，r 是单结点的可靠度，系统中任意一个结点发 生故障都会导致整个系统发生故障。这种情况下，一个n 结点系统的平均无故障 第4 页 国防科学技术大学研究生院博士学位论文 时间( m e a i lt i m et of a i l u r e ，m t t f ) 近似为百j 1 眄。 s i n g l e 出so n e - h o , , r e l i a b l i t y 一0 9 9 9 9 一0 9 9 9 ) 9 一0 0 9 9 9 9 9 鼻 。| ；| 1 ；j 太、太 1人 7 - 叶、i t k 、 图1 - 5 系统可靠性的理论预测f 9 1 图1 5 显示了根据可靠性理论预测的系统可靠性与结点数目的关系。从中可 以看出，随着系统规模的扩大，m t t f 会迅速减小。 商业器件一般有1 到3 年的质量保修期。我们把这个周期作为m t t f ，并且假 定单结点的可靠度r 在0 9 9 9 9 到0 9 9 9 9 9 之间取值。当系统规模达到1 0 ，0 0 0 结点 时，如果没有额外的增加系统可靠性的措施，m t t f 会降低到不足1 0 小时。即使 系统由可靠度为0 9 9 9 9 9 9 ( 换算过来就是m t t f 为1 1 4 年) 的极端可靠的部件组 成，像b l u eg e n e l 这样规模庞大的系统的m t t f 也会小于1 0 小时一j 。 来自高性能计算机的实际运行数据也表明：即便单个器件的可靠性很高，由 数干甚至上万个器件组成的系统的可靠性也会很低。如i n t e l 公司为美国能源部研 制的a s c ir e d 1 0 】系统，共有9 1 5 2 个处理器。虽然单个处理器的m t b f 都大于1 0 年，但全系统的m t b f 仅有1 0 小时( 尚不含偶发性故障) 。表1 2 列出了部分高 性能计算机的可靠性数据。 表1 - 2 高性能计算机的可靠性9 1 系统( 所在地)i 处理器数目 i 可靠性 第5 页 船 的 o j n o s k 卜_ l 乏 国防科学技术大学研究生院博士学位论文 m t b l l ：6 5 小时 a s c iq ( l a n l )8 1 9 2 ( 2 0 0 2 年6 月- 2 0 0 3 年6 月) a s c i 、h i t em t b f ：5 1 i , 时( 2 0 0 1 年1 月) 8 1 9 2 ( l l n l ) 4 0 d 时( 2 0 0 3 年2 月) m t b i ：9 7 d x 时 l e m i e u x ( p s c )3 0 1 6 ( 2 0 0 2 年4 月- 2 0 0 3 年2 月 m t b i 1 4 天 s e a b o r g ( n e r s c ) 6 6 5 6m t t r ：3 3 d x 时 ( 2 0 0 2 年8 月2 0 0 3 年7 月) 每天2 0 台机器蕈启 g o o g l e 1 5 0 0 0 每年更换2 - 3 的机器 综上所述，高性能计算面临着严峻的可靠性挑战。为了能够执行完成，运行 于高性能计算机上的并行程序必须具有容错能力。因此，研究面向高性能计算的 容错技术具有重要的现实意义。 1 2 相关研究工作 我们对高性能计算领域的容错技术进行了大量的调研工作，这些相关领域的 研究和进展对本课题的研究具有很大的启发和指导作用。下面将对相关领域的研 究工作进行总结，并通过对现有研究工作的分析突出本文工作的创新性。 1 2 1 容错的基本概念和常用方法 1 2 1 1 容错的基本概念 容错是系统的一种能力在发生故障时仍能完成预定的功能。1 9 6 7 年， a v i z i e n i s 在文献【1 l 】中第一次提出了容错的概念：“w es a y t h a tas y s t e mi s f a u l t t o l e r a n ti fi t sp r o g r a m sc a nb ep r o p e r l ye x e c u t e dd e s p i t et h eo c c u r r e n c eo fl o g i c f a u l t s “如果在发生逻辑故障的情况下，系统中的程序仍然能够正确地执行， 那么我们就称这个系统是可容错的。” 通常有三个描述故障的术语：故障( f a u l t ) 、错误( e r r o r ) 和失效( f a i l u r e ) 。 这三个概念的关系如图1 - 6 所示。故障发生在物理级，指硬件或软件组件在物理 上的缺点、不完整或缺陷。错误发生在计算级，指的是计算结果不正确或不精确， 1 m t b i ：m e 姐t i m eb e t 、v e 朗i n t e r r l l j p t s ，m t b i = _ 曼堕兰要竺璺! 一 n u m b e r0 ti n t e r r u p t s 第6 页 国防科学技术大学研究生院博士学位论文 它是故障的后果。失效发生在系统级，指系统在一个特定时间段内提供的服务与 其规定不相符，它是错误的后果【1 2 1 。比如，一个发电厂里用一套计算机控制系统 探测各设备的温度、压力和其它物理特性。如果报告主涡轮转速的传感器坏了( 故 障发生) ，这个故障导致系统给该涡轮发送超出其承受能力的蒸汽( 导致错误) ， 使得涡轮超速旋转。为了防止涡轮损坏，机械安全系统关掉涡轮，整个系统不能 继续发电( 系统失效) 1 1 2 1 。 图1 - 6 故障、错误和失效三者的关系 故障的来源很多，可能是设计、生产、装配过程中的缺陷，也可能是使用过 程中外部因素的影响。事先检测出所有设计和生产过程中的故障是极其困难的， 有些故障只在特定条件下才会引起错误。例如，1 9 9 4 年，人们发现i n t e lp e n t i u mi 微处理器在计算特定浮点除法时得到不正确的结果。比如5 5 0 5 0 0 1 除以2 9 4 9 1 l 得 到1 8 6 6 6 0 0 0 9 3 而不是1 8 6 6 6 6 5 1 9 7 。