基于架構(gòu)的眾核軟件可靠性建模與分析

覃志東，郝四明，韋俊銀，肖芳雄

（1 東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620；2 金陵科技學(xué)院 軟件工程學(xué)院，南京 211169）

0 引言

隨著芯片制程技術(shù)的不斷進(jìn)步，處理器設(shè)計(jì)技術(shù)已進(jìn)入到眾核（Many-Core）時(shí)代。如MIT 早在2008 年就設(shè)計(jì)出64 核心的Tile64 處理器。

一方面，當(dāng)晶體管的特征尺寸進(jìn)入到納米尺度并不斷縮小時(shí)，生產(chǎn)缺陷、工藝偏差、溫升和老化等因素將導(dǎo)致處理器的成品率和預(yù)期可靠性不斷降低。所以，為構(gòu)建高可靠的眾核系統(tǒng)，需要高可靠的眾核軟件系統(tǒng)進(jìn)行支撐。

但另一方面，為充分發(fā)揮眾核處理器的并行計(jì)算能力，眾核軟件系統(tǒng)一般都是由很多具有通信依賴關(guān)系的任務(wù)模塊構(gòu)成，按照特定的優(yōu)化算法映射到處理器核心上并發(fā)執(zhí)行。由于任務(wù)數(shù)量眾多，并發(fā)性將導(dǎo)致各任務(wù)及系統(tǒng)的執(zhí)行狀態(tài)更加不可預(yù)計(jì)，使得眾核軟件系統(tǒng)的可靠性預(yù)期也變差。

軟件由于邏輯抽象性，其可靠性設(shè)計(jì)、測(cè)試與評(píng)估技術(shù)是滯后于硬件的。雖然軟件可靠性工程已經(jīng)發(fā)展了幾十年了，但軟件可靠性仍然是導(dǎo)致系統(tǒng)可靠性提升的瓶頸。傳統(tǒng)單核處理器執(zhí)行的軟件所面臨的可靠性難題，眾核軟件依然存在。而且，由于眾核軟件架構(gòu)和并發(fā)執(zhí)行方式的不同，原來基于單核處理器軟件所建立的可靠性模型、可靠性測(cè)試方法和評(píng)估技術(shù)用于眾核軟件已不合適。

基于這種現(xiàn)狀，本文在分析眾核軟件模型和剖析眾核軟件映射流程的基礎(chǔ)上，對(duì)眾核軟件進(jìn)行了可靠性建模。模型揭示了各任務(wù)模塊和軟件系統(tǒng)之間的可靠性關(guān)系，為后續(xù)的可靠性設(shè)計(jì)、測(cè)試與評(píng)估方法的研究打下了基礎(chǔ)。

1 基于軟件架構(gòu)的典型可靠性模型介紹

為了說明不同的軟件架構(gòu)導(dǎo)致不同的軟件系統(tǒng)與任務(wù)模塊的可靠性關(guān)系，下面介紹2 種典型的基于軟件架構(gòu)的可靠性模型。

1.1 串并行軟件系統(tǒng)的可靠性模型

串并行模塊軟件系統(tǒng)是一種用硬件結(jié)構(gòu)來模擬軟件架構(gòu)的模型。其基本結(jié)構(gòu)是由個(gè)并行模塊組（每個(gè)模塊組包括k個(gè)模塊）和個(gè)串行模塊組成，如圖1 所示。

圖1 串并行模塊軟件系統(tǒng)基本架構(gòu)Fig.1 Basic architecture of a parallel-series modular software system

假設(shè)軟件系統(tǒng)中模塊的失效強(qiáng)度為λ（T），表示為：

其中，a、b是常量，分別表示模塊中錯(cuò)誤的平均值和檢測(cè)到的錯(cuò)誤率。

模塊持續(xù)工作時(shí)長(zhǎng)的可靠性為：

聯(lián)合式（1）、（2）可以得圖1 所示軟件系統(tǒng)的可靠性：

1.2 馬爾可夫鏈執(zhí)行狀態(tài)軟件可靠性模型

這里，設(shè)（）為一隨機(jī)過程，若（t）的狀態(tài)只取決于（t）的狀態(tài)，而與之前的（t）、（t）、…、（）的狀態(tài)都無關(guān)，則稱（）為馬爾可夫鏈。若為離散時(shí)間變量，則為離散時(shí)間馬爾可夫鏈（Discrete Time Markov Chain，DTMC）。一些軟件在執(zhí)行時(shí)，對(duì)CPU 的控制權(quán)在不同的軟件模塊之間轉(zhuǎn)移的過程便是DTMC，如圖2 所示。

圖2 DTMC 執(zhí)行狀態(tài)軟件基本架構(gòu)Fig.2 Basic architecture of the DTMC executing state transition software system

用p表示模塊到模塊的單步控制傳遞概率，p∈［0，1］。因此對(duì)于模塊軟件系統(tǒng)，可得到軟件的控制傳遞矩陣：

對(duì)于帶吸收狀態(tài)DTMC，吸收狀態(tài)和分別表示系統(tǒng)執(zhí)行成功和失敗。在軟件系統(tǒng)的實(shí)際運(yùn)行中，當(dāng)軟件模塊存在的缺陷被觸發(fā)后就會(huì)導(dǎo)致系統(tǒng)運(yùn)行的失敗，使得控制由模塊以概率q轉(zhuǎn)向吸收狀態(tài)。相反地，若軟件系統(tǒng)執(zhí)行成功，則控制由模塊以概率p轉(zhuǎn)向吸收狀態(tài)。且控制傳遞概率滿足：

進(jìn)一步可得，在運(yùn)行中的模塊軟件系統(tǒng)的運(yùn)行控制傳遞矩陣為：

因此，可得到該系統(tǒng)的可靠性R為：

2 眾核軟件映射流程剖析

眾核軟件往往基于吞吐率、通信量、功耗等優(yōu)化目標(biāo)和限制條件，映射到各處理核心上并發(fā)執(zhí)行。任務(wù)映射就是離線任務(wù)分配、調(diào)度和綁定。處于并發(fā)執(zhí)行狀態(tài)的眾核軟件的架構(gòu)是不同于單處理器上經(jīng)操作系統(tǒng)動(dòng)態(tài)調(diào)度的序貫執(zhí)行架構(gòu)。現(xiàn)有的基于架構(gòu)的可靠性模型不適用于眾核軟件。

本節(jié)首先介紹眾核軟件映射流程和平衡調(diào)度算法，為可靠性建模提供知識(shí)基礎(chǔ)。

2.1 眾核軟件映射流程剖析

眾核軟件映射的基本流程如下。

（1）邏輯處理器抽象。圖3（a）是一個(gè)具有4 核心的物理處理器。根據(jù)各核心的個(gè)數(shù)、互聯(lián)方式、緩存的設(shè)置方式等，可以把物理處理器抽象為邏輯處理器，如圖3（g）所示。其中，物理核心Core1 抽象為邏輯核心，物理核心Core3 被抽象為邏輯核心，而物理核心Core2 被抽象為邏輯核心，物理核心Core4 被抽象為邏輯核心。處理器核心很多、甚至有些壞掉了，可以根據(jù)具體情況選擇一些核心使用，并將其抽象成邏輯處理器。

圖3 眾核軟件映射流程Fig.3 Mapping process of the many-core software system

（2）數(shù)據(jù)流圖分析與轉(zhuǎn)換。同步數(shù)據(jù)流圖（Synchronous Data Flow Graph，SDFG）常用來表示一個(gè)眾核軟件，如圖3（b）所示。該軟件由6 個(gè)任務(wù)、、、、和組成，分別實(shí)現(xiàn)低通濾波、傅里葉變換、數(shù)據(jù)分發(fā)、數(shù)據(jù)快插和數(shù)據(jù)融合。其中，運(yùn)行一次要消耗1 單元的數(shù)據(jù)，并產(chǎn)生1 單元數(shù)據(jù)。運(yùn)行一次要消耗32 單元的數(shù)據(jù)，并產(chǎn)生32 單元數(shù)據(jù)。所以，為滿足軟件系統(tǒng)的正常運(yùn)行，需要連續(xù)運(yùn)行32 次，才運(yùn)行1 次，而需16 次，、和各需1 次；此時(shí)，通信量為32。這種調(diào)度平衡后的負(fù)載與通信常用有向無循環(huán)圖（Directed Acyclic Graph，DAG）表示，見圖3（c）。已有成熟算法解決SDFG 的平衡調(diào)度，平衡調(diào)度好的SDFG 可以直接用DAG 表示，供劃分映射。

（3）軟件向邏輯處理器分配與調(diào)度。此階段由映射算法把圖3（c）中的DAG 向邏輯處理器進(jìn)行分配與調(diào)度。由圖3（d）可知，假定：、、分配到，、分配到，分配到，便構(gòu)成了一個(gè)3 段流水線。系統(tǒng)可以基于最大化該條流水線吞吐率的優(yōu)化目標(biāo)進(jìn)行分配。單個(gè)處理核心上的任務(wù)集分配結(jié)束后，可以基于某種優(yōu)化方式離線安排好相應(yīng)的執(zhí)行順序，即靜態(tài)調(diào)度。

（4）軟件任務(wù)向處理器核心綁定。由圖3 中（e）至（h）可知，分配好的任務(wù)集需要綁定到邏輯核心所對(duì)應(yīng)的物理核心。如、對(duì)應(yīng)的是邏輯核心，要綁定到物理核心Core3。此時(shí)，需要根據(jù)任務(wù)間的相對(duì)位置，建立通信。若2 個(gè)任務(wù)在一個(gè)核心上，那么定義數(shù)組變量，完成數(shù)據(jù)通信，如［32］便是對(duì)的通信。若兩者不在一個(gè)核心上，那么要定義數(shù)據(jù)發(fā)送/接收函數(shù)；如（［1：16］，Core3）便是向所在的Core3 的緩存寫數(shù)據(jù)，而（［1：16］，Core3）便是把寫在本地緩存的數(shù)據(jù)讀出來。顯然函數(shù)是跨越處理器核心的，其通信時(shí)間是受具體通信鏈路決定的。為了讓任務(wù)利用以及產(chǎn)生通信數(shù)據(jù)，還要對(duì)任務(wù)加上封裝函數(shù)，如（［1：32］，［1：32］）。

（5）眾核軟件的流水執(zhí)行模式。假定映射到的、、及其封裝函數(shù)為，映射到的、及其封裝函數(shù)為，映射到的及其封裝函數(shù)為。那么、、所綁定的物理核心Core1、Core3 和Core4 就構(gòu)成處理器核心執(zhí)行流水線，處理器上的、、是并行執(zhí)行的。其中，流水周期由、、三者的最大執(zhí)行時(shí)間決定，即：max｛，，｝；當(dāng)流水線充滿后，每隔一個(gè)周期便有一個(gè)系統(tǒng)輸出。該流水線的時(shí)空?qǐng)D如圖4 所示。

圖4 眾核軟件流水線執(zhí)行的時(shí)空?qǐng)DFig.4 Executed spatio-temporal diagram of the pipeline for many-core software

2.2 SDFG 的周期平衡調(diào)度

SDFG 描述的眾核軟件如圖5 所示。圖5 中，節(jié)點(diǎn)代表任務(wù)，任務(wù)按字母順序編號(hào)；箭頭代表?。ㄈ蝿?wù)之間的輸出輸入關(guān)系），弧的箭尾上的數(shù)字，代表前一個(gè)任務(wù)執(zhí)行一次產(chǎn)生的數(shù)據(jù)資源，箭尖的數(shù)字代表下一個(gè)任務(wù)執(zhí)行一次所需要消耗的數(shù)據(jù)資源?；∩戏娇蚶锏臄?shù)字代表了弧的編號(hào)。

圖5 多鏈結(jié)構(gòu)SDFGFig.5 Structure of the multi-chains SDFG

顯然，當(dāng)滿足產(chǎn)生與消耗的數(shù)據(jù)量平衡時(shí)，這個(gè)SDFG 表示的眾核軟件才能正常執(zhí)行下去。所以，當(dāng)眾核軟件執(zhí)行時(shí)，每個(gè)任務(wù)需要按照一定的次數(shù)重復(fù)執(zhí)行；而單個(gè)任務(wù)重復(fù)執(zhí)行的次數(shù)越多，代表分配到處理核心的執(zhí)行負(fù)載越大。則在任務(wù)向處理核心分配前，需要對(duì)SDFG 進(jìn)行平衡調(diào)度，從而得到滿足通信量平衡時(shí)每個(gè)任務(wù)模塊具體執(zhí)行次數(shù)，并間接得到負(fù)載量。

SDFG 的周期平衡調(diào)度已有多種成熟算法。本文介紹文獻(xiàn)［8］中方法。首先，SDFG 用與有向圖相關(guān)聯(lián)的拓?fù)渚仃噥肀硎荆盒袑?duì)應(yīng)??；對(duì)應(yīng)任務(wù)節(jié)點(diǎn)。第（，）項(xiàng)表示第個(gè)任務(wù)節(jié)點(diǎn)調(diào)用一次，其在弧上產(chǎn)生的數(shù)據(jù)流。若是消耗，數(shù)值為負(fù)；若沒有在弧上，則為0。圖5 的拓?fù)渚仃嚾缡剑?）所示：

若拓?fù)渚仃嚨闹?1（為節(jié)點(diǎn)的數(shù)量），則表示該SDFG 上能構(gòu)造周期性可允許的順序調(diào)度。對(duì)圖5 的拓?fù)渚仃嚲剡M(jìn)行初等行變換，得：

矩陣的秩5。等于-1，則可以構(gòu)造周期性均衡循環(huán)調(diào)度。具體構(gòu)造方法是求解滿足0的向量。例如，拓?fù)渚仃嚕?）對(duì)應(yīng)的向量為：

向量中對(duì)應(yīng)的元素為相應(yīng)任務(wù)調(diào)度在一個(gè)循環(huán)周期中被激發(fā)執(zhí)行的次數(shù)。

3 眾核軟件可靠性建模

3.1 SDFG 向DAG 轉(zhuǎn)換

顯然，只有對(duì)SDFG 進(jìn)行均衡調(diào)度后，才能知道一個(gè)具體的任務(wù)在一個(gè)循環(huán)周期中對(duì)處理核心產(chǎn)生的負(fù)載量是多少?？梢园颜{(diào)度好的軟件轉(zhuǎn)換為由DAG 來刻畫。例如圖5 給出的SDFG 向DAG 轉(zhuǎn)化結(jié)果如圖6 所示。其中，任務(wù)在一個(gè)周期循環(huán)中，需要激發(fā)執(zhí)行8 次，每次占用處理核心5 單位時(shí)間，總共占用40 單位時(shí)間；那么用任務(wù)來代表整體執(zhí)行8 次的，于是就形成了右邊的DAG 圖。

圖6 SDFG 轉(zhuǎn)化為DAGFig.6 Conversion of SDFG to DAG

3.2 眾核軟件可靠性建模

當(dāng)流水充滿后，每過時(shí)間便會(huì)有個(gè)輸出。定義核心上任務(wù)集運(yùn)行一次的時(shí)間與周期的比：

核心上任務(wù)是分時(shí)獨(dú)占處理核心資源的，第個(gè)任務(wù)占用比例為：

當(dāng)處理器穩(wěn)定工作一段時(shí)間以后，處理核心上任務(wù)集運(yùn)行的總時(shí)間為：

整個(gè)軟件系統(tǒng)在時(shí)間段內(nèi)不失效，則必須滿足所有核心上工作的任務(wù)集在其執(zhí)行期間不失效。則系統(tǒng)可靠性可以表示為：

將式（15）代入式（17），可得：

將式（18）代入式（16），可得：

又因?yàn)椋?span id="j5i0abt0b" class="emphasis_italic">R()＝e，則有：

又因?yàn)椋?span id="j5i0abt0b" class="emphasis_italic">R()＝e，R()＝e，所以：

將式（14）代入式（12）得到：

式（23）便是SDFG 所示軟件系統(tǒng)的可靠性模型。

設(shè)任務(wù)A在一個(gè)周期內(nèi)被調(diào)度執(zhí)行的次數(shù)為d（可由得到），運(yùn)行一次的時(shí)間為T，則有：

將式（24）代入式（13），可得k：

4 實(shí)驗(yàn)及結(jié)果分析

圖7 即為一SDFG 表示的眾核軟件系統(tǒng)，及其被映射到的邏輯處理器核心的情況。表1 是其各個(gè)任務(wù)模塊的參數(shù)。

圖7 一個(gè)眾核軟件系統(tǒng)例子Fig.7 An example of the many-core software system

表1 眾核軟件的任務(wù)模塊參數(shù)Tab.1 Parameters of task modules in the many-core software system

由表1 可知，模塊的執(zhí)行時(shí)間比例是最高的，而模塊的執(zhí)行時(shí)間比例是最低的。將其它模塊的總失效率之和設(shè)為0.0001 個(gè)/h，利用R（）＝e和式（23），分別對(duì)模塊和的失效率變化所導(dǎo)致對(duì)系統(tǒng)可靠性的影響進(jìn)行了數(shù)值模擬，結(jié)果如圖8 所示。

圖8 系統(tǒng)對(duì)任務(wù)模塊可靠性變化的敏感性仿真Fig.8 Sensitivity simulation of the system to reliability change of a task module

由圖8 可知，隨著任務(wù)模塊失效率的增加，系統(tǒng)可靠性R降低得更快，表明R對(duì)的失效率變化非常敏感。但是，隨著任務(wù)模塊的失效率的增加，系統(tǒng)可靠性R基本沒有變化，說明R對(duì)的失效率變化不敏感。由于執(zhí)行時(shí)間比例是遠(yuǎn)遠(yuǎn)大于的，也就表明了執(zhí)行時(shí)間比例高的任務(wù)模塊對(duì)系統(tǒng)可靠性影響大。所以，可以通過本文所建立的眾核軟件可靠性模型，識(shí)別出對(duì)系統(tǒng)可靠性影響大的模塊，并采取措施切實(shí)提高這些任務(wù)模塊的可靠性，如此就可以有效確保整個(gè)軟件系統(tǒng)的可靠性。

5 結(jié)束語

本文在剖析眾核軟件映射過程的基礎(chǔ)上，建立了一個(gè)眾核軟件可靠性模型；該模型建立了軟件系統(tǒng)與任務(wù)模塊之間的可靠性關(guān)系。利用該模型，識(shí)別出對(duì)系統(tǒng)可靠性影響較大的任務(wù)模塊，可以提高可靠性保障措施的實(shí)施針對(duì)性。