矩阵lu分解的容错并行算法设计与实现

《矩阵lu分解的容错并行算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、25卷第1嗍2008年10月微电子学与计算机MICROEUeCrI之ONICS&COM咿UTERVd．25No．10October2008矩阵LU分解的容错并行算法设计与实现杜云飞，王攀峰，富弘毅，周海芳，杨学军(国防科技大学计算机学院并行与分布重点实验室，湖南长沙410073)摘要：给出了容错并行算法的定义，提出了一种新的基于并行复算的容错并行算法．针对许多计算密集型任务中的矩阵LU分解设计了相应的基于并行复算的容错并行算法，并对设计的矩阵LU分解的容错并行算法的性能进行了评估并与checkpointing方法进行了对比．结果表明与checkpointing方法相比，矩阵

2、LU分解的容错并行算法有性能上的优势．关键词：矩阵LU分解；并行算法；容错中图分类号：TP302文献标识码：A文章编号：1000—7180(2008)10—0001—04Fault-tolerantMatrixLUAlgorithmusingParallelRecoveryDUYun—fei，WANGPan-feng，FUHong-yi，ZHOUHai—fang，YANGXue-jun(PDL，CollegeofComputer，NationalUniversityofDefenseTechnology，Changsha410073，China)Abstract：T11iS

3、paperpresentsthedefinitionoffaulttolerantparalldalgorithm．Thenanewmethodnamedparallelre—computingbasedfaulttolerantparalldalgorithm(PRBFTPA)isproposed．TheauthorspresentthedesignofPRBFTPAformatrixLUdecomposition，andevaluatethembyexperimentsonadustersystemandeomparethemwiththemethodofcheckpo

4、inting．TheexperimeaatalresultsshowthattheoverheadofPRBFTPAsformatrixoperationsislessthantheoverheadofcheck-pointing．Keywords：matrixLUdecomposition；paralldalgorithms；faulttolerance1引言系统级Checkpointing是一种广泛应用于大规模系统的容错技术[1-2]，该技术是在程序执行期间周期性的将所有进程的地址空间内容(堆、栈和全局变量)、寄存器信息和通信库状态存储到可靠的存储器上【3圳．如果某个进

5、程失效，所有进程都必须回滚到最近一个检查点处重新计算．当系统中包含数千甚至数万个处理器时，做一次checkpoint可能会导致所有处理器传输Terabytes的数据到存储介质上，从而使I／O成为大规模并行系统中checkpointing技术的性能瓶颈．由于这个原因，在IBMBlueGene和ASCI等大规模系统中未采用系统级checkpoint—ing技术t5

6、．应用级容错是大规模系统中另一种通用容错技术，通过修改应用实现容错功能，可实现较低的容错开销№J．应用级check-p蛐g是应用级容错技术中使用最广泛的方法，它允许用户指定checkr施thg的时机并选择尽可能少的信

7、息进行保存，通过减小需要保存的数据量来改善容错性能．但这种技术仍然要求无故障进程在恢复时回滚，重算上次检查点到故障时刻之间的任务，这造成了计算时间的浪费【7j．文中提出了一种新的基于并行复算的容错算法，本文创新点在于以下几个方面：提出了容错并行算法的定义，用于描述应用级容错方法；设计了矩阵计算的基于并行复算的容错并行算法，并对设计的算法进行了性能测试．2容错并行算法系统中两种通用故障类型分别是Fail．stop和收稿日期：2008—03—13基金项目：国家自然科学基金项目(60621003，60603081)；国家“八六三”计划项目(2007AAl22147)2微电子学与计

8、算机2008年Byzatine故障[8]8．针对不同的故障类型，容错并行算法的设计有很大的不同．文中主要针对fail．stop的故障类型，对基于并行复算的容错并行算法的设计进行讨论．基于并行复算的容错并行算法(PR唧A)是一种新的用于并行计算的容错方法【9J，它的主要特点是当某一进程发生故障时，通过其它无故障进程并行重算失效进程的任务实现故障快速恢复，并且整个故障恢复过程由算法自动完成，不需要人工干预．为了进行基于并行复算的容错并行算法的设计，首先给出并行程序复算段的定义．定义1复算段是指通信与通信之间、通信与初始