[發(fā)明專利]一種面向數據并行計算容錯的快速并行復算方法

有效

• 申請?zhí)枺?/td>: 201510415605.1
• 申請日: 2015-07-15
• 公開（公告）號: CN105022673B
• 公開（公告）日: 2018-07-20
• 發(fā)明（設計）人: 竇萬峰;苗守帥
• 申請（專利權）人: 南京師范大學
• 主分類號: G06F11/07
• 分類號: G06F11/07
• 代理公司: 南京知識律師事務所 32207
• 代理人: 李媛媛

本發(fā)明屬于并行系統(tǒng)容錯的技術領域，涉及利用冗余計算對計算任務進行檢錯和糾錯進行的并行復算方法，特別提出基于出錯任務對應的數據塊進行邏輯劃分及二次調度的快速并行復算方法。包括：對數據塊的計算結果進行基于冗余計算策略的錯誤檢測；基于多線程的線程檢錯和進程復算糾錯進行的復算方法。本發(fā)明的方法完全可應用于大規(guī)模海量數據的并行數字地形分析的高性能計算的容錯處理場合，例如，規(guī)則格網并行插值、坡度坡向并行計算、洼地填平并行計算等地形因子提取；可以應用于地理信息處理的高性能計算；也可以應用于基于地理信息的空間決策分析和數據挖掘等應用場合，提高處理效率。

技術領域

本發(fā)明屬于并行計算系統(tǒng)容錯的技術領域，涉及利用冗余策略對出錯的計算任務進行快速糾錯，特別提出一種面向數據并行計算容錯的快速并行復算方法。

背景技術

并行計算機系統(tǒng)的容錯處理是一個不容忽視的問題。一個并行系統(tǒng)是容錯的，指的是它的程序在出現邏輯故障的情況下仍然能夠正確的運行和保證得到正確的結果。

近年來，隨著計算機系統(tǒng)結構的復雜性增加，半導體制造工藝的發(fā)展，線寬的降低以及集成度的提高，從用戶桌面系統(tǒng)到分布式計算環(huán)境，乃至大規(guī)模并行計算機系統(tǒng)，功耗和可靠性問題都日漸突出。并行計算機系統(tǒng)的可靠性反映了系統(tǒng)為用戶提供預定服務的能力，可靠性的高低與系統(tǒng)故障率緊密相關。并行計算容錯技術的目的在于降低并行計算機系統(tǒng)的故障率，或者在一定故障率的前提下，提高系統(tǒng)能正確提供服務的概率。

容錯技術雖然多樣，但具有一個共同的本質，就是進行一定程度的冗余計算。所謂冗余計算是指在對關鍵任務進行多副本的同步計算。最基本的冗余包括時間冗余和空間冗余。時間冗余直觀地講就是復算，包括重復進行的計算和重復進行的通信，以及對多次計算結果的比較。空間冗余又可以細分為軟件冗余、硬件冗余和信息冗余。軟件冗余就是設置冗余的軟件模塊；硬件冗余就是設置冗余的硬件部件；而信息冗余就是通過使用附加的數據來描述某些內部狀態(tài)，通過對這些附加數據的考察就可以實現檢錯和容錯。

通過對現有的研究工作分析研究發(fā)現，目前國內外已有的并行系統(tǒng)的成果主要基于硬件冗余和軟件冗余機制，且主要用于故障檢測，而針對故障恢復機制的研究還很少。當前主流的軟件容錯策略面向時間冗余的方法，導致計算失敗的節(jié)點需要重新進行任務恢復，由于其恢復時間大于前一個檢查點和故障發(fā)生時刻之間的時間間隔，從而導致具有依賴關系的任務處于長時間的等待，而這些問題導致了并行效率降低以及計算資源的浪費。

發(fā)明內容

本發(fā)明針對上述問題，提出了一種基于多線程技術的檢錯與糾錯同時進行的錯誤快速恢復方法。

本發(fā)明的一種面向數據并行計算容錯的快速并行復算方法包括：

步驟1，讀入數據與數據分發(fā)：首先主節(jié)點的進程讀入數據，按照數據劃分策略，啟動相應的線程；然后，每個線程依據二次冗余計算策略，將每個數據塊分發(fā)給兩個從節(jié)點進程；

步驟2，冗余計算：從節(jié)點的每個進程按序計算某個數據塊的邏輯子塊，完成一個邏輯子塊后，發(fā)送結果給主節(jié)點的線程，若是最后一個邏輯子塊，則線程結束該數據塊的計算，否則，繼續(xù)執(zhí)行下一個邏輯子塊；

步驟3，錯誤檢測：主節(jié)點上的線程接收到兩個從節(jié)點的計算進程的邏輯子塊的計算結果后，立即進行該子塊的結果一致性檢查；若兩個子塊的計算結果一致，則執(zhí)行步驟6，線程融合子塊結果，否則計算結果有錯，則進入步驟4步啟動復算過程。若該子塊是該數據塊的最后一個子塊，則進入步驟7進行結果保存，否則線程等待接收下一個子塊的計算結果；

步驟4，重分發(fā)子塊：線程檢測到某個數據塊的邏輯子塊的結果有錯，則立即分發(fā)該出錯的邏輯子塊給一個從節(jié)點的計算進程，然后等待結果；

步驟5，子塊復算：從節(jié)點的進程接收到邏輯子塊后，發(fā)起該子塊的計算過程；計算完成后，進程將子塊的結果發(fā)給線程；