結合指令預取和緩存劃分的多核緩存WCEC優化

安立奎，韓麗艷

1.渤海大學 數理學院，遼寧 錦州121013

2.渤海大學 信息科學與技術學院，遼寧 錦州121013

1 引言

在硬實時多核系統中，任務執行時間必須滿足時間截止期，這對于硬實時系統的可靠性和可調度性來說非常重要。同時對于能量供應受限的硬實時系統，例如衛星的傳感監視系統、普適系統等，最差情況下的能量消耗WCEC（Worst-case Energy Consumption）也是一個必須要考慮的因素[1-3]。

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

由于片上緩存占據了多核處理器的較大面積和擁有較高的訪問頻率，緩存消耗的能量超過了系統片上能量消耗的50%[4]，因此減少緩存能量消耗對延長系統的使用期來說非常關鍵.隨著芯片技術的不斷進步，順序指令預取技術可以減少緩存能量能耗[5-6]。順序指令預取的緩存能量效率與指令預取度密切相關，對于硬實時多核系統中的多個子任務來說，采用相同預取度不利于減少整個系統的緩存WCEC，這就非常有必要對指令預取度進行優化來提高指令預取的能量效率。Gu 等人[7]提出了一個能量有效的支持指令預取的單核嵌入式模型，用循環譯碼的指令緩存減少能量消耗。對于單核中的多個搶占式任務，Gran等人[8]用單層指令預取緩沖區和鎖緩存來優化任務的WCET 和WCEC。在文獻[7]和[8]中，也僅考慮的是單核下的單層指令緩存的能量消耗，并沒有考慮有多個并發任務的硬實時多核系統的緩存能量消耗。

最近的研究表明多個并發任務在多核共享緩存上的干擾，降低了系統的性能，增加能量消耗。緩存劃分技術通過把共享緩存的一部分分配給每個處理核來消除干擾，降低能量消耗，關于這方面的研究已經做了大量的工作[9-14]。Reddy等人[9]用緩存劃分技術消除多個任務在共享緩存上的干擾，減少緩存能量消耗。Wang 等人[12]結合DCR（Dynamic Cache Reconfiguration）和緩存劃分減少多個硬實時任務的緩存能量消耗。其研究的任務集彼此獨立，并且沒有分析指令預取對于硬實時多核系統的緩存能量消耗的影響。

本文通過查閱文獻發現至今還沒有結合指令預取和緩存劃分的緩存能量消耗優化方面的研究工作。為了減少硬實時系統的緩存WCEC，延長系統的使用期，本文提出硬實時多核系統結合指令預取和緩存劃分的最差情況下緩存能量消耗優化方法。首先建立了結合指令預取和緩存劃分緩存WCEC 能量優化模型，然后設計了結合指令預取和緩存劃分的ILP線性規劃方程，在保證硬實時系統滿足時間截止期的情況下，優化其WCEC；最后，對硬實時系統DEBIE進行實例分析，驗證優化方法的有效性。

2 嵌入式多核模型和研究動機

2.1 嵌入式多核結構和任務模型

如圖1 是一種支持指令預取的嵌入式多核模型。有NC個同構的處理器核。每個核有私有的L1指令/數據緩存，所有的核共享L2 聯合緩存，共享L2 緩存有W路（way），通過路緩存劃分技術[13]，它被分成了NC部分，即，L2緩存劃分因子路被分給了運行硬實時任務的核Ci(i=1,2,…,NC) 。緩存的替換策略是LRU（Least Recently Used）。L1 和L2 緩存通過硬實時總線連接。如圖2 是一個基于路劃分的例子（4核，1組，8路組關聯），L2緩存通過路的粒度進行劃分，每個處理器核被分配了一些路，并且此處理器只允許訪問分給它的那些路。

圖2 一個基于路的緩存劃分的例子（4核，1組，8路組關聯）

順序指令預取器采用支持Prefetch-on-Miss 預取策略的Next- N -Line 指令預取。如果處理器需要處理的當前指令i 被映射到L1指令緩存行p 在L1指令緩存上沒有命中，那么L1 指令緩存預取器I-prefetcher 就會發出預取L1 指令緩存行p+1,p+2,…,p+N 的操作請求。如果需要預取的指令行已經在L1 指令緩存，預取請求被丟棄，否則預取請求進入一個FIFO（First In First Out）隊列，隨后請求會被發送到L2緩存。為了支持指令預取優化機制，采用文獻[15]的方法，利用編譯器在任務之間留下程序預取度信息指示，在程序運行的時候，預取硬件檢測到這些指示的預取度，然后用檢測到的預取度來預取指令。

本文研究的硬實時系統有NT個相互依賴的硬實時子任務，并發多任務的執行環境是一個基于靜態優先級的非搶占系統，每一個任務被分配給唯一的一個靜態優先級，如果多個任務被映射到同一核上執行，優先級高的任務先執行。如果任務開始執行，在它完成前，不允許被別的任務搶占。任務之間的小的通信和同步時是通過郵箱（mailbox），并且郵箱足夠大，消息不會溢出。消息在系統內部的通信狀況通過消息跟蹤語言MSC（Message Sequence Chart）描述。

2.2 能量模型

首先假設NT個硬硬實時任務已經被映射到相應的處理核上，并且獨占L2共享緩存的相應分區。

硬件預取器通過一些硬件表來實現，所以它的能量消耗可以被準確的模擬[5]，這里參照文獻[5]，硬件預取器由一個512 bit的FIFO預取緩沖器構成。

這里假設處理器的頻率是1.0 Hz，用的是32 nm 工藝，本文參照文獻[16]中的緩存能量消耗計算模型計算單個硬實時任務T 支持指令預取的最差情況下的緩存能量消耗，如公式（1），對于不同的預取度n(n ≥0)，當n為0時，表示沒有采用預取操作，這時候關閉預取器：在指令預取度是n 情況下任務T 最差情況下的緩存能耗E(T,n)，是由最差情況下的靜態能耗Estatic(n)和動態能耗Edynamc(n)組成的。其中Cstatic(n)，Pstatic(n)分別是緩存和硬件預取器的單位時間內的靜態能耗，tn是當預取度是n 時的任務最差情況執行時間WCET。動態能耗Edynamc(n)由緩存的動態能耗Ec_dynamc(n)和預取器的動態能耗Ep_dynamc(n)組成，Eaccess表示一次訪問緩存所消耗的能量，caccess(n)是當預取度為n 時的最差情況下訪問緩存次數。Emiss表示一次緩存缺失所消耗的能量，cmiss(n)是當預取度為n 時的最差情況下訪存缺失次數。Eprefetch表示一次預取時額外訪問緩存的能量消耗，cprefetch(n)表示最差情況下當預取度是n 時由于預取額外需要訪問緩存的次數，這里cprefetch(0)=0。Enext_access表示一次訪問下一級緩存所消耗的能量，Eup_stall表示由于緩存缺失，處理器停頓所消耗的能量，Eblock_fill表示把取回的指令填充到緩存所消耗的能量，Ep_access表示一次訪問預取器所消耗的能量，paccess(n)是最差情況下訪問預取器次數。

這里Cstatic、Pstatic、Eaccess、Eblock_fill、Ep_access通過CACTI5[17]測得，在32 nm工藝下，預取器消耗0.359 mW的靜態能耗，每次訪問的能耗是0.002 nJ。

對于每一個硬實時任務T 、tn、caccess(n)、cmiss(n)、paccess(n)通過支持指令預取的緩存WCET 分析工具[18]測得。

2.3 研究動機

對文獻[19]中的硬實時M?lardalen wcet benchmarks，如圖3 是不同預取度下支持指令預取的緩存WCEC，結果被不支持指令預取（預取度N 是0）的結果歸一化了。這里假設有4 個同構的處理器核，32 nm 工藝，芯片的頻率是1.0 GHz，5階段流水，順序執行，分支預測是完美的（perfect），L1 指令/數據緩存大小是256 Byte，緩存行大小是16 Byte，直接映射。L2 緩存大小是1 KB，緩存行大小是32 Byte，2路組關聯。

圖3 指令預取度對于緩存WCEC的影響

從圖可以看出順序指令預取在不同的預取度下獲得的能量效率不同，cnt最大，預取度是4時，最差情況下的能量減少43.7%，bsort100最差，在預取度是4時，能量反而增加了43.9%。這是因為由公式（4）可知，指令預取的能量獲益是減少的緩存靜態能耗和增加的預取器與緩存動態能耗中和的結果，每個程序的特性不同，預取效率不同，所以WCEC呈現的結果是非線性的。

運行在多核上的硬實時系統具有多個相互依賴的硬實時子任務，由于每個硬實時子任務的特性不同，所有任務采用相同的預取度，所有處理器核分配相同的L2 緩存因子，不利于提高硬實時系統的最差情況下能量效率。因此，就非常有必要對分配給硬實時系統中子任務的指令預取度和每個處理器的L2劃分因子進行進行調整，來優化系統的緩存WCEC。

3 支持指令預取和L2緩存劃分的WCEC優化

3.1 WCEC優化模型描述

本文為需要優化的硬實時多核系統建立下面的模型：

（1）多核處理器有NC個處理器核C={c1,c2,…,cNC}。

（2）T 是硬實時系統所有具有依賴關系的子任務的集合T={T1,T2,…,TNT}，子任務到NC個處理器核上的映射不固定。每個子任務都有一個時間截止期F={f1,f2,…,fNT}，整個系統有一個時間截止期SD。

（3）L2 共享緩存共有W 路，通過基于路的緩存劃分，分配給了NC個處理器核，每個核可以分配的L2緩存劃分因子可以是P={p1,p2,…,pW} ，其中pi=i ,(i=1,2,…,W)。

（4）D 是順序指令預取度集合D={d0,d1,…,dND}，其中di=i ,(i=0,1,…,ND)，由于太大的預取度會給多核系統的負載帶來沉重負擔，影響系統性能，這里本文設定預取度最大閾值為4，預取度為0 表示不支持指令預取，關閉指令預取器。

本文假設：

（1）L 是任務T 到處理器C 的映射，L：T →C，每個硬實時子任務被映射到一個處理器核。

（2）M 是任務T 到預取度D 的映射，M：T →D，每個硬實時子任務被設定一個指令預取度。

（3）R 是處理器C 到L2劃分P 的映射，R：C →P，每個處理器核指定一個L2緩存劃分因子。

通過硬實時系統的MSC，本文得到了硬實時系統任務之間的依賴關系，用Pred(Ti)來表示任務Ti的前驅的集合，只有Pred(Ti)中的任務都執行結束，任務Ti才可以執行。用Starti(L,M,R)表示任務Ti的在映射L、M 和R 下的開始時間，用Finishi(L,M,R)表示任務Ti在映射L、M 和R 下結束時間。那么任務Ti的開始時間是Ti所有前驅任務結束時間的最大值，如公式（8）：

任務Ti的結束時間是Ti開始時間與任務Ti本身在映射L、M 和R 最差執行時間WCETi(L,M,R)的和，如公式（9）：

硬實時系統的在映射L、M和R下的WCRT(L,M,R)是運行在所有核上任務的結束時間的最大值，如公式（10）所示：

用WCECi(L,M,R)表示硬實時系統的子任務Ti在映射L、M 和R 下最差情況下的緩存能量消耗，硬實時系統的在映射L、M 和R 下的最差情況下的緩存能量消耗WCEC(L,M,R)是所有子任務在映射L、M 和R 下的最差緩存能量消耗的和，如公式（11）：

本文的緩存能量優化目標是尋找映射L、M 和R，使得當在硬實時系統和它的所有子任務在滿足時間截止期的情況下，最小化其WCEC，即公式（12）～（14）：

3.2 優化WCEC的ILP方程

對于3.1 節中建立的結合指令預取和緩存劃分的WCEC優化模型，本文設計了的相應的ILP線性規劃方程，建立過程如圖4所示。

圖4 ILP線性規劃方程建立流程圖

從圖4 可以看到，對于一個硬實時系統，建立規劃方程首先初始化變量來確定處理器的核數、實時系統子任務數量、L2 緩存大小和預取度取值范圍。然后建立子任務到處理器核的約束，保證每個子任務被分配到唯一的一個處理器核上，建立核到L2緩存劃分的約束，確保每個處理器核擁有唯一的L2 緩存劃分因子，建立子任務到預取度的約束，保證每個子任務采用唯一的預取度。上面3個約束建立后，就可以通過建立子任務選取WCET和WCEC的約束來確定每個實時子任務的WCET和WCEC，再建立硬實時系統的WCRT和WCEC的約束，最后建立優化目標約束，使得整個硬實時系統的WCRT滿足時間截止期的情況下，最小化系統的WCEC。

3.2.1 任務到核的映射約束

C1 首先定義0-1變量Cij，表示任務Ti是否被映射到核Cj上，0 ≤Cij≤1,where 1 ≤i ≤NTand 1 ≤j ≤NC。

3.2.2 核到L2緩存劃分的約束

C3 如果L2緩存共有W 路，P={p1,p2,…,pW}，(pi=i)(i=1,2,…,W)是L2 緩存劃分因子，定義0-1 變量Lij，表示核Ci是否被分配了L2緩存劃分因子pj，0 ≤Lij≤1,where 1 ≤i ≤NCand 1 ≤j ≤W 。

3.2.3 任務選擇WCET和WCEC的約束

C6 如果任務可以選擇的預取度的集合D={d0,d1,…,dND}，di=i (i=0,1,…,ND)，定義0-1 變量Tijk，表示任務Ti是采用預取度dj，此時的L2緩存劃分因子是pk，因此有

C7 用數組W[i][j][k]存儲任務Ti采用預取度dj，L2緩存劃分因子是pk下的WCET，用整型變量Wi表示任務Ti應該選擇的WCET，因此有0 ,where 1 ≤ i ≤NT。

C8 用數組E[i][j][k]存儲任務Ti采用預取度dj，L2緩存劃分是pk下的WCEC，用整型變量Ei表示任務Ti應該選擇的WCEC，因此有0 ,where 1≤i≤NT

C9 定義0-1變量Aijkm，表示每一任務Ti被分配了唯一的處理器核Cj，預取度dk，L2 緩存劃分因子是pm，對1≤i≤NT,1≤j≤NC,0≤k≤ND,1≤m≤W 有：

3.2.4 硬實時系統WCRT和WCEC計算約束

C10 為了計算硬實時系統的WCRT，本文需要計算所有核上的任務的最晚結束時間。定義0-1 變量Mijk表示任務Ti與任務Tj是否映射到核Ck上，有：

把上面的方程線性化，有：

C11 定義另外一個0-1 變量Mij表示任務Ti與任務Tj是否映射到同一個處理器核上，有：

把上面的方程線性化：

C12 如果兩個任務Ti與Tj映射到同一個處理器核上，定義0-1 變量Bij，表示任務Ti在任務Tj之前執行，定義0-1變量Bji表示任務Tj在任務Ti之前執行，對于1≤i≤NT-1,i≤j≤NT有：

C13 對于任務Ti，用整型變量Si表示任務Ti的開始時間，用整型變量Fi表示任務Ti的結束時間，用0-1變量Dij表示任務Tj是否是任務Ti的直接后繼，有：

對于直接依賴的兩個任務，后繼任務的開始時間要小于前驅任務的結束時間，for ?Ti,Tj，有：

C14 對被映射到同一核上的任務，先執行的任務的結束時間要小于后執行任務的開始時間，有：

這里MC是比所有任務的WCET的和都大的一個常量。

C15 對于所有的任務根據公式（9），Fi-Si-Wi=0,1 ≤i ≤NT。

C16 對硬實時系統的WCRT，有WCRT-Fi≥0,1≤i≤NT。

3.2.5 優化目標

C18 本文優化的目標是硬實時系統和所有子任務滿足時間截止期SD 的情況下，最小化WCEC，即Minimize WCEC，當WCETi≤fi,1≤i≤NT，WCRT ≤SD。

4 實驗評估

本章評估提出的支持指令預取和L2緩存劃分的硬實時多核系統緩存WCEC優化方法。

4.1 評估環境

這里假設有4個同構的處理器核，32 nm工藝，芯片的頻率是1.0 GHz ，5階段流水，順序執行，分支預測是完美的（perfect），L1 指令/數據緩存大小是256 Byte，緩存行大小是16 Byte，直接映射。這里L2 行大小是32 Byte，16 組，L2 緩存是10 KB，通過CACTI5[17]收集能量計算參數，利用IBM CPLEX12.2 ILP 求解器[20]來求解WCEC優化方程。本文使用的benchmark是DEBIE，它是由Patria Finavitec和UniSpace Kent聯合開發的空間碎片探測器系統[21]，根據DEBIE 的系統狀態和功能，在文獻[22]中對子任務進行了并行化處理。

所有的實驗運行在Intel?Core?I5-3230 機器上，有4 GB內存，運行Ubuntu Linux 8.04操作系統。

4.2 實驗結果

本節中，任務映射由ILP方程確定，用下面的符號表示硬實時系統DEBIE在不同優化方法下的緩存WCEC。

（1）E_base：此時系統不支持指令預取優化，也不支持緩存劃分優化，通過路劃分技術[13]，L2 緩存被平均分配給了所有的處理器，它用作歸一化時的基底。

（2）E_ip（n）：文獻[8]中的緩存WCEC 優化方法，此時系統采用固定的指令預取度n，但不支持L2 緩存劃分優化。

（3）E_ocp：文獻[9]中的緩存WCEC優化方法，此時系統通過L2 緩存劃分來優化WCEC，但是系統不支持指令預取。

（4）E_oip+E_ocp：本文中的系統既支持L2 緩存劃分優化，也支持指令預取優化的緩存WCEC。

4.2.1 比較不同優化方法下的緩存WCEC

為了驗證本文優化方法的有效性，如圖5把本文中的結合指令預取及L2緩存劃分的緩存WCEC優化方法（E_oip+E_ocp）和已有的支持L2 緩存劃分（E_ocp）[9]和支持固定預取度（E_ip（n））[8]緩存WCEC優化方法進行比較，指令預取度 n 從1、2、3 到4。所有結果都被E_base歸一化了。

圖5 不同優化方法下的緩存WCEC

從圖5 可以看到，在不同的預取度 n 下，E_ip（n）都比E_base小，說明指令預取可以減少最差情況下的緩存能量消耗，這是因為指令預取的能量優化效率和訪存次數以及靜態能量在總能量中的比重有關系。在32 nm的處理器中，靜態能量消耗在總能量消耗中的比重增大，指令預取大大減少了系統的最差情況執行時間，因此盡管它增加了一部分動態能耗，它最終也能夠減少總的能量消耗。當預取度是2時，指令預取的能量獲益是最大的，達到了21.9%。L2 緩存劃分能耗E_ocp 比E_base 減少了6.3%，這說明L2 緩存劃分對于減少WCEC 也是有效的。E_ocp 是經過L2 緩存劃分優化后的WCEC，因此它比不優化的E_base要小。

這里還可以看到E_oip+E_ocp比E_ip（n）平均減少了22.5% ，比E_ocp 平均減少了36.6%，這說明本文中的緩存WCEC方法是有效的。當預取度是1，3和4時，本文的WCEC優化效率好于當預取度是2的情況，這是因為當預取度是2的時候，指令預取可以獲得最好的能量效益，此時本文方法能量優化效率比預取度是1，3和4時會降低。

4.2.2 L2 緩存大小對于優化方法的影響

為了分析L2緩存大小對于本文提出的優化方法的影響，圖6比較了不同L2緩存大小下的E_oip+E_ocp和E_base，L2緩存大小分別為4 KB、6 KB、8 KB和10 KB，所有結果都被E_base歸一化了。

圖6 不同L2大小的歸一化的緩存WCEC

從圖6中可以看到當L2緩存是10 KB的時候，本文的優化方法的能量效率最高。這說明本文的WCEC 優化方法的效率與L2 緩存大小有關系。當L2 緩存大于4 KB 的時候，緩存WCEC 已經被本文的方法優化到了最小，L2 緩存越大，計算E_base 時，分配給每個處理器的L2 緩存劃分因子越大，整個系統的執行時間并沒有顯著減少，因此靜態能耗變大，總的能耗也變大。當L2緩存是10 KB 時的E_base，比L2 緩存是4 KB、6 KB 和8 KB時的E_base要大，因此歸一化的結果越小，本文能耗優化效率越高。

4.2.3 處理器核的數目對于優化方法的影響

為了分析處理器核的數目對于本文提出的優化方法的影響，如圖7 比較了不同處理器核下的E_oip+E_ocp 和E_base，處理器的核數分別為2、3 和4，所有結果都被E_base歸一化了。

圖7 不同處理器核數下的歸一化的緩存WCEC

從圖7中看到，當處理器是2核的時候，通過本文方法優化后的最差緩存能量比不優化時的最差緩存能量減少了54.4%，這比處理器是3 核與4 核的時候要好。這是因為不同處理器核下的能耗優化效率與硬實時系統中子任務的并行度有很大的關系。從文獻[22]中可以看到，DEBIE 系統在某一時間點，至多有3 個子任務并行運行，當處理器的核數多于3時，E_base很少改變，而本文中的方法已經把WCEC優化到最小，所以對于3核與4核，優化效率也未改變。當處理器是2核時，本應該并行的子任務也需要串行執行，同3 核相比，利用本文方法，緩存WCEC優化的空間更大，效率提高的也越明顯。

5 結論

對于能耗有很高要求的并發多任務硬實時多核系統，本文提出支持指令預取和緩存劃分的緩存WCEC優化方法，該方法通過建立ILP 方程，調整子任務的預取度和L2緩存劃分因子對硬實時系統的最差情況下的緩存能耗進行優化。通過對粒子探測系統DEBIE 的分析，表明本文提出的支持指令預取和緩存劃分的緩存WCEC優化方法大大減少了系統的緩存WCEC，其優化的效率與硬實時系統任務的并行度與處理器數目，L2緩存大小有密切關系。

下一步，計劃改進本文的方法，對支持數據預取的并發多任務硬實時系統進行分析，并把指令預取和數據預取結合起來對硬實時系統地最差情況下的能耗進行優化。