面向并行迭代計(jì)算的故障恢復(fù)技術(shù)研究.pdf

1、迭代方法求解線性方程組是工程技術(shù)應(yīng)用和科學(xué)研究的核心計(jì)算方法，目前迭代方法求解線性方程組都是在分布式計(jì)算系統(tǒng)上進(jìn)行，但伴隨著分布式系統(tǒng)中節(jié)點(diǎn)規(guī)模的擴(kuò)大，系統(tǒng)在運(yùn)行期間發(fā)生故障的概率也隨之增大。發(fā)生的故障同時(shí)包括失效停止的故障（硬故障）和失效繼續(xù)的故障（軟故障）。在迭代計(jì)算中基于算法的故障恢復(fù)技術(shù)是對(duì)這兩種故障進(jìn)行在線恢復(fù)的主流技術(shù)，但是基于算法的故障恢復(fù)技術(shù)對(duì)這兩種故障進(jìn)行在線恢復(fù)時(shí)都存在開銷大的問題。而開銷問題很大程度上限制了迭代計(jì)算

2、的應(yīng)用與發(fā)展，本文研究如何降低在線故障恢復(fù)產(chǎn)生的開銷，主要分為以下兩個(gè)方面:
　　第一，針對(duì)迭代計(jì)算時(shí)基于算法的硬故障恢復(fù)技術(shù)因?yàn)殡y以保證對(duì)所有節(jié)點(diǎn)實(shí)現(xiàn)在線故障恢復(fù)，以及無法保證對(duì)多節(jié)點(diǎn)同時(shí)失效時(shí)進(jìn)行在線故障恢復(fù)，從而導(dǎo)致產(chǎn)生開銷大的問題。本文在基于算法的硬故障恢復(fù)技術(shù)的基礎(chǔ)上提出基于信息冗余的硬故障恢復(fù)技術(shù)，該技術(shù)在迭代計(jì)算時(shí)通過額外的多傳遞一份數(shù)據(jù)給別的計(jì)算節(jié)點(diǎn)，使整個(gè)迭代計(jì)算在迭代時(shí)保證每個(gè)節(jié)點(diǎn)都能在整個(gè)迭代計(jì)算系統(tǒng)中存在多

3、個(gè)備份。當(dāng)多個(gè)節(jié)點(diǎn)同時(shí)失效時(shí)，失效節(jié)點(diǎn)可以從沒有失效節(jié)點(diǎn)上獲取正確數(shù)據(jù)繼續(xù)進(jìn)行計(jì)算。雖然基于信息冗余的硬故障恢復(fù)技術(shù)在數(shù)據(jù)傳遞時(shí)產(chǎn)生了一定的額外開銷，然而這種額外開銷是很小的甚至可以忽略不計(jì)，但是基于信息冗余的硬故障恢復(fù)技術(shù)不僅保證了對(duì)所有節(jié)點(diǎn)實(shí)現(xiàn)在線故障恢復(fù)，而且保證對(duì)多節(jié)點(diǎn)同時(shí)失效時(shí)進(jìn)行在線故障恢復(fù)。避免了因無法實(shí)現(xiàn)在線對(duì)多節(jié)點(diǎn)同時(shí)失效進(jìn)行故障恢復(fù)而重新計(jì)算，導(dǎo)致產(chǎn)生巨大的時(shí)間開銷問題。
　　第二，在迭代計(jì)算中基于算法的軟故障

4、恢復(fù)技術(shù)通過采用做檢測(cè)點(diǎn)和檢查點(diǎn)實(shí)現(xiàn)對(duì)軟故障進(jìn)行在線故障恢復(fù)，但是存在難以科學(xué)設(shè)置檢測(cè)點(diǎn)和檢查點(diǎn)間隔而導(dǎo)致開銷大的問題。本文基于檢查點(diǎn)和檢測(cè)點(diǎn)的開銷的不同，以檢測(cè)點(diǎn)和檢查點(diǎn)的間隔時(shí)間為變量，利用馬爾科夫鏈構(gòu)建計(jì)算任務(wù)在有故障情況下的完成時(shí)間估計(jì)模型，得到最優(yōu)的檢查點(diǎn)間隔和檢測(cè)點(diǎn)間隔的求解試，進(jìn)而在最低開銷下實(shí)現(xiàn)對(duì)軟故障的在線冗余。通過實(shí)驗(yàn)表明，針對(duì)不同的故障率以及任務(wù)長(zhǎng)度，檢測(cè)點(diǎn)和檢查點(diǎn)間隔優(yōu)化后的基于算法的軟故障恢復(fù)技術(shù)與傳統(tǒng)基于算法