（计算机科学与技术专业论文）容错并行算法的研究与分析.pdf

国防科学技术大学研究生院博士学位论文 摘要 随着系统规模的增加，大规模并行计算机的平均故障间隔时间远低于许多大 规模科学应用的运行时间，因此大规模科学应用必须能够容忍硬件错误。传统的 回滚恢复协议是目前大规模系统中常用的容错技术，在恢复时失效进程上的计算 全部在一个处理器上重算。这是对计算资源的浪费，也使得恢复时间不可能小于 前一个检查点和故障发生时刻之间的时间间隔。 为了缩短故障恢复时间，本文提出了一种新的容错方法：容错并行算法。文 章从容错并行算法的理论基础、概念、设计方法及支撑工具等几个方法对容错并 行算法进行了深入的研究，并对容错并行算法的性能进行了分析和测试。本文所 做的创新工作主要体现在以下几点： 1 、给出了并行计算在系统出现故障的情况下的可靠性定义，并基于任务依赖 图给出了并行计算可靠性的定量分析方法；基于此分析方法，分析和比较了时间 冗余和空间冗余的容错技术对并行计算可靠性的影响。 2 、为了缩短故障恢复时间，有效提高并行计算的可靠性，提出了一种新的容 错方法：容错并行算法。容错并行算法执行时在数据保存段保存计算的中间状态 以保证故障时正确的复算；发生故障时未发生故障的处理器通过在线的方式感知 故障处理机的故障，并自动通过并行复算恢复故障处理器上的负载。容错并行算 法充分发挥无故障进程的计算能力，加速故障恢复过程，缩短了故障恢复时间， 使得恢复时间可以远低于c h e c k p o i n t 和发生故障时刻之间的时间间隔。 3 、容错并行算法设计的基本思想是以程序段为基础，添加数据保存段，故障 检测段和复算段构成相应的容错程序段。本文系统地讨论了容错并行算法的设计 方法，提出了面向容错并行算法的程序段的划分方法以及分割和合并原则；利用 面向并行程序的定值引用关系确定状态保存段中所需保存的数据；给出了两种复 算段中并行复算代码的设计方法：基于循环并行化以及基于模板的方法。同时， 还针对矩阵l u 分解、快速傅里叶变换以及桶排序等三类典型的并行应用，设计并 实现了其相应的容错并行算法。 4 、为了降低容错并行算法给用户带来的编程负担，本文实现了一个面向m p i 程序的容错并行算法设计的支撑工具g i f t 。g i f t 通过编译指导的方法实现程序段 的划分；利用面向并行程序的控制流分析以及数据流分析方法自动确定保存的数 据，实现了容错并行算法数据保存的低开销以及数据保存段的自动设计：通过编 译指导的方法，实现了基于循环并行化以及基于模板的并行复算代码生成的自动 化。 5 、容错并行算法的性能分析与实验。首先，给出了故障情况下的容错并行算 第i 页 国防科学技术大学研究生院博士学位论文 法的性能度量，建立了考虑系统故障情况下的性能模型来预测容错并行算法的完 成时间，并以此为基础评估了程序段的运行时间、数据保存开销、故障率以及并 行复算加速比等系统参数对容错并行算法性能的影响；随后，针对科学计算中的6 个典型测试用例在一个1 0 2 4 个处理器的集群系统上对容错并行算法的性能进行了 测试并与系统级c h e c k p o i n f i n g 方法进行了对比，这6 个典型测试用例包括矩阵乘 程序和5 个n p b 核心测试用例( e p 、i s 、c g 、m g 和f t ) 。结果表明与c h e c k p o i n t i n g 方法相比，容错并行算法有性能上的优势。 关键词：高性能计算，容错，并行计算的可靠性，容错并行算法，并行复算， g i f t 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t a st h es i z eo f l a r g e - s c a l ec o m p u t e rs y s t e m s i n c r e a s e s ，t h e i r m e a n - t i m e b e t w e e n - f a i l u r e sa r eb e c o m i n gs i g n i f i c a n t l ys h o r t e rt h a nt h ee x e c u t i o nt i m e o fm a n yc u r r e n ts c i e n t i f i c a p p l i c a t i o n s t oc o m p l e t et h e e x e c u t i o no fs c i e n t i f i c a p p l i c a t i o n s ，t h e ym u s t t o l e r a t eh a r d w a r ef a i l u r e s c o n v e n t i o n a l r o l l b a c k r e c o v e r y p r o t o c o l sr e d ot h ec o m p u t a t i o no ft h ec r a s h e dp r o c e s ss i n c et h el a s tc h e c k p o i n to na s i n g l ep r o c e s s o la sar e s u l t ，t h er e c o v e r yt i m eo fa l lp r o t o c o l si sn ol e s st h a nt h et i m e b e t w e e nt h el a s tc h e c k p o i n ta n dt h ec r a s h i nt h i st h e s i sw ep r o p o s ean e wa p p l i c a t i o n l e v e lf a u l t t o l e r a n t a p p r o a c hf o r p a r a l l e la p p l i c a t i o n sc a l l e df a u l t t o l e r a n tp a r a l l e la l g o r i t h m ( f t p a ) w h i c hp r o v i d e s f a s ts e l fr e c o v e r y o u rs t u d yf o c u s e so nt h et h et h e o r e t i c a lf o u n d a t i o no ff t p a ，t h e c o n c e p to ff t p a ，t h ed e s i g nm e t h o d o l o g yo ff f p aa n dat o o ls u p p o r t i n gf o rd e g i s n i n g f t p a w ea l s oa n a l y z ea n de v a l u a t et h ep e r f o r m a n c eo ff t p a p r i m a r yi n n o v a t i v e w o r ki nt h i st h e s i sc a nb es u m m a r i z e da sf o l l o w i n g ： 1 t h ed e f i n i t i o nf o rt h er e l i a b i l i t yo fp a r a l l e lr e c o m p u t i n gu n d e rf a i l u r ei sg i v e n a l s ow ep r e s e n tt h eq u a n t i t a t i v ea n a l y s i sa p p r o a c hf o r t h er e l i a b i l i t yo fp a r a l l e l r e c o m p u t i n gb a s e do nt a s kd e p e n d e n c eg r a p h a c c o r d i n gt ot h ea n a l y s i sa p p r o a c h ，w e a n a l y z ea n dc o m p a r et h ee f f e c t so ft i m er e d u n d a n c ya n ds p a c er e d u n d a n c yo nt h e r e l i a b i l i t yo fp a r a l l e lr e c o m p u t i n g 2 t os p e e du pt h er e c o v e r yp r o c e d u r ea n di m p r o v et h er e l i a b i l i t yo fp a r a l l e l c o m p u t i n g ，w ep r o p o s e al l e w a p p l i c a t i o n l e v e l f a u l t - t o l e r a n t a p p r o a c h c a l l e d f a u l t t o l e r a n tp a r a l l e la l g o r i t h m ( f t p a ) f i p ai sap a r a l l e la l g o r i t h mw h i c hp r o v i d e s f a s ts e l f - r e c o v e r y f t p as a v e sd a t aa td a t a s a v i n gp o i n t sf o rc o r r e c tr e c o v e r yd u r i n gi t s e x e c u t i o n w h e nap r o c e s sf a i l s ，t h ef a i l u r ew i l lb ed e t e c t e db ya l ls u r v i v i n gp r o c e s s e s ， w h i c hw i l lr e e x e c u t et h ew o r kl o s to nt h ef a i l e d p r o c e s si np a r a l l e l p a r a l l e l r e c o m p u t i n gs p e e d su pt h er e c o v e r yp r o c e d u r e ，m a k i n gt h er e c o v e r yt i m ec o n s i d e r a b l y l e s st h a nt h et i m eb e t w e e nt h el a s tc h e c k p o i n ta n dt h ec r a s h 3 t h ed e s i g no ff t p aa l l o w st h em a n i p u l a t i o no fe a c hp r o g r a ms e c t i o ni n t oa f a u l t - t o l e r a n tp r o g r a ms e c t i o nw i t ht h ei n s e r t i o no fad a t as a v i n gs e c t i o n af a i l u r e d e t e c t i o ns e c t i o na n dar e c o v e r ys e c t i o n i nt h i sp a p e r , t h ed e s i g nm e t h o d o l o g yo ff r p a i sd i s c u s s e dc o m p r e h e n s i v e l y t h ep r o g r a ms e c t i o n sf i n a l l yu s e db yf i p aa r ep r o d u c e d b yt h ea p p r o a c hf o rp a r t i t i o n i n gt h eo r i g i n a lp r o g r a mo rb yt h ea p p r o a c hf o rs p l i t t i n g a n dc o m b i n i n gt h ep a r t i t i o n e dp r o g r a ms e c t i o n s t h ed a t ar e q u i r e dt ob es a v e di nad a t a s a v i n gs e c t i o ni sd e t e r m i n e db yt h ed e f i n i t i o nu s er e l a t i o n s h i pf o rp a r a l l e lp r o g r a m s f o r d e s i g n i n gar e c o v e r ys e c t i o n ，t w om e t h o d sa r ep r e s e n t e d ：a u t o m a t i cp a r a l l e l i z a t i o na n d t h et e m p l a t ea p p r o a c h w ea l s od e s i g na n di m p l e m e n tt h ef t p av e r s i o np r o g r a m sf o r 第血页 国防科学技术大学研究生院博士学位论文 t h r e et y p i c a lp a r a l l e la p p l i c a t i o n sw h i c ha r em a t r i xl ud e c o m p o s i t i o n ，f a s tf o u r i e r t r a n s f c i r ma n db u c k e ts o r t 4 i no r d e rt oe a s ef r p ai m p l e m e n t a t i o n w ed e v e l o pg i f t , as o u r c e t o s o u r c e p r e c o m p i l e rt o o lt ot r a n s f o r ma nm p i f o r t r a no rm p i cp r o g r a mw i t hu s e ri n s t r u m e n t e d c o m p i l e rd i r e c t i v e si n t oi t sf t p av e r s i o n g i f tr e q u i r e st h a tt h eu s e ru s ec o m p i l e r d i r e c t i v e st oc h o o s ep r o g r a ms e c t i o n sa n df i g u r eo u tt h ev a r i a b l e sn e c e s s a r yt ob es a v e d i nad a t a s a v i n gs e c t i o nt h r o u g hc o n t r 0 1 f l o wa n a l y s i sa n dd a t a f l o wa n a l y s i s g i f t a u t o m a t e si m p l e m e n t i n gr e c o v e r ys e c t i o n sb ym e a n so fc o m p i l e rd i r e c t i v e s 5 t oa n a l y z ea n de v a l u a t et h ep e r f o r m a n c eo ff t p a f i r s t l y , t h ep e r f o r m a n c e m e t r i c sf o rp a r a l l e ls y s t e m su n d e rf a i l u r ea r ep r e s e n t e d w ea l s og i v eap e r f o r m a n c e m o d e lt op r e d i c tt h ef r p ac o m p l e t i o nt i m eu n d e rf a i l u r e b a s e do nt h ep e r f o r m a c e m o d e l ，w ee v a l u a t et h ee f f e c t so ft h ep r o g r a ms e c t i o ns i z e ，t h ed a t a s a v i n go v e r h e a da n d f a i l u r er a t eo nt h ep e r f o r m a c eo ff t p a s e c o n d l y , w ee v a l u a t et h ep e r f o r m a n c eo ff t p a w i t hp a r a l l e lm a t r i xm u l t i p l i c a t i o na n df i v ek e r n e l so fn a sp a r a l l e lb e n c h m a r k so na c l u s t e rs y s t e mw i t h10 2 4c p u s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo f f r p ai sb e t t e rt h a nt h ep e r f o r m a n c eo ft h et r a d i t i o n a lc h e c k p o i n t i n ga p p r o a c h 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 ，r e l i a b i l i t yf o r p a r a l l e lc o m p u t i n g ，f a u l t t o l e r a n tp a r a l l e la l g o r i t h m ，p a r a l l e lr e c o m p u t i n g ， g i f t 第i v 页 国防科学技术大学研究生院博士学位论文 图表目录 图1 1t o p 5 0 0 中所有系统的平均处理器数目。2 图1 2 不同处理器规模下系统的m t b f 。2 图1 3 故障，错误和失效4 图1 - 4c h e c k p o i n t i n g 技7 r 8 图1 5 悲观日志1 0 图1 6 乐观日志。l o 图1 7 因果日志1 1 图1 8 矩阵乘的a b f t 算法1 4 图2 1 一个任务依赖图的例子1 8 图2 2 入度为n 的任务结点2 2 图2 3 存在相关的任务结点2 3 图2 4 基于时间冗余的容错结点2 5 图2 5 包含基于空间冗余的容错结点的任务依赖图2 7 图2 - 6 基于空间冗余的容错结点的工作过程2 7 图3 1 矩阵乘的例子3 0 图3 2 矩阵乘算法的c h e c k p o i n t i n g 工作过程j 3 1 图3 3 容错矩阵乘算法的工作过程3 2 图3 - 4 容错程序段结构图3 4 图3 5 容错方法的工作过程3 5 图3 - 6 计算的f o r t r a n m p i 程序的程序段。3 6 图3 7 故障检测段3 7 图3 8 定值一引用关系。3 8 图3 - 9 保存变量代码4 0 图3 1 0 优化后的保存代码。4 l 图3 1 l 变量y 的引用点u i 与其通信定值点位于不同程序段。4 l 图3 1 2 变量y 的引用点u j 与其通信定值点位于同一程序段4 2 图3 13 基于循环并行化方法设计的程序段s 3 的复算代码4 2 图3 1 4 计算兀程序运行时的迭代划分4 4 图3 1 5 基于模板方法设计的程序段s 3 的复算代码4 4 图3 1 6b l o c k 的映射关系4 5 图3 1 7c y c l i c 的映射关系4 6 第页 国防科学技术大学研究生院博士学位论文 图3 1 8 ( c y c l i c ，b l o c k ) 的映射关系4 6 图3 1 9 ( b l o c k ，c y c l i c ) 的映射关系4 7 图3 2 0 矩阵乘程序4 8 图3 ，2 l 程序切片4 9 图3 2 2 基于模板的并行复算代码生成方法。4 9 图4 1l u 分解算法的核心代码5 5 图4 2 容错l u 分解算法的并行复算代码5 6 图4 3l u 分解算法及其容错并行算法工作过程5 7 图4 4n = 8 时的f f t 蝶形计算图5 8 图4 5 一维划分时n p bf t 中快速傅里叶变换的计算代码5 9 图4 6 容错n p bf t 算法的数据保存段代码6 0 图4 7 容错n p bf t 算法的并行复算代码6 0 图4 8n p bi s 中的桶排序计算代码6 2 图4 9 容错n p bi s 算法的的数据保存段代码6 4 图4 1 0 容错n p bi s 算法的并行复算代码6 4 图5 1 容错并行算法设计支撑工具框架图6 7 图5 2m p i 程序片段7 0 图5 3 图5 2 中程序的控制流图7 1 图5 _ 4 到达一定值分析的数据流方程7 2 图5 5 恢复代码生成7 4 图5 6d o 编译指导语句格式7 4 图5 7n p bi s 中的一个循环结构7 5 图5 。8 基于模板的并行复算代码生成算法7 7 图5 9 两种t b b 和t b e 指导命令的错误使用7 8 图5 1 0t b b 和t b e 指导命令嵌套使用的错误7 8 图5 儿程序段s 3 中d o 循环全模板的编译指导语句7 9 图5 1 2 确定模板映射变量的实现算法。8 0 图5 1 3 过程内程序切片算法8 2 图5 1 4 过程问程序切片算法8 3 图5 1 5 通信代码生成优化方法。8 5 图6 一l 在不同的程序段运行时间和并行复算加速比的情况下的性能度量9 0 图6 2 在不同的数据保存开销和并行复算加速比的情况下的性能度量9 1 图6 3 在不同的故障率和程序段运行时间的情况下的性能度量9 2 图6 4 在不同的故障率和并行复算加速比的情况下的性能度量9 3 第v 页 国防科学技术大学研究生院博士学位论文 表6 1 评测容错并行算法性能的测试程序9 3 图6 5m m 的性能评估图。9 6 图6 - 6e p 的性能评估图9 6 图6 7i s 的性能评估图9 8 图6 8c g 的性能评估图9 9 图6 - 9m g 的性能评估图1 0 0 图6 1 0f t 的性能评估图1 0 1 第v i 页 独创性声明 本人声明所里交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：窒垡羞i i 篡洼鲍盈壅生佥堑 学位论文作者签名：牡交墼 日期： 勘o g 年c i 月l 上日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印缩印或扫描等复制手段保存，汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：查篮羞踅笺鎏煎盈容量佥堑 学位论文作者签名：血云孽 日期： 如g 年0 1 月) 1 日 作者指导教师签名： 日期：年月 日 国防科学技术大学研究生院博士学位论文 第一章绪论弟一早殖比 1 1 大规模系统的可靠性问题 传统的大规模系统一直以追求高性能为目标，当前的大规模系统排g ( t o p s 0 0 ) 仍以峰值性能作为评价系统的主要参数i 。但随着处理器制造工艺的发展，以及系 统规模的不断增加，可靠性己成为大规模系统发展的重大挑战问题之一，新一代 高产出率大规模计算机系统的研究计划( h i g hp r o d u c t i v i t yc o m p u t e rs y s t e m s ，h p c s ) 已将可靠性列为关键目标之一【2 1 。 1 1 1 单芯片处理器制造工艺不断发展 随着微处理器芯片逐步采用纳米级制造工艺，在微处理器性能得到大幅提高 的同时，由于集成电路特征尺寸的减小、电源电压的降低和频率的升高，使得处 理器对于串扰、电压扰动、电磁干扰以及辐射等各种噪声干扰变得很敏感，并可 能引发错误的操作，导致了微处理器的故障发生率不断攀升，微处理器的可靠性 不断降低。 另一方面，微处理器的功耗密度在不断增加，功耗密度每1 8 2 4 月增加一倍， 这称为功耗的摩尔定律1 3 。功耗密度的增加使得热量对系统可靠性的影响加剧；改 善的工艺往往采用更低的供电电压，这会导致切换电流的噪声影响恶化。这些这 些因素都会影响系统部件的可靠性，从而进一步影响了系统的可靠性。系统部件 的温度在不断上升，一般来说，在2 1o c 基础上，温度每升高1 0 0 c ，系统的失效率 就会提高一倍1 4 1 。 1 1 2 大规模系统的规模不断增加 大规模科学计算一直是推动高性能计算机迅速发展的主要动力。今天的科学 家更加依赖于高性能计算机处理空前庞大的数据集以及实现空前复杂的模拟仿 真。直到目前为止，提高计算机性能的主要手段仍是增加处理器数目，图1 1 给出 了从2 0 0 0 年1 1 月到2 0 0 7 年1 1 月t o p 5 0 0 中所有系统的处理器数目平均值( 均是 每年1 1 月份的数据) ，由此可见，高性能计算机的规模在迅速扩大。当前世界上 规模最大的计算机mb l u eg e n e l 所拥有的处理器数目己高达2 1 2 。9 9 2 个i i l 。 1 1 3 大规模系统的可靠性受到挑战 单处理器可靠性的降低以及系统规模的急剧扩大导致系统的平均故障时间间 第1 页 国防科学技术大学研究生院博士学位论文 隔( m 凶t i m eb e t w e e nf a i l u r e s ，m t b f ) 大幅降低。图1 - 2 给出了在单结点可靠度 r = o 9 9 9 9i 拘情况下，根据图1 - 1 中的处理器数目和计算公式脚= f 得到的系 统m t b f 时间。由图1 - 2 中可以看出，系统的m t b f 随系统规模的增大，降低幅 度也很大，在处理器规模为3 2 9 6 时，m t b f 只有3 6 小时左右。 3 5 0 0 m 3 0 0 0 u u 鼎2 5 0 0 誉2 0 0 0 未1 5 0 0 霎1 0 0 0 * ” 5 0 0 0 4 0 3 5 3 0 鲁2 5 邑2 0 昌1 5 = 1 0 5 0 网门| _ 1 j 1 - j 1 2 0 0 02 0 0 12 0 0 22 0 0 32 0 0 42 0 0 52 0 0 62 0 0 7 年份 图1 - 1t o p 5 0 0 中所有系统的平均处理器数目 l 、 ii- i -i 2 8 0 3 2 34 3 95 3 4 8 1 81 4 6 52 0 4 2 3 2 9 6 处理器数目 图1 2 不同处理器规模下系统的m t b f 实际的系统，如m 的a s c iw h i t e ，在不断提高可靠性的基础上，m t b f 时 间仅为4 0 小时左右 5 1 ；g o o g l e 的8 0 0 0 结点的c l u s t e r ，每年的结点故障率为2 - 3 ， 也就是说每3 6 小时就会发生一个结点故斟6 l ；根据预测，处理器数目超过1 0 0 ，0 0 0 的i b mb l u eg e n e l 的m t b f 可能只有几十分钟口1 。 然而，目前的科学计算程序往往需要连续运行几天甚至几个月，例如b l u eg e n e 第2 页 国防科学技术大学研究生院博士学位论文 上的蛋白质折叠( p r o t e i n f o l d i n g ) 程序需要运行好几个月，科学计算程序难以在大规 模系统上正确地完成计算。所以，可靠性问题己成为高性能计算机发展的重大挑 战之一，p e t a f l o p 规模的计算的成功取决于大规模系统可靠性技术的发展，如何确 保其上运行的科学计算程序能够正确地完成是大规模计算机系统必须解决的重大 问题之一【8 】【引。 1 1 4 软件实现的硬件容错 为了确保科学计算程序能够在大规模系统上正确完成，提高系统的可靠性， 大规模系统必须对出现的硬件故障具有容错功能。容错是用冗余的资源使计算机 具有容忍故障的能力，即在产生故障的情况下，程序仍然能够正确地运行【1 0 1 。 硬件容错是通过硬件的重复使用来获得容错能力【1 - 【2 4 】。例如，对于c a c h e 和 r a m 等存储部件采用奇偶校验位或者差错校正码( e c c ，e r r o rc o r r e c t i o n c o d e s ) 1 12 | ，这些冗余位用来检测和纠正故障。然而，高可靠的系统需要更多的硬 件冗余，如ms 3 9 0 系列处理器采用了重复功能单元的方法来获得高可靠性 2 1 】【2 2 1 ；b o e i n g7 7 7 飞行系统采用y - 模冗余的方法实现故障检测和恢复冽【2 4 1 。由 此可见，硬件容错的方法对于大规模系统代价很高，大规模系统可能会在存储子 系统中采用e c c 校正码，但是执行部件的双模或三模冗余肯定是不可行的。 软件实现的硬件容错是采用软件的方法来屏蔽发生在硬件中的故障，软件实 现的硬件容错通常采用时间冗余的方法实现【2 5 】- 【4 9 1 。例如，e d d i 算法复制程序指 令，并在一定的同步点( s t o r e 指令处和b r a n c h 指令处) 插入检测指令来检测故斟2 5 1 ； s w i f r 在e d d i 算法的基础上增加了对程序控制流故障的检测，且将指令复制范 围缩小为仅针对所有的s t o r e 指令，提高了故障检测的效率1 2 6 1 ；c h e c k p o i n t i n g 技术 通过故障后从上一次检查点处重新执行应用的方法实现故障恢复1 3 1 1 【4 9 1 。与硬件容 错方法相比，软件实现的硬件容错以消耗时间资源来达到容错的目的，因此，对 程序的性能有一定的影响。但是，它无需在系统中增加冗余硬件，可以在保证可 靠性的同时，获得较高的性价比。 因此，研究软件实现的硬件故障容错技术，对解决大规模系统的可靠性问题 具有十分重要的意义。 1 2 容错研究基础 在进入硬件故障的容错技术研究之前，本文首先给出一些与容错研究相关的 基础知识，然后讨论并行程序的故障类型，以求读者对容错技术的研究问题以及 本文研究所针对的故障类型有一个直观的印象。 第3 页 国防科学技术大学研究生院博士学位论文 1 2 1 基本概念 一个系统是容错的，指的是它的程序在逻辑故障的情况下仍然能够正确地运 行【l0 1 。容错技术中对于故障( f a u l t ) ，错误( e r r o r ) 和失效( f a i l u r e ) 都分别有明 确的定义【5 0 】【5 。故障是系统的硬件中发生的物理缺陷、设计制造的不完善或软件 中隐含的错误。错误是系统中的某一部分由于故障而产生了非正常的行为或状态 的现象。失效是系统在运行到一定的时间，或在一定的条件下偏离它预期设计的 要求或规定的功能。故障、错误与失效构成一个因果链，即故障引起错误，错误 又引起失效。故障会造成错误，但并不总是故障一出现就立即会产生错误，从故 障发生至由于该故障而产生错误的时间间隔称为故障潜伏期( f a u l tl a t e n c y ) ；同样， 错误会造成失效，但并不总是错误一发生就会造成失效。从错误发生至由于该错 误而造成失效的时间间隔称为错误潜伏期( e r r o rl a t e n c y ) 。从故障发生至造成失效 的时间间隔称为失效潜伏期( f a i l u r el a t e n c y ) ，是故障潜伏期和错误潜伏期之和。 图1 3 给出了从故障到失效之间的变化过程。 图1 3 故障，错误和失效 1 - 2 2 并行程序的故障类型 为了便于研究，故障模型一般分为两类：b y z a t i n e 故障模型和f a i l s t o p 故障模 型。b y z a n t i n e 模型中，当一个进程发生故障时，故障进程会引起其它进程产生错 误的状态，比如发送错误的数据等【5 2 j _ 【5 8 】。b y z a n t i n e 模型可以表示任意故障，但检 测这类故障非常困难【5 9 1 一【6 8 l 。f a i l s t o p 模型中，当一个进程发生故障时，该进程停 止运行，它不会引起系统中的其它进程产生错误的状态。f a i l s t o p 故障模型可描述 并行计算中进程挂起或崩溃的情况旧】1 7 0 i ，是并行计算领域常见的硬件故障模型。 高性能计算领域常用的容错技术大多是遵循f a i l s t o p 模型，因此，本文的研究也是 针对f a i l s t o p 故障类型的容错技术。 1 3 1 课题来源 1 3 课题研究内容 第4 页 国防科学技术大学研究生院博士学位论文 本课题来源于国家自然科学基金创新研究群体科学基金“千万亿次高性能计 算关键技术”( 项目编号：6 0 6 2 1 0 0 3 ) 。此项目的主要研究内容是面向高性能计算 的处理器体系结构、并行算法及其容错技术以及编译优化技术。作为其中的组成 部分，本课题重点针对并行算法的容错技术进行了深入研究。 1 3 2 课题研究重点 为了提高大规模系统的可靠性，必须提供硬件故障的容错方法。软件实现的 硬件容错是指大规模系统的软件能够检测出系统中已经发生的硬件故障并从故障 中恢复。软件实现的硬件容错技术包括故障检测和故障恢复等过程，本文的研究 主要是针对故障恢复的方法，故障检测利用并行执行环境的支持实现。本文的研 究重点是提出了容错并行算法的新概念，容错并行算法是一种可以实现硬件容错 的并行算法。本文从算法设计，编译工具以及性能分析等多个层次对容错并行算 法进行研究，主要是回答下面的几个问题： ( 1 ) 提出容错并行算法的理论背景是什么? 传统的并行计算是以性能为目标的，不考虑系统出现故障情况下的可靠性。 然而，随着大规模并行系统具有硬件故障的不可避免性，系统故障导致并行计算 的可靠性急剧降低，可靠性逐渐成为并行计算的主要目标之一，因此，必须在考 虑系统故障的条件下对并行计算的可靠性进行研究。并行算法任务依赖图是算法 设计的基础，本文基于并行算法任务依赖图分析了并行计算的可靠性，并以此为 基础，分析和比较了最常采用的时间冗余和空间冗余的容错技术对并行计算可靠 性的影响。时间冗余的容错技术中复算时间对提高并行计算的可靠性影响很大， 缩短故障恢复时间可以有效提高并行计算的可靠性，这也是容错并行算法提出的 背景。 ( 2 ) 什么是容错并行算法? 目前的并行应用中，一旦出现结点失效，整个并行应用停止运行。当前大规 模系统中应用最广泛的软件实现的硬件容错方法是回滚恢复的方法：当一个并行 作业运行时，将在某一时刻的计算状态称作检查点( c h e c k p o i n t ) ，将这一状态存储 起来；出现故障时，需要冷启动并行作业，并行作业重启后，回滚到最近一个检 查点处重新计算，重算上次检查点到故障时刻之间的任务，这造成了用户响应时 间的增加。同时，这种方法在恢复时，所有故障结点上的全部计算都在单个处理 器上重算，使得恢复时间不可能小于前一个检查点和故障发生时刻之间的时间间 隔。为避免现有回滚恢复技术的冷启动以及缩短故障的恢复时间，提高并行计算 的可靠性，本文提出了容错并行算法的概念，容错并行算法是一种能够实现自行 检测故障并容错的并行算法。恢复时，容错并行算法利用无故障进程对故障进程 第5 页 国防科学技术大学研究生院博士学位论文 上的计算进行并行复算。 ( 3 ) 如何设计容错并行算法? 容错并行算法的设计在并行算法设计的基础上增加了容错设计部分。设计一 个容错并行算法必须考虑下面的因素：容错的粒度；正常运行时数据保存的开销 以及故障恢复的开销。容错并行算法的设计过程就是综合上面的因素，产生与相 应的并行算法相匹配的容错性能。本文系统地讨论了容错并行算法的设计方法， 随后，根据容错并行算法的设计方法设计出矩阵l u 分解、快速傅里叶变换以及桶 排序等三类典型并行应用的容错并行算法，进一步阐述了容错并行算法的设计方 法。 ( 4 ) 如何使容错并行算法走向实用? 容错并行算法的设计是以程序段为基础，添加数据保存段，故障检测段和复 算段构成相应的容错程序段。容错并行算法的实现需要对原有的并行算法进行修 改，需要用户选择程序段，手动设计故障检测段、数据保存段和复算段。实现过 程给程序员带来了很大的编程负担，这也是容错并行算法走向实用的一大障碍。 为了减轻程序员设计容错并行算法的负担，使容错并行算法走向实用，必须通过 编译技术实现容错并行算法的设计自动化。本文给出了面向m p i 并行程序的容错 并行算法设计的编译辅助工具g i f t ( g e ti tf a u l t t o l e r a n t ) 的实现方法，g i f t 实现了 故障检测段，数据保存段和复算段设计的自动化。 ( 5 ) 如何评估容错并行算法? 传统的并行程序的性能度量是用于评估无故障时的程序性能。容错并行算法 是在并行算法设计的基础上增加了容错设计部分，因此，容错并行算法的评估必 须考虑故障对程序性能的影响。本文研究评估故障情况下的容错并行算法性能的 各种度量，通过建立性能模型来预测容错并行算法的期望执行时间，并以此为基 础完成对容错并行算法的性能评估。 1 3 3 课题研究难点 本课题主要围绕容错并行算法展开研究，涉及的知识领域较广，具有一定的 难度，具体表现