指令預取感知的多核系統WCRT和WCEC優化

韓麗艷，安立奎

(1.渤海大學 信息科學與技術學院，遼寧 錦州 121013;2.渤海大學 數理學院，遼寧 錦州 121013)

0 引 言

對于嵌入式多核下的實時系統，最壞情況下響應時間(worst-case response time，WCRT)是一個優先考慮的問題，來保證實時任務的可靠性和可調度性[1]。同時對于一些能量供應受限的實時系統，例如衛星的傳感監視系統，普適系統，最壞情況下的能量消耗(worst-case energy consumption，WCEC)也是一個非常重要的因素[2]。

許多嵌入式多核系統支持順序指令預取技術來提高系統的性能，文獻[3]研究表明硬件預取也能夠降低系統的能耗。實時系統通常具有多個并發個子任務，由于系統中的子任務有事務密集型的，也有數據密集型的，順序指令預取的性能和能量效率就與指令預取度有著密切關系,如果這些子任務采用相同預取度，不利于提高實時系統的性能和降低系統的能耗。

目前文獻[4]提出一種多核實時系統的WCRT分析方法，通過分析并發多個任務在共享緩存上的干擾來實現。文獻[5]通過優化任務到核的映射，減少實時系統的WCRT。文獻[4-5]并沒有關注指令預取對與實時系統的最壞情況下的能耗的影響。文獻[6-7]研究了Next-N硬件指令預取技術對WCET(worst-case execution time)的影響，考慮的僅是單核下的單級指令緩存，并沒有考慮多核實時系統的多級緩存，也沒有考慮實時系統最壞情況下的能量效率。文獻[8]用循環譯碼的指令緩存減少能量消耗，提出了一個支持指令預取的能量有效的單核嵌入式模型。文獻[9]用單層指令預取緩沖區和鎖緩存來優化任務的WCET和WCEC。文獻[10]提出一種基于基本塊的指令預取方法來優化系統WCET的評估值。

針對具有多級緩存的嵌入式多核系統，目前還沒有利用指令預取來優化其最壞情況下性能和能量消耗方面的研究工作。為此，文中提出了支持指令預取的WCRT和WCEC優化模型，設計了相應的優化算法，通過實例分析驗證了優化算法的有效性。

1 支持指令預取的嵌入式多核模型

1.1 嵌入式多核結構

圖1 支持指令預取器的嵌入式多核架構

并發多任務的執行環境是一個基于靜態優先級的非搶占系統，假設實時系統有NT個相互依賴的實時任務。這些任務根據它們之間可并行化的關系被映射到了NC(NC<6)處理器核，與實時系統無關的非實時任務都被映射到了剩下的核中。這里，緩存劃分的目的是為了消除并發的多個實時任務在共享緩存上的干擾，確保實時任務的時間可分析性。L2優先分給實時任務使得每個核上的實時任務WCET滿足其截止期，剩余的L2緩存分給非實時任務。

1.2 能量模型

文中采用文獻[12]中的能量消耗計算模型，對于不同的預取度n(n≥0)，當n為0時，表示沒有采用預取操作，這時候關閉預取器，式(1)計算單個實時任務T支持指令預取的最壞情況下的能耗：

E(T,n)=Estatic(n)+Edynamic(n)

(1)

其中,

Ec_dynamic(n)=Ec*cn,Ep_dynamic(n)=Ep*pn

任務T最壞情況下總的能耗是由最壞情況下的靜態能耗Estatic(n)和動態能耗Edynamic(n)組成。其中Cstatic，pstatic分別是處理器和預取器的靜態能耗，tn是當預取度是n時的任務最壞情況執行時間，當n=0時，意味著關閉預取器。動態能耗Edynamic(n)由處理器和預取器的動態能耗組成，Ec表示每次訪問存儲器所耗費在存儲系統上的能耗，cn是當預取度為n時的最壞情況下訪存次數。Ep表示每次預取操作預取器的動態能耗，pn是最壞情況下的預取操作次數。

2 支持指令預取的WCRT和WCEC優化

2.1 實時系統WCRT和WCEC優化模型

實時系統RS={TS,D,M,WCRT,WCEC}，TS是其所有子任務的集合TS={T1,T2,…,TNT}，D是順序指令預取度集合D={0,1,…,Np}，0表示關閉指令預取器，M是任務TS到預取度D的映射：M:TS→D。

通過實時系統的MSG(message sequence graph)圖，得到了實時系統任務之間的依賴關系，用Pred(Ti)來表示任務Ti的所有前驅任務的集合，Start(M,Ti)表示任務Ti的在映射M下的開始時間，Finish(M,Ti)表示任務Ti在映射M下的結束時間， WCET(M,Ti)表示任務Ti在映射M下的最壞情況執行時間，任務Ti的開始時間是Ti所有前驅任務完成時間的最大值，如式(2)，任務Ti的結束時間是Ti開始時間與WCET(M,Ti)的和，如式(3)：

Start(M,Ti)=Max(Finish(M,Ti)),Tj∈Pred(Ti)

(2)

Finish(M,Ti)=Start(M,Ti)+WCET(M,Ti)

(3)

實時系統的支持指令預取的WCRT是運行在所有核上任務的結束時間的最大值，如式(4)：

WCRT=Max(Finish(M,Ti)),1≤i≤NT

(4)

為了通過上面的公式計算實時系統的WCRT，文中根據MSG建立與實時系統相對應的有向無環任務圖TG=(V,E)，每個節點vi∈V表示一個實時任務Ti，每條有向邊ei∈E表示任務間的依賴關系。每條邊上有一個權值，它代表這條邊的始點代表的任務Ti在映射M下支持指令預取的WCET。為了計算整個系統的WCRT，文中需要給這個無環圖的終節點再增加一個匯集節點T_end作為任務圖的終點，那么整個實時系統的WCRT是運行在所有核上的任務的結束時間的最大值，也就是TG的源點(開始任務)到匯集節點(終止任務)的關鍵路徑長度。

實時系統在最壞情況下的能量消耗WCEC是所有子任務在映射M下最壞能量消耗的和，如式(5)，其中WCEC(M,Ti)是任務Ti在映射M下的WCEC。

(5)

文中的優化目標是尋找映射M，使得在實時系統的WCRT最小化的情況下，WCEC最小，即：

(6)

當，

Minize(Maxmize(Finish(M,Ti))),1≤i≤NT

(7)

2.2 WCRT和WCEC優化算法

2.2.1 WCRT和WCEC優化原理

對于實時系統，WCET(dj,Ti)表示任務Ti在預取距離dj下的WCET，首先通過式(8)確定映射Mp，對于每一個子任務Ti，在給定的預取度范圍D內，Mp確定它取得最小WCET的預取距離dj:

(8)

在映射Mp下，計算TG的關鍵路徑P={Tp1,Tp2,…,Tpn},關鍵路徑P的長度是整個實時系統的最小化的WCRT。此時令M(Ti)=Mp(Ti),如果Ti∈P。

對于非關鍵路徑上的實時任務Tj?P，在不改變關鍵路徑的情況下，最小化Tj的WCET并不能夠減小整個系統的WCRT，這時候取它們的能量獲益最高的預取度，會降低整個系統的能量消耗。M(Tj)=dk，這里dk使得任務Tj在不改變TG的關鍵路徑情況下WCEC最小。

下面通過一個例子對WCRT和WCEC優化方法進行說明。假設有兩個核，實時系統具有6個子任務，圖2是其MSG描述，圖3是其相應的TG，其邊上的權值是所有子任務支持指令預取的不同預取度下最小的WCET。

圖2 實時系統MSG

圖3 實時系統TG

由TG可以計算從任務T1到任務Tend的關鍵路徑P:T1→T3→T5→Tend，路徑長度是800，這里整個實時系統的最優的WCRT就是800。對于非關鍵路徑P:T1→T2→T4→T6→Tend上的實時任務T2，T4，T6，為了不影響與它們對應的關鍵路徑P，它們總共可以延長100，在這個范圍內，再次調整T2，T4，T6的指令預取度，使得能量獲益最大。

2.2.2 WCRT和WCEC優化算法實現

優化算法的難點主要有兩處：一是如何識別出非關鍵子路徑，計算非關鍵子路徑的可以被延長的時間片；二是如何把時間片分給非關鍵子路徑上的每個任務，取得能量收益的最大化。

對于順序指令預取，不同的預取度N對于系統的性能和能耗都有不同的影響。矩陣元素P[i][j]和E[i][j]分別存儲任務Ti(1≤i≤NT)在預取度j(0≤j≤NP)下的最壞情況下的性能和能量消耗。P_D[i](1≤i≤NT)表示任務Ti在結合性能和能耗優化后，在執行時候的應該采用的預取度。非關鍵子路徑構建算法如下：

算法1：非關鍵子路徑構建。

輸入：任務TG，P[i][j]，P_D[i](初始化為0)。

輸出：優化后的WCRT，非關鍵子路徑集合NPS，P_D[i](性能優化后的預取度)。

(1)通過P[i][j]把任務Ti取得最好的WCET的預取度k賦值給P_D[i]，?j∈[0,NP],p[i][k]≤p[i][j]，同時給TG中與Ti相對應的邊賦最優的WCET值。

(2)根據實時系統的TG，P_D[i]和P[i][j]計算最優情況下支持指令預取的關鍵路徑P和WCRT。

(3)對所有非關鍵路徑上的任務，按拓撲序列構建任務隊列TQ。

(4)從TQ隊頭選擇一個任務Tj，以Tj直接前驅Tk(關鍵任務)為頭構建非關鍵子路徑隊列NP。從Tj開始，依次在TQ中尋找每個非關鍵任務的直接后繼Tm，并把Tm從TQ中刪除，加入到NP隊尾，直到任務Tm的直接后繼為一關鍵任務Tc，把Tc也加入到NP中，把NP加入到NPS中。

(5)重復過程4，構建非關鍵子路徑集合NPS={NP1,NP2,…,NPn},直到TQ為空。

圖3中的T2，T4，T6是非關鍵路徑上的任務，按拓撲序列TQ={T2,T4,T6}。第1個非關鍵任務是T2，它的直接前驅T1作為非關鍵子路徑隊列NP1的隊頭，T2的直接后繼是T4,把T4從TQ中刪除，插入到NP1隊尾，T4的直接后繼是T6，它也被插入到NP1隊尾。T6的后繼是關鍵任務Tend,把Tend也加入NP1隊尾，此時NP1是一條非關鍵子路徑。這時非關鍵任務隊列TQ為空，算法結束。至此圖3所示的TG中存在一條非關鍵子路徑NP1={T1,T2,T4,T6,Tend}，非關鍵路徑長度是700。

對于一條非關鍵子路徑隊列NP，它可以被延長的時間片是從隊頭到隊尾之間關鍵路徑長度與非關鍵路徑長度的差。

在非關鍵子路徑上的任務，文中用窮舉法在允許被延長的時間內，調整實時任務的預取度，優化能耗，P_E[i](1≤i≤NT)表示任務Ti在結合性能和能耗優化后，在執行時應該采用的預取度。優化算法如下：

算法2：優化WCEC。

輸入：實時系統任務圖TG，非關鍵子路徑集合NPS={NP1,NP2,…,NPn}，P[i][j]，E[i][j]，P_D[i]。

輸出：優化后的WCEC，P_E[i](結合性能和能耗優化后的預取度)。

(1)對每一個非關鍵子路徑NPi={Ti1,Ti2,…,Tin}，計算NPj隊列中兩個關鍵任務Ti1和Tin之間的關鍵路徑的長度ti，它是兩個關鍵任務最早開始時間的差值。

(2)計算最優性能下非關鍵子任務的能量消耗：

Ei=Ε[i2][P_D[i2]]+E[i3][P_D[i3]]+…+E[in-1][P_D[in-1]]

(3)用窮舉法求出在時間不超出ti情況下的取得最優能耗的指令預取度。

FOR(ki2from 0 toNP) DO

FOR(ki3from 0 toNP) DO

……

FOR(kin-1from 0 toNP) DO

IF(P[i1][P_D[i1]]+P[i2][ki2]+…+P[in-1][kin-1]≤ti)THEN

IF(E[i2][ki2]+E[i3][ki3]+…+E[in-1][kin-1]≤Ei)THEN

Ei=E[i2][kι2]+…+E[in-1][kin-1]

P_E[i2]=ki2;…P_E[in-1]=kin-1;

END IF

END IF

END FOR

……

END FOR

END FOR

(4)重復過程1到3，直到NPS為空。

(5)用式(9)計算實時系統優化后的最壞情況下的能量消耗。

(9)

3 實驗評估

這部分評估文中支持指令預取的實時系統WCRT 和WCEC優化算法。

3.1 評估環境

嵌入式多核假設有6個同構的處理器核，對于每一個核，有5階段流水，順序執行。L2緩存是8 KB，緩存行是32 B，4路組關聯，有64組。L1指令和數據緩存是512 B，緩存行大小是16 B，直接映射。L1緩存的命中延遲是1 circle，缺失延遲是6 circles。L2緩存的缺失延遲是30 circles，預取度N的取值范圍是從0到5。

實驗運行在Intel i5-3230 機器上,4 GB內存，運行Ubuntu Linux 8.04操作系統。

文中子任務的WCET通過支持指令預取的緩存WCET分析工具[13]測得。采用文獻[12]中的能量消耗計算模型。芯片的工藝是32 nm,頻率是1.0GH,總的緩存訪問和緩存缺失可以通過靜態分析獲得。不同工藝下每次訪問的動態能耗和靜態能耗是CACTI5[14]的測試結果。硬件預取器通過一些硬件表來實現[3],它的能耗可以被精確模擬。這里假設有一個1 024-bit的指令預取緩沖隊列，在32 nm工藝下，預取器消耗0.063 mW的靜態能耗，每次讀的能耗是0.002 nJ，每次寫的能耗是0.003 nJ。

文中使用的benchmark是DEBIE空間碎片探測器系統[15]，根據DEBIE的系統狀態和功能，文獻[16]對系統進行了并行化處理，圖4是系統的MSG圖。當DEBIE的所有實時任務被映射到了核1，2，3到4，分配給每個核的L2緩存組是由它上面運行的最大的任務所決定的，最大任務的WCET最小的L2組被分配給了該處理器核，表1是分配給核1，2,3和4的L2組。余下的組被核5和核6共享。

圖4 DEBIE 系統的MSG

表1 L2緩存劃分結果

3.2 實驗結果

3.2.1 優化算法對最壞情況下的性能的優化

為了分析文中的優化算法對于最壞情況下系統性能的影響，圖5給出的是DEBIE系統在文中算法優化后的WCRT和不同預取度下的WCRT的比值，比值越小則表明性能提高越明顯。

從圖5可以看出，優化后的支持指令預取的最壞情況下的性能比沒有預取的最壞情況下(N為0)的性能提高了57.7%，與預取度是5的比值接近于1。這是由于整個系統的指令較多，需要進行的數據計算很少，指令預取度越大，指令預取提高最壞情況下的性能越明顯，此時優化的效果反而不明顯。

圖5 不同預取度下WCRT的比值

3.2.2 指令預取對最壞情況能耗的影響

為了分析指令預取度對于最壞情況下系統性能的影響，圖6比較了系統在不同預取度下的支持指令預取和不支持指令預取的WCEC，結果被WCEC(N是0)歸一化了。

圖6 歸一化的WCEC

從圖6可以看出，不同預取度下DEBIE系統在最壞情況下的能量消耗都被減少了。預取節省的平均能耗為28.3%，預取度越大，節能效果反而不好，原因是預取度越大，消耗的動態能耗比重越大，預取減少的總的能量消耗也就越少。

3.2.3 最壞情況下能量的優化

為了分析文中的優化算法對于最壞情況下能量消耗的影響，圖7比較了DEBIE系統在保證系統性能最優的情況下，文中算法優化后的WCEC和不同預取度下的WCEC比值，比值越小則表明能耗降低越明顯。

圖7 不同預取度下WCEC的比值

從圖7可以看出，優化后的WCEC比不支持指令預取(N是0)的最壞情況下的WCEC提高30.5%，但此時不是性能最優。當預取度N是5時，性能最優，這時優化后的最壞情況下的能量消耗減少了10.8%。能量優化的效率與程序的訪存次數和動態能耗在總能耗中的比重有關系。預取度越大，訪存次數也就越多，動態能耗消耗得也就越多，因而能量優化的效果越明顯。

4 結束語

對于性能和能耗要求很高的多核實時系統，提出支持指令預取的WCRT和WCEC優化算法，通過調整子任務的預取度在保證性能最優的情況下來優化最壞情況下的能耗。實驗通過對DEBIE系統的分析，表明優化算法是有效的，系統中子任務的并行程度高，指令訪存次越多數多，優化的效果越明顯。

今后希望能夠研究數據預取對于實時系統WCEC的影響，并提出支持指令預取和數據預取的實時系統最壞情況下的性能和能耗優化方法。