宋效東，劉學(xué)軍，湯國安＊，竇萬峰，江嶺，楊坤

（1.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023；2.南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210023）

0 引言

在高性能地學(xué)計(jì)算領(lǐng)域，任務(wù)計(jì)算失敗將會(huì)導(dǎo)致計(jì)算資源的巨大浪費(fèi)。高性能地學(xué)計(jì)算不僅要滿足實(shí)時(shí)性需求，還要求在計(jì)算機(jī)的軟硬件出現(xiàn)故障時(shí)保證計(jì)算的正確進(jìn)行。但高性能計(jì)算的發(fā)展遠(yuǎn)遠(yuǎn)領(lǐng)先于軟件設(shè)計(jì)及應(yīng)用的發(fā)展，這使得利用已有的硬件資源實(shí)現(xiàn)高質(zhì)量的軟件容錯(cuò)功能成為重要的研究方向［1－3］。

根據(jù)對容錯(cuò)資源的使用性質(zhì)分類，容錯(cuò)技術(shù)主要分為軟件容錯(cuò)與硬件容錯(cuò)。軟件容錯(cuò)不僅需要處理計(jì)算機(jī)中的硬件故障，還需要在系統(tǒng)運(yùn)行周期內(nèi)及時(shí)發(fā)現(xiàn)并處理自身的設(shè)計(jì)錯(cuò)誤［4］。軟件容錯(cuò)技術(shù)不僅避免了增加冗余硬件的開銷，又能有效屏蔽軟件設(shè)計(jì)中的錯(cuò)誤［5］，提高系統(tǒng)整體的可靠性，因此成為目前應(yīng)用較為廣泛的容錯(cuò)模型?；谒惴ǖ娜蒎e(cuò)技術(shù)（Algorithm Based Fault Tolerance，ABFT）是為容忍硬件瞬時(shí)故障而設(shè)計(jì)的一類算法［6，7］。與傳統(tǒng)的容錯(cuò)技術(shù)相比，ABFT技術(shù)能夠高效地實(shí)現(xiàn)硬件錯(cuò)誤的檢測、定位甚至恢復(fù)［8，9］。ABFT在20世紀(jì)90年代得到廣泛關(guān)注，其理論與應(yīng)用也得到了豐富與發(fā)展［10，11］。但由于算法本身固有的缺點(diǎn)——低通用性，此類算法只對部分操作具有容錯(cuò)功能，如矩陣乘、矩陣分解、快速傅里葉變換算法等。

近十年來，各種空間數(shù)據(jù)獲取技術(shù)的飛速發(fā)展為數(shù)字地形分析提供了海量的數(shù)據(jù)源，并行計(jì)算的應(yīng)用已是大勢所趨［12］。本文針對并行數(shù)字地形分析技術(shù)的特點(diǎn)提出基于算法的容錯(cuò)模型，以此為基礎(chǔ)完成對鄰域型算法的錯(cuò)誤檢測與恢復(fù)。

1 容錯(cuò)模型與前提假設(shè)

1.1 前提假設(shè)

有別于一般的高性能計(jì)算程序，并行地形分析的算法復(fù)雜度一般不是很高。由于數(shù)據(jù)日益增長的精度與分辨率，導(dǎo)致海量空間數(shù)據(jù)的運(yùn)行時(shí)間相對較長［13－15］，一旦計(jì)算失敗，將會(huì)浪費(fèi)大量的計(jì)算資源進(jìn)行重算。在并行數(shù)字地形分析的容錯(cuò)研究中，本文將注意力集中在軟件容錯(cuò)方面。假設(shè)基于算法的容錯(cuò)模型應(yīng)用于：有N個(gè)進(jìn)程進(jìn)行分布式并行計(jì)算，同時(shí)該集群可以提供穩(wěn)定的通信。集群中有兩個(gè)主節(jié)點(diǎn)，同時(shí)負(fù)責(zé)對各子進(jìn)程計(jì)算結(jié)果的校驗(yàn)（圖1）。這樣主進(jìn)程也有一個(gè)相應(yīng)的副本，該主從模型可以很好地避免子節(jié)點(diǎn)與主節(jié)點(diǎn)同時(shí)發(fā)生故障時(shí)系統(tǒng)崩潰的情況。

根據(jù)算法的分析范圍與數(shù)據(jù)依賴關(guān)系，可以將地形分析算法基本分為鄰域型算法與全局型算法［16］。鄰域型算法可以有效地研究與表達(dá)地貌形態(tài)特征，算法種類繁多［17］，具有重要的理論與應(yīng)用價(jià)值。在數(shù)據(jù)劃分時(shí)，假設(shè)DEM數(shù)據(jù)以行為單位進(jìn)行數(shù)據(jù)劃分，相應(yīng)地，所有的計(jì)算節(jié)點(diǎn)上DEM的列數(shù)都相等。為了更好地體現(xiàn)基于算法的容錯(cuò)模型的特點(diǎn)，本文不考慮數(shù)據(jù)或算法間的依賴關(guān)系，著重研究鄰域型算法并行化設(shè)計(jì)中的容錯(cuò)機(jī)制。

圖1 基于算法的容錯(cuò)模型Fig.1 Basic diagram of fault－tolerant model based on algorithm

1.2 基于算法的容錯(cuò)模型

并行算法將規(guī)則格網(wǎng)DEM數(shù)據(jù)以一維行的形式劃分。以二維坐標(biāo)系的形式表示，X軸為東西方向，Y軸為南北方向。借鑒經(jīng)典的基于算法的容錯(cuò)思想，本文提出增加每一數(shù)據(jù)塊部分的校驗(yàn)行，通過校驗(yàn)行計(jì)算結(jié)果的對比來檢驗(yàn)計(jì)算節(jié)點(diǎn)是否發(fā)生了計(jì)算錯(cuò)誤。

定義1 并行數(shù)據(jù)集D ＝ ｛D1，D2，…，Dn｝，其中Di（1≤i≤n）為某一計(jì)算節(jié)點(diǎn)需要處理的數(shù)據(jù)塊，并且該空間數(shù)據(jù)的部分屬性會(huì)保存在主節(jié)點(diǎn)上。

數(shù)據(jù)集存儲(chǔ)在網(wǎng)絡(luò)文件系統(tǒng)（Network File System，NFS）中，各節(jié)點(diǎn)讀取的數(shù)據(jù)都將記錄在主節(jié)點(diǎn)相應(yīng)的日志文件中，從而為從節(jié)點(diǎn)的計(jì)算提供有效的管理功能。

定義2 全局?jǐn)?shù)據(jù)劃分控制ID，用于標(biāo)識(shí)并行數(shù)據(jù)集的計(jì)算任務(wù)。該ID由計(jì)算節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識(shí)（計(jì)算機(jī)名或網(wǎng)卡MAC地址）和劃分?jǐn)?shù)據(jù)的左上角坐標(biāo)——CoordFrom組成。節(jié)點(diǎn)標(biāo)識(shí)數(shù)據(jù)類型為string類型。

定義3 鄰域型算法的容錯(cuò)屬性集合PNeigh，用于記錄所有數(shù)據(jù)塊的空間屬性。主節(jié)點(diǎn)負(fù)責(zé)維護(hù)該屬性集合，用于管理備份所有節(jié)點(diǎn)計(jì)算的任務(wù)信息。該屬性集合部分成員及屬性注釋表述如下：

定義4 冗余行NRow。假設(shè)算法分析窗口為M×N，每一數(shù)據(jù)塊添加冗余行的數(shù)目：

其中的（M－1）／2行是為了避免最后一行數(shù)據(jù)的邊界效應(yīng)增加的緩沖區(qū)，額外增加的最后一行是為了計(jì)算下一節(jié)點(diǎn)的第一行數(shù)據(jù)，用來與相鄰節(jié)點(diǎn)的計(jì)算結(jié)果進(jìn)行正確性校驗(yàn)。

性質(zhì)1：每一數(shù)據(jù)塊的總行數(shù)：Row＝LocakSizeY＋NRow。圖2為一個(gè)5×5分析窗口額外增加冗余數(shù)據(jù)行的示意圖。

圖2 5×5算法數(shù)據(jù)劃分冗余行示意圖Fig.2 Schematic showing redundant rows of algorithm based on five－by－five window

定義5 校驗(yàn)結(jié)果，是在計(jì)算節(jié)點(diǎn)i（i＜N）上對校驗(yàn)行執(zhí)行地形分析算法計(jì)算出的結(jié)果。

定義6 被校驗(yàn)結(jié)果，是節(jié)點(diǎn)i（i＞1）第一行數(shù)據(jù)計(jì)算的結(jié)果。

定義7 校驗(yàn)結(jié)果集V，用于保存所有節(jié)點(diǎn)的校驗(yàn)結(jié)果。V保存了每個(gè)計(jì)算節(jié)點(diǎn)的冗余行計(jì)算結(jié)果和相鄰節(jié)點(diǎn)中被校驗(yàn)的計(jì)算結(jié)果。

第i個(gè)數(shù)據(jù)塊中冗余行計(jì)算結(jié)果也是相鄰節(jié)點(diǎn)（i＋1）的第一行數(shù)據(jù)計(jì)算的結(jié)果。因此，前（N－1）個(gè)數(shù)據(jù)塊的冗余行是在當(dāng)前數(shù)據(jù)塊的最底部。第一塊數(shù)據(jù)沒有被校驗(yàn)結(jié)果，最后一塊數(shù)據(jù)沒有校驗(yàn)結(jié)果。

性質(zhì)2：結(jié)果集V的大小為（TotalSizeX，2×（N－1））。數(shù)據(jù)劃分時(shí)所有數(shù)據(jù)塊的列數(shù)均為TotalSizeX，所以結(jié)果集的列數(shù)也是TotalSizeX。在N個(gè)節(jié)點(diǎn)中，節(jié)點(diǎn)1和節(jié)點(diǎn)N均只能提供校驗(yàn)結(jié)果或被校驗(yàn)結(jié)果，因此結(jié)果集的總行數(shù)是2×（N－1）。結(jié)果集中包含了絕大部分?jǐn)?shù)據(jù)塊的校驗(yàn)結(jié)果和被校驗(yàn)結(jié)果，通過與相鄰計(jì)算節(jié)點(diǎn)的兩次對比，可以保證計(jì)算結(jié)果的正確性。

定義8 鄰域型算法的容錯(cuò)模型N－ABFT。通過以上定義，將鄰域型算法的容錯(cuò)模型表示為一個(gè)三元組 N－ABFT ＝｛PNeigh，NRow，ID｝。通過該三元組，算法可以對比分析各節(jié)點(diǎn)計(jì)算結(jié)果的正確性，實(shí)現(xiàn)計(jì)算錯(cuò)誤的快速檢測。

2 容錯(cuò)處理算法

通過對鄰域型算法冗余的容錯(cuò)機(jī)制分析，本章設(shè)計(jì)基于容錯(cuò)模型的具體算法：錯(cuò)誤檢測算法和任務(wù)恢復(fù)算法。錯(cuò)誤檢測算法通過對比數(shù)據(jù)塊冗余行的計(jì)算結(jié)果對相鄰進(jìn)程進(jìn)行檢錯(cuò)。任務(wù)恢復(fù)算法主要負(fù)責(zé)在其他節(jié)點(diǎn)重新執(zhí)行計(jì)算失敗的節(jié)點(diǎn)，當(dāng)其他節(jié)點(diǎn)計(jì)算結(jié)束后，結(jié)果數(shù)據(jù)需要重新進(jìn)行錯(cuò)誤檢測，從而保證所有數(shù)據(jù)均正確。

為方便描述，定義以下符號(hào)：1）TMaxC（i，j）：無故障情況下，計(jì)算節(jié)點(diǎn)i執(zhí)行算法j的最長計(jì)算時(shí)間，其包含計(jì)算結(jié)果的讀寫時(shí)間；2）TMaxLat（i）：計(jì)算節(jié)點(diǎn)i將計(jì)算過程中的消息發(fā)送給主節(jié)點(diǎn)最大的延遲時(shí)間；3）Equal（arri，arrj）：數(shù)組相等判斷函數(shù)，用于判斷數(shù)據(jù)arri與arrj是否完全相等，兩數(shù)組相等時(shí)函數(shù)返回true，否則返回false；4）Updata（FileName）更新主節(jié)點(diǎn)的日志文件；5）F｛f1，f2，…，fn＋2｝：各節(jié)點(diǎn)計(jì)算的正確性數(shù)據(jù)集，其中n是計(jì)算節(jié)點(diǎn)數(shù)，fi（1≤i≤n＋2）為整型，是節(jié)點(diǎn)計(jì)算結(jié)果的正確性標(biāo)識(shí)，取值范圍是｛0，1，10｝，0代表不可恢復(fù)的計(jì)算錯(cuò)誤，1代表瞬時(shí)錯(cuò)誤，10代表正常。

2.1 錯(cuò)誤檢測算法

利用各節(jié)點(diǎn)計(jì)算數(shù)據(jù)的屬性集合，錯(cuò)誤檢測算法主要負(fù)責(zé)計(jì)算結(jié)果的正確性檢驗(yàn)。錯(cuò)誤檢測算法與各節(jié)點(diǎn)計(jì)算同時(shí)開始，在計(jì)算節(jié)點(diǎn)的計(jì)算過程中，負(fù)責(zé)統(tǒng)計(jì)各計(jì)算節(jié)點(diǎn)執(zhí)行一次計(jì)算的總時(shí)間、最早完成時(shí)間和最大延遲時(shí)間。在錯(cuò)誤檢測時(shí)，如果某節(jié)點(diǎn)運(yùn)行時(shí)間超過最大延遲時(shí)間，則判定該節(jié)點(diǎn)計(jì)算失敗，立即啟動(dòng)任務(wù)恢復(fù)算法。在各節(jié)點(diǎn)計(jì)算全部結(jié)束后，主節(jié)點(diǎn)根據(jù)校驗(yàn)結(jié)果集對各節(jié)點(diǎn)計(jì)算的結(jié)果進(jìn)行正確性檢驗(yàn)。如果相鄰行計(jì)算結(jié)果相等，代表這兩個(gè)節(jié)點(diǎn)均已正確執(zhí)行，否則，啟動(dòng)任務(wù)恢復(fù)算法。如果所有的數(shù)據(jù)塊均已正確計(jì)算，主節(jié)點(diǎn)將算法的容錯(cuò)屬性集合PNeigh寫入日志文件。如果各節(jié)點(diǎn)均正確執(zhí)行或執(zhí)行任務(wù)恢復(fù)算法后，需判定主節(jié)點(diǎn)是否存在計(jì)算失敗的情況。算法描述如下：

算法1 N－ABFT錯(cuò)誤檢測算法

輸入：計(jì)算節(jié)點(diǎn)個(gè)數(shù)N，全局?jǐn)?shù)據(jù)劃分控制ID，校驗(yàn)結(jié)果集V，鄰域型算法的容錯(cuò)屬性集合PNeigh，TMaxLat（i）；

輸出：各節(jié)點(diǎn)計(jì)算的正確性數(shù)據(jù)集F，TMaxC（i，j）。

（1）判斷機(jī)群中是否存在節(jié)點(diǎn)失敗的情況，依次對各計(jì)算節(jié)點(diǎn)進(jìn)行錯(cuò)誤檢測（for i＝1，…，N）。在計(jì)算開始前，向各進(jìn)程i發(fā)送計(jì)算任務(wù)，包括PNeigh和Di；如果節(jié)點(diǎn)均能在TMaxLat（i）之內(nèi)將消息發(fā)送給主節(jié)點(diǎn)，則該節(jié)點(diǎn)初始化正常，fi＝10，否則記錄并修改該節(jié)點(diǎn)的狀態(tài)屬性fi＝0。兩個(gè)主節(jié)點(diǎn)分別對節(jié)點(diǎn)1和節(jié)點(diǎn)N的數(shù)據(jù)進(jìn)行冗余計(jì)算，并保存在本地，其他的從節(jié)點(diǎn)計(jì)算地形分析算法，計(jì)算結(jié)束后將計(jì)算結(jié)果寫入全局輸出文件；當(dāng)所有節(jié)點(diǎn)計(jì)算結(jié)束后，根據(jù)算法j的復(fù)雜度，記錄各計(jì)算節(jié)點(diǎn)的TMaxC（i，j）。各節(jié)點(diǎn)發(fā)送結(jié)束消息到主節(jié)點(diǎn)，如果節(jié)點(diǎn)均能在TMaxLat（i）之內(nèi)將消息發(fā)送給主節(jié)點(diǎn)，則該節(jié)點(diǎn)計(jì)算結(jié)束，fi＝10；否則判定該節(jié)點(diǎn)計(jì)算失敗，記錄修改該節(jié)點(diǎn)的狀態(tài)屬性fi＝0。

（2）對比分析各節(jié)點(diǎn)計(jì)算結(jié)果的正確性。讀取校驗(yàn)結(jié)果集V，依次判斷數(shù)據(jù)行（for i＝1，…，（N－1））：首先判斷節(jié)點(diǎn)1和節(jié)點(diǎn)N的正確性，并修改fi的值；讀取數(shù)據(jù)集，取出2×i－1與2×i兩行數(shù)據(jù)（分別對應(yīng)計(jì)算節(jié)點(diǎn)i和i＋1的校驗(yàn)結(jié)果與被校驗(yàn)結(jié)果），分別存入浮點(diǎn)數(shù)組arri，arrj，執(zhí)行Equal（arri，arrj）；如果函數(shù)返回true，節(jié)點(diǎn)i與i＋1計(jì)算的結(jié)果完全正確，修改fi＝10；如果函數(shù)返回false，驗(yàn)證節(jié)點(diǎn)i＋1計(jì)算結(jié)果的正確性，讀取第2×（i＋1）－1與2×（i＋1）行的數(shù)據(jù)（分別對應(yīng)計(jì)算節(jié)點(diǎn)i＋1與j＋2的校驗(yàn)結(jié)果與被校驗(yàn)結(jié)果），并分別存入浮點(diǎn)數(shù)組arri＋1，arrj＋1，并執(zhí)行Equal（arri＋1，arrj＋1）：如果函數(shù)返回true，說明節(jié)點(diǎn)i＋1計(jì)算結(jié)果正確，節(jié)點(diǎn)i計(jì)算錯(cuò)誤，修改fi＋1＝10，fi＝1；如果函數(shù)返回false，說明節(jié)點(diǎn)i計(jì)算結(jié)果錯(cuò)誤，節(jié)點(diǎn)i＋1計(jì)算正確，修改fi＝10，fi＋1＝1。

（3）判斷主節(jié)點(diǎn)的計(jì)算是否發(fā)生錯(cuò)誤，執(zhí)行如下操作：兩個(gè)主節(jié)點(diǎn)同時(shí)對PNeigh和F進(jìn)行判斷與更新；兩節(jié)點(diǎn)相互發(fā)送確認(rèn)消息，如果其中的一個(gè)節(jié)點(diǎn)效應(yīng)時(shí)間超過TMaxLat（i），則判定該節(jié)點(diǎn)失敗，fN＋1＝0，取另外一個(gè)主節(jié)點(diǎn)的數(shù)據(jù)作為輸出結(jié)果；輸出各節(jié)點(diǎn)計(jì)算的數(shù)據(jù)集F與TMaxC（i，j）。

2.2 任務(wù)恢復(fù)算法

在程序計(jì)算結(jié)束后，對于發(fā)生計(jì)算故障的計(jì)算任務(wù)，算法將根據(jù)其故障類型進(jìn)行重算。對于不可恢復(fù)故障，算法使用其他的計(jì)算節(jié)點(diǎn)對計(jì)算任務(wù)進(jìn)行重算。對于瞬時(shí)故障，算法會(huì)在該節(jié)點(diǎn)上重新計(jì)算。算法描述如下：

算法2 N－ABFT任務(wù)恢復(fù)算法

輸入：各節(jié)點(diǎn)計(jì)算的正確性數(shù)據(jù)集F；

輸出：校驗(yàn)結(jié)果集V，鄰域型算法的容錯(cuò)屬性集合PNeigh、TMaxC（i，j）和TMaxLat（i）。

（1）統(tǒng)計(jì)出現(xiàn)可恢復(fù)和不可恢復(fù)故障的計(jì)算節(jié)點(diǎn)數(shù)，分別為NErrRecov、NErrUnrecov。

（2）對于可恢復(fù)故障的計(jì)算節(jié)點(diǎn)（for i＝1，…，NErrRecov）：重新執(zhí)行可恢復(fù)故障計(jì)算失敗的計(jì)算任務(wù)，對V中相應(yīng)的內(nèi)容進(jìn)行重寫；根據(jù)V的內(nèi)容，重新執(zhí)行錯(cuò)誤檢測算法：如果正確執(zhí)行，修改fi＝10；否則，判定該節(jié)點(diǎn)不可用，從計(jì)算資源中刪除該節(jié)點(diǎn)，fi＝1；計(jì)算TMaxC（i，j）、TMaxLat（i），并更新正確性標(biāo)識(shí)集合F。

（3）對于不可恢復(fù)故障的計(jì)算節(jié)點(diǎn)上的計(jì)算任務(wù)（for i＝1，…，NErrUnrecov）：重新分配計(jì)算資源，對計(jì)算失敗的任務(wù)重新計(jì)算。從計(jì)算資源中刪除不可用節(jié)點(diǎn)；對重新計(jì)算的計(jì)算結(jié)果進(jìn)行錯(cuò)誤檢測；其余節(jié)點(diǎn)執(zhí)行新的計(jì)算。

（4）輸出并更新校驗(yàn)結(jié)果集V等信息。

3 實(shí)驗(yàn)結(jié)果

本文在一個(gè)小規(guī)模的機(jī)群系統(tǒng)上實(shí)現(xiàn)了該算法。性能測試的環(huán)境為：18臺(tái)計(jì)算機(jī)構(gòu)成Cluster結(jié)構(gòu)（2個(gè)管理節(jié)點(diǎn)，16個(gè)計(jì)算節(jié)點(diǎn)），處理器配備Xeon E5645 2.8GHz的四核處理器和8GB內(nèi)存，節(jié)點(diǎn)間使用千兆以太網(wǎng)互連。機(jī)群采用主從模型，兩個(gè)主節(jié)點(diǎn)用來負(fù)責(zé)數(shù)據(jù)分發(fā)、管理、容錯(cuò)檢測與調(diào)度。DEM數(shù)據(jù)規(guī)模是16 000×15 120，數(shù)據(jù)類型是16位浮點(diǎn)型，數(shù)據(jù)大小約為540MB，TIFF格式。

在可靠性需求較大的重要領(lǐng)域，以往的容錯(cuò)技術(shù)主要采用三部件冗余［18］或進(jìn)程副本，其錯(cuò)誤檢測的資源消耗分別為200%和100%。軟件容錯(cuò)方法中的冗余進(jìn)程（Redundant Processes）被認(rèn)為是并行程序錯(cuò)誤檢測的有效方法［19，20］。本文以冗余進(jìn)程為對比對象，使用不同的資源進(jìn)程對不同的算法進(jìn)行性能測試。設(shè)計(jì)并實(shí)現(xiàn)了不同分析窗口下的并行容錯(cuò)算法：3×3窗口的坡度算法和11×11窗口的切割深度算法。軟件錯(cuò)誤概率分別為0～0.2。為了測試部分計(jì)算失敗對算法性能的影響，假設(shè)節(jié)點(diǎn)具有相等且獨(dú)立的錯(cuò)誤概率，系統(tǒng)隨機(jī)地設(shè)定部分計(jì)算失敗，包括CPU崩潰、內(nèi)存申請失敗、文件讀寫異常、NoData值設(shè)定異常和程序計(jì)算錯(cuò)誤。

并行坡度提取算法與切割深度的平均檢錯(cuò)開銷如圖3和圖4所示。測試結(jié)果表明，該算法的檢錯(cuò)開銷明顯比冗余進(jìn)程方法低很多，能很好地檢測到計(jì)算錯(cuò)誤，并能夠根據(jù)校驗(yàn)結(jié)果集找出計(jì)算錯(cuò)誤的節(jié)點(diǎn)。盡管冗余進(jìn)程可以實(shí)時(shí)地檢測程序錯(cuò)誤，但是需要占用較多的資源進(jìn)行容錯(cuò)，而本文的檢錯(cuò)開銷在5%以內(nèi)。通過引入冗余行的概念，不僅使系統(tǒng)獲得了高錯(cuò)誤檢測率，還為容錯(cuò)調(diào)度提供了參考方法。

圖3 并行坡度算法的檢錯(cuò)開銷Fig.3 Execution time of parallel slope algorithms

圖4 并行切割深度算法的檢錯(cuò)開銷Fig.4 Execution time of parallel cutting depth algorithms

4 結(jié)語

軟件質(zhì)量的提高并不意味著不再需要容錯(cuò)。隨著軟件運(yùn)行環(huán)境的開放與集群規(guī)模的增大，殘留在并行系統(tǒng)中的各種故障隱患被激活的概率也隨之增加。本文設(shè)計(jì)的容錯(cuò)算法主要針對海量DEM的并行地形分析鄰域型算法而設(shè)計(jì)，通過定義基于算法的容錯(cuò)模型與冗余行所計(jì)算的校驗(yàn)結(jié)果集，對比分析節(jié)點(diǎn)間計(jì)算同一數(shù)據(jù)行的正確性。測試結(jié)果表明，該算法可以有效檢測集群中的計(jì)算錯(cuò)誤，縮短錯(cuò)誤檢測時(shí)間，提高并行系統(tǒng)穩(wěn)定性。該算法雖然為鄰域型地形分析算法而設(shè)計(jì)，但算法原理有望在其他鄰域型并行算法容錯(cuò)上得到應(yīng)用。下一步，筆者將深入探討檢查周期的系統(tǒng)耗費(fèi)及二次容錯(cuò)機(jī)制。

［1］ RANDELL B.System structure for software fault tolerance［J］.IEEE Transactions on Software Engineering，1975，1（2）：221－232.

［2］ LEVITIN G.Optimal structure of fault－tolerant software systems［J］.Reliability Engineering and System Safety，2005，89（3）：286－295.

［3］ LEVITIN G，XIE M，ZHANG T.Reliability of fault－tolerant systems with parallel task processing［J］.European Journal of Operational Research，2007，177（1）：420－430.

［4］ 杜云飛，唐玉華.容錯(cuò)并行算法的分類和設(shè)計(jì)［J］.華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，39（4）：49－52.

［5］ HANMER R S.Patterns for Fault Tolerant Software［M］.John Wiley ＆Sons Ltd，2007.

［6］ HUANG K H，ABRAHAM J A.Algorithm－based fault tolerance for matrix operations［J］.IEEE Transactions on Computers，1984，33（6）：518－528.

［7］ OBORIL F，TAHOORI M B，HEUVELINE V，et al.Numerical defect correction as an algorithm－based fault tolerance technique for iterative solvers［A］.17th IEEE Pacific Rim International Symposium on Dependable Computing Pasadena，CA，USA，2011.144－153.

［8］ BOSILCA G，DELMAS R，DONGARRA J，et al.Algorithm－based fault tolerance applied to high performance computing［J］.Parallel and Distributed Computing，2009，69（4）：410－416.

［9］ BANERJEE P，ABRAHAM J A.Bounds on algorithm－based fault tolerance in multiple processor systems［J］.IEEE Transactions on Computers，1986，35（4）：296－306.

［10］ CHEN Z，DONGARRA J.Algorithm－based fault tolerance for fail－stop failures［J］.IEEE Transactions on Parallel and Distributed Systems，2008，（19）12：1628－1641.

［11］ MISHRA A，MILI L，PHADKE A G.Algorithm based fault tolerant state estimation of power systems［A］.Proceedings of the 8th International Conference on Probabilistic Methods Ap－plied to Power Systems，Iowa State University，Ames，IA，2004.97－103.

［12］ 王結(jié)臣，王豹，胡瑋，等.并行空間分析算法研究進(jìn)展及評述［J］.地理與地理信息科學(xué)，2011，27（6）：1－5.

［13］ MINETER M J，DOWERS S，CALDWELL D R，et al.Highthroughput computing to enhance intervisibility analysis［A］.Proceedings of the 7th International Conference on GeoComputation［C］.Southampton，United Kingdom，2003.

［14］ GUAN X，WU H.Leveraging the power of multi－core platforms for large－scale geospatial data processing：Exemplified by generating DEM from massive LiDAR point clouds［J］.Computers＆ Geosciences，2010，36（10）：1276－1282.

［15］ 宋效東，劉學(xué)軍，湯國安，等.DEM與地形分析的并行計(jì)算［J］.地理與地理信息科學(xué)，2012，28（4）：1－7.

［16］ SCHIELE S，M LLER M，BLAAR H，et al.Parallelization strategies to deal with non－localities in the calculation of regional land－surface parameters［J］.Computers ＆ Geosciences，2012，44：1－9.

［17］ WILSON J P.Digital terrain modeling［J］.Geomorphology，2012，137（1）：107－121.

［18］ LYONS R E，VANDERKULK W.The use of triple－modular redundancy to improve computer reliability［J］.IBM Journal of Research and Development，1962，6（2）：200－209.

［19］ 富弘毅，宋偉，楊學(xué)軍.利用冗余進(jìn)程實(shí)現(xiàn) MPI程序錯(cuò)誤檢測［J］.微電子學(xué)與計(jì)算機(jī)，2009，26（9）：53－56.

［20］ REED D A，LU C，MENDES C L.Reliability challenges in large systems［J］.Future Generation Computer Systems，2006，22（3）：293－302.