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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

模塊持續(xù)工作時長的可靠性為：

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

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

這里，設(shè)（）為一隨機過程，若（t）的狀態(tài)只取決于（t）的狀態(tài)，而與之前的（t）、（t）、…、（）的狀態(tài)都無關(guān)，則稱（）為馬爾可夫鏈。若為離散時間變量，則為離散時間馬爾可夫鏈（Discrete Time Markov Chain，DTMC）。一些軟件在執(zhí)行時，對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］。因此對于模塊軟件系統(tǒng)，可得到軟件的控制傳遞矩陣：

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

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

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

2 眾核軟件映射流程剖析

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

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

2.1 眾核軟件映射流程剖析

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

（1）邏輯處理器抽象。圖3（a）是一個具有4 核心的物理處理器。根據(jù)各核心的個數(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）常用來表示一個眾核軟件，如圖3（b）所示。該軟件由6 個任務、、、、和組成，分別實現(xiàn)低通濾波、傅里葉變換、數(shù)據(jù)分發(fā)、數(shù)據(jù)快插和數(shù)據(jù)融合。其中，運行一次要消耗1 單元的數(shù)據(jù)，并產(chǎn)生1 單元數(shù)據(jù)。運行一次要消耗32 單元的數(shù)據(jù)，并產(chǎn)生32 單元數(shù)據(jù)。所以，為滿足軟件系統(tǒng)的正常運行，需要連續(xù)運行32 次，才運行1 次，而需16 次，、和各需1 次；此時，通信量為32。這種調(diào)度平衡后的負載與通信常用有向無循環(huán)圖（Directed Acyclic Graph，DAG）表示，見圖3（c）。已有成熟算法解決SDFG 的平衡調(diào)度，平衡調(diào)度好的SDFG 可以直接用DAG 表示，供劃分映射。

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

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

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

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

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

SDFG 描述的眾核軟件如圖5 所示。圖5 中，節(jié)點代表任務，任務按字母順序編號；箭頭代表弧（任務之間的輸出輸入關(guān)系），弧的箭尾上的數(shù)字，代表前一個任務執(zhí)行一次產(chǎn)生的數(shù)據(jù)資源，箭尖的數(shù)字代表下一個任務執(zhí)行一次所需要消耗的數(shù)據(jù)資源。弧上方框里的數(shù)字代表了弧的編號。

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

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

SDFG 的周期平衡調(diào)度已有多種成熟算法。本文介紹文獻［8］中方法。首先，SDFG 用與有向圖相關(guān)聯(lián)的拓撲矩陣來表示：行對應弧；對應任務節(jié)點。第（，）項表示第個任務節(jié)點調(diào)用一次，其在弧上產(chǎn)生的數(shù)據(jù)流。若是消耗，數(shù)值為負；若沒有在弧上，則為0。圖5 的拓撲矩陣如式（8）所示：

若拓撲矩陣的秩-1（為節(jié)點的數(shù)量），則表示該SDFG 上能構(gòu)造周期性可允許的順序調(diào)度。對圖5 的拓撲矩陣矩進行初等行變換，得：

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

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

3 眾核軟件可靠性建模

3.1 SDFG 向DAG 轉(zhuǎn)換

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

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

3.2 眾核軟件可靠性建模

當流水充滿后，每過時間便會有個輸出。定義核心上任務集運行一次的時間與周期的比：

核心上任務是分時獨占處理核心資源的，第個任務占用比例為：

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

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

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

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

又因為，R()＝e，則有：

又因為，R()＝e，R()＝e，所以：

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

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

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

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

4 實驗及結(jié)果分析

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

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

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

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

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

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

5 結(jié)束語

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