資源描述：
《矩陣lu分解的容錯并行算法設(shè)計與實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、25卷第1嗍2008年10月微電子學(xué)與計算機MICROEUeCrI之ONICS&COM咿UTERVd．25No．10October2008矩陣LU分解的容錯并行算法設(shè)計與實現(xiàn)杜云飛，王攀峰，富弘毅，周海芳，楊學(xué)軍(國防科技大學(xué)計算機學(xué)院并行與分布重點實驗室，湖南長沙410073)摘要：給出了容錯并行算法的定義，提出了一種新的基于并行復(fù)算的容錯并行算法．針對許多計算密集型任務(wù)中的矩陣LU分解設(shè)計了相應(yīng)的基于并行復(fù)算的容錯并行算法，并對設(shè)計的矩陣LU分解的容錯并行算法的性能進行了評估并與checkpointing方法進行了對比．結(jié)果表明與checkpointing方法相比，矩陣
2、LU分解的容錯并行算法有性能上的優(yōu)勢．關(guān)鍵詞：矩陣LU分解；并行算法；容錯中圖分類號：TP302文獻標識碼：A文章編號：1000—7180(2008)10—0001—04Fault-tolerantMatrixLUAlgorithmusingParallelRecoveryDUYun—fei，WANGPan-feng，F(xiàn)UHong-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引言系統(tǒng)級Checkpointing是一種廣泛應(yīng)用于大規(guī)模系統(tǒng)的容錯技術(shù)[1-2]，該技術(shù)是在程序執(zhí)行期間周期性的將所有進程的地址空間內(nèi)容(堆、棧和全局變量)、寄存器信息和通信庫狀態(tài)存儲到可靠的存儲器上【3圳．如果某個進
5、程失效，所有進程都必須回滾到最近一個檢查點處重新計算．當系統(tǒng)中包含數(shù)千甚至數(shù)萬個處理器時，做一次checkpoint可能會導(dǎo)致所有處理器傳輸Terabytes的數(shù)據(jù)到存儲介質(zhì)上，從而使I／O成為大規(guī)模并行系統(tǒng)中checkpointing技術(shù)的性能瓶頸．由于這個原因，在IBMBlueGene和ASCI等大規(guī)模系統(tǒng)中未采用系統(tǒng)級checkpoint—ing技術(shù)t5
6、．應(yīng)用級容錯是大規(guī)模系統(tǒng)中另一種通用容錯技術(shù)，通過修改應(yīng)用實現(xiàn)容錯功能，可實現(xiàn)較低的容錯開銷№J．應(yīng)用級check-p蛐g(shù)是應(yīng)用級容錯技術(shù)中使用最廣泛的方法，它允許用戶指定checkr施thg的時機并選擇盡可能少的信
7、息進行保存，通過減小需要保存的數(shù)據(jù)量來改善容錯性能．但這種技術(shù)仍然要求無故障進程在恢復(fù)時回滾，重算上次檢查點到故障時刻之間的任務(wù)，這造成了計算時間的浪費【7j．文中提出了一種新的基于并行復(fù)算的容錯算法，本文創(chuàng)新點在于以下幾個方面：提出了容錯并行算法的定義，用于描述應(yīng)用級容錯方法；設(shè)計了矩陣計算的基于并行復(fù)算的容錯并行算法，并對設(shè)計的算法進行了性能測試．2容錯并行算法系統(tǒng)中兩種通用故障類型分別是Fail．stop和收稿日期：2008—03—13基金項目：國家自然科學(xué)基金項目(60621003，60603081)；國家“八六三”計劃項目(2007AAl22147)2微電子學(xué)與計
8、算機2008年Byzatine故障[8]8．針對不同的故障類型，容錯并行算法的設(shè)計有很大的不同．文中主要針對fail．stop的故障類型，對基于并行復(fù)算的容錯并行算法的設(shè)計進行討論．基于并行復(fù)算的容錯并行算法(PR唧A)是一種新的用于并行計算的容錯方法【9J，它的主要特點是當某一進程發(fā)生故障時，通過其它無故障進程并行重算失效進程的任務(wù)實現(xiàn)故障快速恢復(fù)，并且整個故障恢復(fù)過程由算法自動完成，不需要人工干預(yù)．為了進行基于并行復(fù)算的容錯并行算法的設(shè)計，首先給出并行程序復(fù)算段的定義．定義1復(fù)算段是指通信與通信之間、通信與初始
