?

面向分布式流體系結(jié)構(gòu)的多副本積極容錯技術(shù)*

通信地址：410073 湖南省長沙市國防科學技術(shù)大學高性能計算國家重點實驗室Address:The State Key Laboratory of High Performance Computing,National University of Defense Technology,Changsha 410073,Hunan,P.R.China

李鑫1,3,4，林宇斐2，郭曉威1

(1.國防科學技術(shù)大學高性能計算國家重點實驗室，湖南 長沙 410073；2.國防科學技術(shù)大學研究生院，湖南 長沙 410073；

3.解放軍理工大學，江蘇 南京 210007；4.總參第六十三研究所，江蘇 南京 210007)

摘要：隨著互聯(lián)網(wǎng)環(huán)境下計算系統(tǒng)規(guī)模的不斷擴大，分布式流體系結(jié)構(gòu)的可靠性問題面臨著嚴峻的挑戰(zhàn)。以多模冗余容錯技術(shù)為基礎，針對軟錯誤提出了一種面向分布式流體系結(jié)構(gòu)的多副本積極容錯技術(shù)TREFT，利用三個程序副本進行高效的檢錯與糾錯。在分布式流體系結(jié)構(gòu)原型系統(tǒng)上的實驗結(jié)果表明，該技術(shù)能有效提高系統(tǒng)的可靠性，具有較低的容錯成本，平均增加10.77%的容錯開銷。

關(guān)鍵詞：分布式流體系結(jié)構(gòu)；容錯技術(shù)；三模冗余

1引言

互聯(lián)網(wǎng)環(huán)境資源規(guī)模巨大，通信環(huán)境復雜，各種網(wǎng)絡資源呈現(xiàn)異構(gòu)性與動態(tài)性。隨著商用器件的廣泛使用、計算系統(tǒng)規(guī)模的持續(xù)擴大與異構(gòu)系統(tǒng)的興起流行，互聯(lián)網(wǎng)分布式計算模型的可靠性問題面臨著嚴峻挑戰(zhàn)。作者近期提出了一種新型的分布式流體系結(jié)構(gòu)DSA(Distributed Stream Architecture)，在互聯(lián)網(wǎng)環(huán)境下提供高效的大數(shù)據(jù)計算環(huán)境，其可靠性面臨著同樣的問題。

近年來，面向互聯(lián)網(wǎng)應用的數(shù)據(jù)中心的計算系統(tǒng)規(guī)模在持續(xù)增加，如2015年6月TOP500前10名系統(tǒng)的平均處理器核數(shù)已經(jīng)突破83.7萬顆[1]，并繼續(xù)向百萬顆邁進。隨著系統(tǒng)計算部件數(shù)目的增加，計算系統(tǒng)的可靠性將會持續(xù)下降，如IBM ASCI White平均無故障時間僅為40個小時[2]，Google擁有的8 000個節(jié)點的集群系統(tǒng)平均36個小時發(fā)生一個故障[3]，超過10萬個處理器核的IBM Blue Gene/L的平均無故障時間預測可能只有幾十分鐘[4]。據(jù)美國Los Alamos國家實驗室10年超級計算機系統(tǒng)的統(tǒng)計數(shù)據(jù)顯示，高性能計算機單個節(jié)點的平均故障率為1/(512 h)[5，6]，這意味著128個節(jié)點系統(tǒng)的平均無故障時間僅為4小時。

同時，采用異構(gòu)系統(tǒng)加速應用程序已成為一種新型的計算模式，具有較高的效能比，如CPU-GPU與CPU-MIC典型系統(tǒng)，已經(jīng)成功應用在Tianhe-1A[7，8]與Tianhe-2等系統(tǒng)中。然而，作為異構(gòu)系統(tǒng)的加速部件，其強大的計算能力來源于更高的芯片集成度與簡單的控制邏輯，目前硬件尚未提供強大的容錯支持，顯然會帶來嚴重的可靠性問題[9，10]。例如，60個NVIDIA GeForce 8800 GTS GPU同時連續(xù)工作72小時就會發(fā)生7個GPU故障，同時GPU故障都發(fā)生在存儲器，且不易被感知[11]。

因此，對于在互聯(lián)網(wǎng)上運行長達幾個小時甚至幾天的應用來說，保證程序在分布式環(huán)境下的可靠運行顯得尤為重要，如蛋白質(zhì)折疊應用計算就需要連續(xù)運算幾個月時間[12]。分布式系統(tǒng)容錯技術(shù)主要基于空間冗余、時間冗余或數(shù)據(jù)世系等方法來實現(xiàn)?？臻g冗余進一步可劃分為硬件冗余、軟件冗余、數(shù)據(jù)冗余等。Hadoop中的分布式文件系統(tǒng)HDFS中采用的是多副本數(shù)據(jù)的軟件冗余方法，以保證在大規(guī)模廉價PC服務器上提供可靠的數(shù)據(jù)訪問能力。已有研究[13]表明，多副本容錯技術(shù)是一種針對大規(guī)模計算的有效手段。Google提出的數(shù)據(jù)糾刪碼技術(shù)就是一種典型的數(shù)據(jù)冗余方法[14]。時間冗余方式主要包括回滾恢復技術(shù)與并行復算技術(shù)等，傳統(tǒng)高性能計算領域經(jīng)常采用基于檢查點的回滾恢復技術(shù)來處理故障。數(shù)據(jù)世系方法通過記錄數(shù)據(jù)之間的關(guān)系與操作，一旦發(fā)生錯誤就從最近數(shù)據(jù)記錄點開始恢復計算，具有較高的容錯效率，已經(jīng)被應用在Spark[15]等大數(shù)據(jù)技術(shù)中。

本文基于分布式流體系結(jié)構(gòu)的特點，針對節(jié)點故障引起的不易察覺的軟錯誤，設計了一種多副本積極容錯技術(shù)，將需要進行檢錯的程序區(qū)域標識為容錯程序段，通過三個程序副本比較其數(shù)據(jù)變量以發(fā)現(xiàn)可能的錯誤。本文的主要創(chuàng)新工作在第3節(jié)與第4節(jié)，其中，第2節(jié)概述了分布式流體系結(jié)構(gòu)[16]，對節(jié)點發(fā)生瞬時故障引起的軟錯誤進行了分析;第3節(jié)詳細說明了多副本積極容錯技術(shù);第4節(jié)描述了實驗方法與結(jié)果分析;第5節(jié)是本文總結(jié)與研究展望。

2分布式流體系結(jié)構(gòu)概述及其故障分析

2.1　分布式流體系結(jié)構(gòu)概述

分布式流體系結(jié)構(gòu)在分布式環(huán)境下擴展了傳統(tǒng)流體系結(jié)構(gòu)中的概念，其中，計算核心(Kernel)是指可用的軟硬件對象，流或數(shù)據(jù)流(Stream)是指計算數(shù)據(jù)與控制狀態(tài)數(shù)據(jù)。流包括計算數(shù)據(jù)流和控制數(shù)據(jù)流，計算核心根據(jù)其功能分為六種：軟計算核心SK(Soft Kernel)、硬計算核心HK(Hard Kernel)、應用計算核心AK(Application Kernel)、客戶管理計算核心CMK(Client Management Kernel)、資源管理計算核心RMK(Resource Management Kernel)與服務管理計算核心SMK(Service Management Kernel)[16]。其中，SK與HK分別封裝了軟件資源與硬件資源信息，AK封裝了主程序相關(guān)信息，負責資源申請與管理程序運行過程，CMK負責提供用戶服務接口，RMK負責命令解釋與任務具體執(zhí)行，SMK維護服務、計算核心等元信息，提供資源調(diào)度與應用生命周期管理等[17]。

如圖1所示，在分布式流體系結(jié)構(gòu)上運行一個應用程序通常需要1個host節(jié)點與多個device節(jié)點。

Figure 1　Basic concepts of the distributed stream architecture圖1　分布式流體系結(jié)構(gòu)基本概念

host節(jié)點上RMK會啟動一個線程執(zhí)行主程序(AK)以管理任務執(zhí)行流程。AK會根據(jù)編譯指導命令將計算核心任務劃分成多個子任務并行執(zhí)行。同時，AK負責向SMK申請軟硬件資源，申請成功后通知目的節(jié)點下載代碼與數(shù)據(jù)，并在計算完畢后更新計算狀態(tài)，以保證全局信息的一致性。AK如此推進計算過程直到所有計算核心執(zhí)行完畢。

2.2　分布式流體系結(jié)構(gòu)故障分析

在分布式流體系結(jié)構(gòu)中，按照錯誤在程序執(zhí)行中產(chǎn)生的原因可以分為原生節(jié)點錯誤與繼生節(jié)點錯誤兩類：

(1)原生節(jié)點錯誤：由于節(jié)點硬件故障等直接造成的錯誤，使得系統(tǒng)存儲數(shù)據(jù)的數(shù)值與正確值之間出現(xiàn)了影響結(jié)果正確性的偏差。

(2)繼生節(jié)點錯誤：由于與其他錯誤數(shù)據(jù)之間存在數(shù)據(jù)依賴關(guān)系而隨著程序執(zhí)行傳播產(chǎn)生的錯誤，造成系統(tǒng)存儲數(shù)據(jù)的數(shù)值與正確值之間出現(xiàn)了影響結(jié)果正確性的偏差。

分布式流體系結(jié)構(gòu)上運行的Kernel函數(shù)是具有數(shù)據(jù)并行性的計算程序，通常以線程級并行方式或任務級并行方式運行在遠程節(jié)點上，本文將Kernel函數(shù)調(diào)用語句稱為并行計算核心(并行Kernel)。同時，主程序串行運行在本地節(jié)點上，本文將非Kernel函數(shù)調(diào)用的執(zhí)行語句統(tǒng)稱為串行計算核心(串行Kernel)。因此，這些計算核心錯誤間的傳播關(guān)系如圖2所示。

Figure 2　Serial Kernel errors and parallel Kernel errors圖2　串行Kernel錯誤與并行Kernel錯誤

可見，分布式流計算程序節(jié)點錯誤的傳播途徑主要是通過程序語句執(zhí)行在節(jié)點內(nèi)傳播或通信語句在節(jié)點間傳播。本文假設主程序運行的節(jié)點是可靠的，即不考慮串行Kernel原生節(jié)點錯誤，只關(guān)心并行Kernel相關(guān)錯誤導致的主程序失效問題。

本文提出的容錯技術(shù)是在系統(tǒng)發(fā)生故障的情況下，仍然可以保證程序的正確運行，主要針對節(jié)點硬件故障引起的不易察覺的軟錯誤(Soft Error)，在錯誤傳播期間對其進行檢測與恢復，以防止系統(tǒng)出現(xiàn)失效，其故障模型如圖3所示。該類軟錯誤是指運行并行Kernel的節(jié)點發(fā)生瞬時故障所引起的程序員不易察覺的軟錯誤，不會立即導致程序失效，而是通過程序語句執(zhí)行傳播影響其他正常數(shù)據(jù)而出現(xiàn)新的錯誤，并最終在主程序中繼續(xù)傳播而導致其失效。這類軟錯誤由于不易察覺，檢錯比較困難，本文考慮基于空間冗余方式對比數(shù)據(jù)以檢錯與糾錯。

Figure 3　Fault model of the instantaneous fault occurred in the parallel Kernel nodes圖3　并行Kernel節(jié)點發(fā)生瞬時故障的故障模型

3面向分布式流體系結(jié)構(gòu)的多副本積極容錯技術(shù)：TREFT

多副本積極容錯技術(shù)是一種主動的空間冗余容錯方法，又稱為多模冗余NMR(N-Modular Redundancy)方法，即多個相同程序副本以空間并行的方式同時執(zhí)行，當程序執(zhí)行遇到同步點時，程序會主動比較多個副本數(shù)據(jù)進行檢錯，遵循“用三取二”方法選擇多數(shù)相同的結(jié)果，并對錯誤的數(shù)據(jù)進行糾錯，以防止錯誤進一步傳播。目前有研究[17]表明，當單個副本程序的可靠性達到80%時，三模冗余容錯方法的系統(tǒng)可靠性就可以達到90%以上?？紤]到容錯成本開銷以及容錯技術(shù)實現(xiàn)的復雜性，本文多副本容錯技術(shù)采用三模冗余積極容錯技術(shù)TREFT(Triple modular Redundancy Eager Fault-tolerant Technique)。

TREFT通過比較三個程序副本活躍變量數(shù)據(jù)的一致性，從而有效檢測出故障引起或正在傳播的不易被發(fā)現(xiàn)的軟錯誤。假設錯誤是隨機出現(xiàn)的，若計算核心重新執(zhí)行時，則本文認為出現(xiàn)相同錯誤的概率很低，一般可以獲得正確的輸出數(shù)據(jù)。由于兩個以上獨立程序副本運行同時出錯的概率非常小，因此，本文對于兩個(含)以上副本同時出現(xiàn)錯誤的情況不予考慮。

3.1　TREFT基本概念

本文中TREFT進行容錯的對象是Kernel函數(shù)的輸出數(shù)據(jù)，因此，需要對包含Kernel函數(shù)的程序段標識成容錯程序段，以便于進行檢錯與糾錯處理，其基本概念定義如下：

定義1

(1)起始同步點：標記容錯程序范圍的起始位置；

(2)比較同步點：標記容錯程序范圍的結(jié)束位置，同時也是執(zhí)行同步操作的位置，在該位置上將數(shù)據(jù)發(fā)送到其他副本節(jié)點上進行數(shù)據(jù)比較。

定義2

(1)容錯程序段：主程序中需要進行容錯的程序語句序列，一般使用起始同步點與比較同步點標記容錯程序的范圍，包含多個串行語句與Kernel函數(shù)調(diào)用語句。一個Kernel函數(shù)調(diào)用語句就可以構(gòu)成一個基本的容錯程序段。

(2)非容錯程序段：主程序中容錯程序段之間的程序語句序列，執(zhí)行時不會產(chǎn)生本節(jié)定義的軟錯誤，因此不需要進行容錯處理。

(3)容錯程序段活躍變量：是指由容錯程序段包含的Kernel函數(shù)調(diào)用語句中進行定值操作的流變量，其在后面的程序執(zhí)行時可能被引用，若這些變量發(fā)生錯誤而沒有進行糾錯，則會形成錯誤的傳播。

如圖4所示，程序員或編譯器需要在容錯程序段的前后分別插入起始同步點與比較同步點進行標記。容錯程序段可以將錯誤傳播的范圍控制在一個有限的程序區(qū)域內(nèi)，使得錯誤不會傳播出所在的容錯程序段而影響其他部分。即使出現(xiàn)軟錯誤，程序只需要重新糾正錯誤的活躍變量，而不需要重新執(zhí)行程序，從而降低容錯開銷。

Figure 4　Schematic diagram of the related concepts of the fault-tolerant program section in the TREFT圖4　TREFT容錯程序段相關(guān)概念示意圖

TREFT中各節(jié)點的表決器模塊使用“用三取二”多數(shù)判決邏輯準則對錯誤數(shù)據(jù)進行判定：

(1)正常情況下三個副本數(shù)據(jù)都是相同的，則使用各自程序結(jié)果作為正確輸出；

(2)若任何一個程序副本出錯，其輸出不同于其他兩個程序副本，則表決器采用多數(shù)程序副本的數(shù)據(jù)結(jié)果作為正確結(jié)果進行故障恢復，即對該錯誤活躍變量直接進行賦值，防止錯誤進一步傳播。

3.2　TREFT容錯程序段設置規(guī)則

容錯程序段的設置是TREFT同步技術(shù)的關(guān)鍵問題，會影響程序容錯粒度與容錯開銷，根據(jù)分布式流應用的程序語句類型的特點，TREFT中包括五個基本設置規(guī)則：

規(guī)則1Write操作之前必須設置容錯程序段以保證其輸入變量的正確性。因為Write操作在主程序中接收錯誤數(shù)據(jù)，為了主程序不失效，所以在數(shù)據(jù)傳回主程序之前進行容錯，Write操作涉及的數(shù)據(jù)也屬于活躍變量，該規(guī)則保證錯誤不會繼續(xù)在主程序中傳播。

規(guī)則2所有Kernel函數(shù)調(diào)用語句都必須處于容錯程序段中。顯然，本節(jié)假設的錯誤都發(fā)生在運行并行Kernel的節(jié)點上，即對應于主程序中Kernel函數(shù)執(zhí)行過程，該規(guī)則保證TREFT對所有可能發(fā)生的并行Kernel原生錯誤都進行了容錯處理。

規(guī)則3每個Kernel并行執(zhí)行模式[16]中的所有Kernel函數(shù)調(diào)用語句必須處于同一個容錯程序段中。由于這些Kernel函數(shù)調(diào)用語句都是并行執(zhí)行的，即以空間并行或時間并行的方式運行多個相鄰的Kernel，所以無法確定它們之間的真實執(zhí)行順序，而該規(guī)則保證了其并行執(zhí)行語義。

規(guī)則4采用數(shù)據(jù)流Eager傳輸策略[16]而提前傳輸?shù)臄?shù)據(jù)必須在數(shù)據(jù)原本所在的容錯程序段內(nèi)進行檢錯與糾錯，如果提前傳輸?shù)臄?shù)據(jù)發(fā)生錯誤，則需要進行重傳，從而保證了后繼Kernel計算的正確性。

規(guī)則5設置合理容錯粒度的容錯程序段。若以主程序中的每個計算核心為容錯粒度，容錯粒度過小，同步點設置過密，就會引發(fā)頻繁的檢錯糾錯操作，數(shù)據(jù)傳輸操作過多，致使容錯執(zhí)行效率不高，因此，應該盡可能合并可以一次容錯的語句。

3.3　TREFT容錯機制實現(xiàn)方法

本文在分布式流體系結(jié)構(gòu)編程模型中設計了TREFT容錯起始同步點與比較同步點的語法，即

#pragma brs treftsyn startProgramCode

#pragma brs treftsyn finish

該編譯指導語句使用在需要進行容錯的程序段開始處和結(jié)尾處，其語義是指該范圍內(nèi)的語句序列是容錯程序段，當程序運行到比較同步點時，需要執(zhí)行TREFT檢錯與糾錯流程。編譯器對所有人工標記的容錯程序段進行標識，生成容錯程序段索引表以及包含的計算核心與對應的輸出活躍變量，并為每個容錯程序段創(chuàng)建一個事件消息隊列用于接收相關(guān)容錯處理的消息。

如圖5所示案例，存在三個程序副本TR1、TR2與TR3，例如每個程序副本的host節(jié)點上都創(chuàng)建了1個執(zhí)行線程(Executor Thread)執(zhí)行主程序(AK代碼)，由其進一步創(chuàng)建1個工作線程(Worker Thread)與1個子任務工作線程(Subworker Thread)管理任務的執(zhí)行過程，同時在1個device節(jié)點上創(chuàng)建了執(zhí)行線程用于執(zhí)行計算核心代碼(SK)。其中，host節(jié)點上：

Figure 5　Schematic diagram of the runtime that supports the TREFT fault-tolerant technique圖5　支持TREFT容錯技術(shù)的運行時結(jié)構(gòu)示意圖

(1)Executor Thread：運行主程序(AK代碼)以管理整個程序的執(zhí)行過程，并依次按照指定的語義執(zhí)行Kernel計算任務；

(2)Worker Thread：執(zhí)行對Kenrel計算任務的相關(guān)操作，包括請求下載與執(zhí)行代碼等，負責監(jiān)控任務狀態(tài)與更新全局信息列表，以保證數(shù)據(jù)一致性；

(3)Subworker Thread：負責執(zhí)行子任務的所有相關(guān)操作以及狀態(tài)監(jiān)控，當程序劃分為多個任務執(zhí)行時，編譯器運行時中會創(chuàng)建相應數(shù)目的線程來維持子任務的運行；

(4)device節(jié)點上Executor Thread：負責直接執(zhí)行計算核心的子任務，包括下載數(shù)據(jù)與代碼、啟動執(zhí)行子任務等。

不同工作線程之間是通過事件消息隊列來傳遞信息的，工作線程(Worker Thread)與子任務工作線程(Subworker Thread)的事件消息隊列分別記作wq與cq。如圖5所示，為了支持TREFT容錯機制，分布式流體系結(jié)構(gòu)的運行時組織結(jié)構(gòu)添加了容錯監(jiān)控線程(Fault-Tolerant Monitor Thread)與相應的事件消息隊列(Fault-Tolerant Queue)，其中：

(1)Fault-Tolerant Monitor Thread：是主程序執(zhí)行線程創(chuàng)建的TREFT容錯監(jiān)控工作線程，負責與其他副本的容錯監(jiān)控線程同步、請求交換數(shù)據(jù)、請求檢錯與糾錯等。當三個副本的容錯監(jiān)控線程互相同步且都準備好時，則本地容錯監(jiān)控線程將請求檢錯與糾錯的事件操作壓入對應的工作線程事件消息隊列進行處理，并由子任務工作線程負責執(zhí)行數(shù)據(jù)交換與檢錯糾錯任務。

(2)Fault-Tolerant Queue：用于接收其他副本容錯監(jiān)控線程與計算核心工作線程反饋的消息，并進一步交給容錯監(jiān)控線程處理，并記為fq。

本文采用一種線程操作表的偽代碼方法來描述TREFT實現(xiàn)與執(zhí)行細節(jié)，如表2所示。假設存在計算核心K1劃分為3個子任務K1i執(zhí)行，1≤i≤3且i為正整數(shù)，使用K1i.OP表示計算核心子任務K1i執(zhí)行操作OP，用ex(OP)表示指定線程執(zhí)行操作OP，wq.p(OP)表示事件消息隊列wq壓入操作OP并進行處理。

Table 1　Operation list of Kernel and Stream in the TREFT

如表2所示，存在兩個串行執(zhí)行的計算核心K1與K2，并對其進行檢錯與糾錯，KR表示容錯監(jiān)控線程，最右邊一列表示各線程事件執(zhí)行的大致順序。TREFT容錯機制中檢錯與糾錯過程是一個阻塞事件過程，只有結(jié)束后才能繼續(xù)執(zhí)行程序，整個TREFT容錯機制的主要運行流程如下：

(1) 當程序執(zhí)行到標記同步點時，三個副本程序創(chuàng)建各自的容錯監(jiān)控線程，同時傳遞容錯程序段索引號給該線程，以便于容錯監(jiān)控線程可以在容錯程序段索引表里檢索相應Kernel的活躍變量信息，同時監(jiān)視容錯程序段中Kernel任務的執(zhí)行狀態(tài)，如圖5和表2中①所示。

(2) 當程序執(zhí)行到比較同步點時，由于在TREFT容錯模式下，所有計算核心執(zhí)行完畢后阻塞等待并不立即退出，而是將計算任務狀態(tài)通知給工作線程與容錯監(jiān)控線程，如圖5和表2中②與③所示。

(3) 當監(jiān)測到容錯程序段中所有Kernel計算完畢時，容錯監(jiān)控線程向其他兩個副本的容錯監(jiān)控線程發(fā)送初始化同步操作OPRS，得到兩者回復才可以確認三個副本都已經(jīng)到達同步點。由于同一時刻只有一個容錯程序段處于運行狀態(tài)，因此，通過容錯程序段索引號保證只有一個容錯程序段進行處理。接著，三個副本之間同步需要檢錯的資源信息，包括其他兩個副本程序活躍變量信息所在的節(jié)點信息，并將對應信息更新到各自的全局信息列表中，如圖5和表2中④所示。

Table 2　Thread operations in the TREFT fault-tolerant technique

(4) 當數(shù)據(jù)同步結(jié)束后，容錯監(jiān)控線程將數(shù)據(jù)檢錯糾錯操作OPTR壓入對應的計算核心Kernel工作線程的事件消息隊列進行處理，如圖5和表2中⑤所示。

(5) 對應Kernel工作線程接收OPTR操作后，通過子任務工作線程請求其他兩個副本程序傳輸活躍變量數(shù)據(jù)到指定副本程序綁定的節(jié)點上，由該節(jié)點上的RMK啟動數(shù)據(jù)檢錯與糾錯任務，并在執(zhí)行結(jié)束后通知子任務工作線程，如圖5和表2中⑥所示。

(6) 子任務工作線程將容錯操作結(jié)果OPTF反饋給工作線程，當所有子任務完成后，工作線程通知容錯監(jiān)控線程當前計算核心已經(jīng)完成了容錯操作OPTF，如圖5和表2中⑦所示。當容錯程序段中所有Kernel都完成容錯操作時，容錯監(jiān)控線程再一次與其他兩個副本執(zhí)行完成容錯的同步操作OPRFS，如圖5和表2中⑧所示，并通知所有Kernel計算完成結(jié)束工作線程操作OPET，如圖5和表2中⑨所示。

(7) 執(zhí)行線程等待容錯程序段所有計算核心結(jié)束，并在最后阻塞等待容錯監(jiān)控線程結(jié)束，以確保程序執(zhí)行語義的正確性，如表2中⑩所示。

4實驗驗證

4.1　實驗方法

整個實驗評估是在由20個節(jié)點組成的互連網(wǎng)絡上完成的，每個節(jié)點由一個多核CPU組成，實驗平臺參數(shù)如表3所示。分布式流體系結(jié)構(gòu)實驗原型系統(tǒng)由C/C++語言實現(xiàn)，主要包括編譯器以及資源管理等，可以支持多種計算資源與編程語言，包括GPU(Brook+、OpenCL、CUDA等)、CPU(C/C++等)等，支持多個Kernel并行執(zhí)行，能有效開發(fā)程序的線程級并行性與任務級并行性。

實驗測試用例采用NASGridBenchmarks(NGB)中的HelicalChain(HC)、VisualizationPipe(VP)與MixedBag(MB)三個用例，如圖6所示，測試用例都是由單個NPB實例求解器(BT，SP，LU，MG或FT)組成的串行流處理模式，MF過濾器用于轉(zhuǎn)換不同實例求解器之間的數(shù)據(jù)，實驗測試用例選定反復執(zhí)行2次流程。本文將實例求解器與對應的過濾器封裝為一個計算核心，所有計算核心都按照順序依次執(zhí)行，并移植到分布式流體系結(jié)構(gòu)上，并通過模擬的方法產(chǎn)生原始輸入數(shù)據(jù)，如圖6所示執(zhí)行流程。

Table 3　Parameter list of the experimental platform

Figure 6　Schematic diagram of the computing process in test case VP,MB and HC圖6　實驗測試用例VP、MB與HC的計算流程示意圖

本文實驗中國際互聯(lián)網(wǎng)模擬環(huán)境的延時采用Internet Traffic Report網(wǎng)站在2015年統(tǒng)計的五大洲延遲時間平均值100 ms，國際互聯(lián)網(wǎng)帶寬則采用Speedtest在2013年180多個國家與地區(qū)測量帶寬平均值13.98 Mbps，其余時間都采用實際測試的時間，所有測試用例采用A與B兩個規(guī)模級別的測試集。三個測試用例的控制依賴關(guān)系較為簡單，因此，實驗中TREFT版本將程序標識成一個粒度較大的TREFT容錯程序段。本文設計了兩個對比實驗版本TREFT-E1與TREFT-E2，其中TREFT-E1是在TREFT容錯程序版本的基礎上分別采用了數(shù)據(jù)流Eager傳輸優(yōu)化策略[16]，可以主動傳輸數(shù)據(jù)，考察優(yōu)化技術(shù)對TREFT容錯技術(shù)的影響;TREFT-E2則以單個計算核心Kernel為TREFT容錯程序段，其每個容錯程序段的容錯粒度較小，考察不同容錯粒度下對容錯開銷的影響。

4.2　實驗結(jié)果

如圖7所示，采用TREFT容錯技術(shù)后各測試用例平均增加10.77%的容錯開銷，并呈現(xiàn)出VP、MB與HC增加容錯開銷依次減小的趨勢，其中，VP.B(20.03%)、VP.A(10.20%)與MB.B(10.12%)增加的容錯開銷均在10%以上。這是由于VP和MB測試用例中FT計算核心的活躍變量數(shù)據(jù)量較大，由于模擬的互聯(lián)網(wǎng)帶寬受限，所以造成通信時間成為TREFT容錯同步過程的瓶頸。同時，HC測試用例中LU計算核心活躍變量的數(shù)據(jù)量較小，通信時間占據(jù)其整個執(zhí)行時間比例開銷較小，從而使得增加的容錯開銷較小。

當測試用例采用數(shù)據(jù)流Eager傳輸優(yōu)化策略時，數(shù)據(jù)會盡可能主動傳輸?shù)侥繕斯?jié)點上，因此可以減少程序執(zhí)行時間。如圖7所示，TREFT-E1版本通常增加的容錯開銷較小(平均13.05%左右)，比原始TREFT版本平均增加了2.28%的開銷比例。VP.B(25.6%)是容錯開銷比例較大的測試用例。在采用性能優(yōu)化技術(shù)后，VP和MB中容錯同步的數(shù)據(jù)通信開銷與檢測開銷沒變，而程序整體執(zhí)行時間減少，因此造成容錯開銷所占比例進一步增加。HC容錯開銷比例沒有顯著增加，這是由于HC中各個計算核心串行連續(xù)執(zhí)行，采用數(shù)據(jù)流Eager傳輸策略后整體執(zhí)行時間沒有顯著減少，因此，HC增加的容錯開銷不顯著。

由此可見，TREFT容錯技術(shù)可以有效支持數(shù)據(jù)流Eager傳輸優(yōu)化技術(shù)，且采用后增加的容錯開銷(2.28%)比例較小，具有較高的容錯效率。

TREFT-E2版本采用了計算核心級別的細粒度TREFT容錯方法，如圖7所示，各測試用例的容錯開銷平均增加52.77%，大約是正常TREFT增加開銷的5倍，其中VP.A(69.12%)、VP.B(67.17%)、MB.A(54.39%)與HC.B(50.31%)增加的容錯開銷超過了50%。這是由于這些測試用例活躍變量的數(shù)據(jù)量較大，容易使得數(shù)據(jù)傳輸與檢錯成為容錯同步過程的瓶頸。同時，HC.A(36.53%)與MB.B(38.09%)測試用例增加的容錯開銷相對較小，HC.A中活躍變量數(shù)據(jù)總和較小，容錯同步需要的數(shù)據(jù)傳輸與比較時間較短，而MB.B的執(zhí)行時間較長，因此使得其增加的容錯開銷比例沒有其他情況高。

Figure 7　Percentage of the fault-tolerant overhead increased after using the TREFT in test case VP,MB and HC圖7　測試用例在使用TREFT后的容錯開銷增加百分比

由此可見，當TREFT容錯粒度過小時，容錯操作頻繁會造成較低的容錯效率，當程序變得更加復雜時，隨著TREFT容錯程序段數(shù)目的增加，需要進行容錯同步的數(shù)據(jù)量逐漸增大，這種趨勢會愈加明顯。

綜上所述，TREFT容錯技術(shù)具有較低的容錯開銷和良好的容錯特性，可以有效提高分布式流體系結(jié)構(gòu)下應用程序執(zhí)行的可靠性。

5結(jié)束語

隨著計算系統(tǒng)規(guī)模的持續(xù)擴大，分布式流體系結(jié)構(gòu)中的可靠性問題面臨著非常嚴峻的挑戰(zhàn)。本文以多模冗余容錯技術(shù)為基礎，提出了一種面向分布式流體系結(jié)構(gòu)的多副本積極容錯技術(shù)TREFT，在分布式流體系結(jié)構(gòu)原型系統(tǒng)上的實驗結(jié)果表明，該技術(shù)能有效提高系統(tǒng)的可靠性，且具有較低的容錯開銷。

未來的研究將在已有研究基礎上，通過數(shù)據(jù)流方法分析分布式流體系結(jié)構(gòu)中的錯誤傳播行為特點，構(gòu)建數(shù)據(jù)流方程來刻畫錯誤傳播行為，以指導分布式流體系結(jié)構(gòu)的容錯技術(shù)研究，設計高效的容錯算法，盡可能比較最小的錯誤數(shù)據(jù)集合，從而進一步減少容錯開銷。

參考文獻:附中文

[1]Meuer H,Simon H,Strohmaier E,et al. TOP500 supercomputer sites[EB/OL].[2015-09-01]. http://www.top500.org．

[2]Lu C-D. Scalable diskless checkpointing for large parallel systems[D]. Urbana-Champaign:University of Illinois,2005．

[3]Bosilca G,Bouteiller A,Cappello F,et al. MPICH-V:Toward a scalable fault tolerant MPI for volatile nodes[C]∥Proc of SC’02,2002:1-18．

[4]Engelmann C,Geist A. A diskless checkpointing algorithm for super-scale architectures applied to the fast Fourier transform[C]∥Proc of the 1st International Workshop on Challenges of Large Applications in Distributed Environments,2003:47-52．

[5]Los Alamos National Laboratory. Operational data to support and enable computer science research[EB/OL]. [2015-09-01]. http://institute.lanl.gov/data/lanldata.shtml．

[6]Wu M,Sun X-H,Jin H. Performance under failures of high-end computing[C]∥Proc of the 2007 ACM/IEEE Conference on Supercomputing,2007:1-11．

[7]Yang X,Liao X,Xu W,et al. TH-1:China’s first petaflop supercomputer[J]. Frontiers of Computer Science in China,2010,4(4):445-455．

[8]Yang X-J,Liao X-K,Lu K,et al. The TianHe-1A supercomputer:Its hardware and software[J]. Journal of Computer Science and Technology,2011,26(3):344-351．

[9]Borucki L,Schindlbeck G,Slayman C. Comparison of accelerated DRAM soft error rates measured at component and system level[C]∥Proc of the 2008 IEEE International Reliability Physics Symposium,2008:482-487．

[10]Schroeder B,Pinheiro E,Weber W-D. DRAM errors in the wild:A large-scale field study[C]∥Proc of the 11th International Joint Conference on Measurement and Modeling of Computer Systems,2009:193-204．

[11]Maruyama N,Nukada A,Matsuoka S. Software-based ECC for GPUS[C]∥Proc of the 2009 Symposium on Application Accelerators in High Performance Computing (SAAHPC’09),2009:1．

[12]Bronevetsky G,Marques D,Pingali K,et al. Automated application-level checkpointing of MPI programs[C]∥Proc of the Symposium on Principles and Practice of Parallel Programming (PPoPP 2003),2003:84-94．

[13]Wang Z Y,Yang X J,Zhou Y.Scalable triple modular redundancy fault tolerance mechanism for MPI-oriented large scale parallel computing[J]. Journal of Software,2012,23(4):1022-1035. (in Chinese)

[14]Plank J S. A tutorial on reed-solomon coding for fault-tolerance in RAID-like systems[J]. Software-Practice & Experience,1997,27(9):995-1012．

[15]Zaharia M,Chowdhury M,Das T,et al. Resilient distributed datasets:A fault-tolerant abstraction for in-memory cluster computing [C]∥Proc of the 9th USENIX Conference on Networked Systems Design and Implementation. USENIX Association,2012:1．

[16]Li Xin,Guo Xiao-wei,Lin Yu-fei. Stream eager transmission:The performance optimization technique for the distributed stream architecture[J]. Computer Engineering & Science,2015,37(11):2035-2044.(in Chinese)

[17]Song W. Research on fault tolerance for transactional memory system[D]. Changsha:National University of Defense Technology,2011. (in Chinese)

[13]王之元，楊學軍，周云. 大規(guī)模MPI并行計算的可擴展三模冗余容錯機制[J]. 軟件學報,2012,23(4):1022-1035．

[16]李鑫，郭曉威，林宇斐. 數(shù)據(jù)流Eager傳輸：一種分布式流體系結(jié)構(gòu)中的性能優(yōu)化技術(shù)[J]. 計算機工程與科學,2015,37(11):2035-2044.

[17]宋偉. 面向事務存儲系統(tǒng)的容錯技術(shù)研究[D]. 長沙:國防科學技術(shù)大學,2011．

李鑫(1984-),男，安徽安慶人，博士生，研究方向為高性能計算和大數(shù)據(jù)。E-mail:xinli@nudt.edu.cn

LI Xin,born in 1984,PhD candidate,his research interests include distributed computing, and big data.

林宇斐(1985-),女，江西南昌人，博士，工程師，研究方向為并行計算。E-mail:linyufei@nudt.edu.cn

LIN Yu-fei,born in 1985,PhD,engineer,her research interest includes parallel computing.

郭曉威(1986-),男，湖南益陽人，博士生，研究方向為并行計算與數(shù)值模擬。E-mail:guoxiaowei@nudt.edu.cn

GUO Xiao-wei,born in 1986,PhD candidate,his research interests include parallel computing, and numerical simulation.

A triple modular eager redundancy fault-toleranttechnique for distributed stream architecture

LI Xin1，3，4,LIN Yu-fei2,GUO Xiao-wei1

(1.The State Key Laboratory of High Performance Computing,National University of Defense Technology,Changsha 410073;

2.Graduate School,National University of Defense Technology,Changsha 410073;

3.PLA University of Science and Technology,Nanjing 210007;

4.The 63rd Research Institute of PLA General Staff Headquarters,Nanjing 210007,China)

Abstract:As computing systems continue to expand in size in the Internet environment, the reliability of the distributed stream architecture is facing serious challenges. Based on the N-modular redundancy technique, we propose a triple modular eager redundancy fault-tolerant method for the distributed stream architecture (TREFT). The TREFT employs three program copies to run the error detection and error correction processes efficiently. Experimental results on a prototype system of the distributed stream architecture show that the TREFT could enhance the reliability of the system at very low cost, increasing the fault-tolerant cost by 10.77% on average.

Key words:distributed stream architecture;fault-tolerant technique;triple modular redundancy

作者簡介:

doi:10.3969/j.issn.1007-130X.2015.12.007

中圖分類號：TP338.8

文獻標志碼：A

基金項目：國家自然科學基金資助項目(61221491，61303071)

收稿日期：修回日期：2015-11-26

文章編號：1007-130X(2015)12-2233-09