多核共享資源沖突延遲上限優化方法*

張吉贊，苑雅娟

1.北京理工大學 計算機科學與技術學院，北京 100081

2.滄州醫學高等專科學校，河北 滄州 061001

多核共享資源沖突延遲上限優化方法*

張吉贊1，苑雅娟2+

1.北京理工大學 計算機科學與技術學院，北京 100081

2.滄州醫學高等專科學校，河北 滄州 061001

嵌入式多核結構的共享資源沖突是硬實時任務最差情況執行時間（worst-case execution time，WCET）估算的難點，而且通過減少共享資源沖突延遲的估算可以減少硬實時任務的WCET估算值，提高硬實時任務的可調度性。針對帶有沖突感知總線（interference-aware bus arbiter，IABA）的嵌入式多核結構，提出了一種基于bank-column緩存劃分的訪存請求沖突延遲上限優化方法，根據bank沖突次數和沖突延遲上限的關系，該方法通過優化bank到核映射來減少bank沖突發生次數，從而減小沖突延遲上限和WCET估算值。實驗結果表明，與現有沖突延遲上限界定方法相比，提出的方法能減少約29％的WCET估算值。

多核結構；硬實時任務；bank沖突；bank-column劃分；bank到核映射

1 引言

硬實時嵌入式系統對硬實時任務的執行時間有著嚴格的要求，每個硬實時任務必須在它的截止期前完成，否則就可能發生災難性事故[1]。硬實時系統通常依據硬實時任務的最差情況執行時間（worstcase execution time，WCET）對硬實時任務進行調度，以確保硬實時任務能在截止期前完成執行[2]。為保證硬實時任務在任何情況下的執行時間不會超過估算的WCET，分析并估算硬實時任務的WCET是至關重要的。

對于硬實時任務在單核系統中的WCET估算，前人提出了各種不同的WCET估算方法[3]，然而，多核結構在硬實時系統中的廣泛應用，給硬實時任務的WCET估算帶來了新的挑戰。這些多核結構往往存在核間可以共享使用的片上共享資源，如片上高速緩存和片上總線等，硬實時任務在同時訪問這些共享資源時會發生資源訪問沖突，給硬實時任務帶來不可預測的額外執行時間，為保證WCET估算是安全的，不得不考慮這些資源訪問沖突給硬實時任務的執行時間帶來的影響，而現有單核系統的WCET估算方法無法估算這些資源訪問沖突帶來的沖突延遲[4]。

片上共享緩存（L2緩存）是多核系統的一個重要共享資源，與之相關的任務間共享資源沖突包括：（1）storage沖突，該沖突是指使用相同緩存塊的硬實時任務在交替訪問該緩存塊時，一個任務會將其他任務的內存塊從該緩存塊中置換出去；（2）bank沖突，該沖突是指當多個任務同時申請訪問共享緩存的同一個bank時，只能有一個任務被允許訪問該bank，其他任務必須等待。目前，多bank結構已成為共享緩存設計的主要方向，一個多bank結構的共享緩存由多個bank組成[5]。在此基礎上，Yoon等人提出了bank-column緩存劃分機制[6]，共享緩存由多個bank構成，每個bank又被均勻劃分成多個column，其中核向bank作映射，硬實時任務向column作映射且獨占分配的column以消除storage沖突。

由于硬實時任務在共享緩存上的沖突延遲受到片上總線仲裁機制的影響[7]，現有方法通常結合片上總線的仲裁機制對硬實時任務的共享緩存沖突延遲進行分析，如結合時分多路復用（time division multiple access，TDMA）總線分析storage沖突和總線沖突[8]、結合沖突感知總線（interference-aware bus arbiter，IABA）或和諧輪詢總線分析bank沖突和總線沖突[6,9]等。在估算bank沖突延遲時，現有方法主要使用訪存請求可能遭受的bank沖突上限最大值來估算硬實時任務的bank沖突延遲[6,9]，這種粗放的bank沖突延遲估算方法雖然能簡化WCET估算且能保證其安全性，但使WCET估算過大，影響了嵌入式多核實時應用的適用范圍。

本文重點研究嵌入式多核結構中任務間共享資源沖突，旨在通過優化bank-column緩存劃分來減小請求的沖突延遲上限，從而減小WCET估算。其中嵌入式多核結構帶有IABA總線和bank-column劃分的L2緩存。鑒于現有緩存劃分或緩存鎖技術能夠消除storage沖突[9]，本文注重于共享緩存的bank沖突分析，主要貢獻如下：（1）基于IABA的bank-column緩存劃分，分析了請求的沖突延遲上限，并給出了計算方法。（2）設計了一個基于bank-column緩存劃分的沖突延遲上限優化方法，該方法通過優化bank到核映射來減少bank沖突次數，從而減小bank沖突延遲上限。

2 相關工作

對bank沖突、總線沖突和storage沖突的處理，現有研究成果主要集中在如下幾方面：

（1）bank沖突組合總線沖突。由于硬實時任務訪問bank的時機影響bank沖突的發生，現有研究通過設計總線仲裁策略來分析bank沖突延遲，同時使用共享緩存劃分來消除storage沖突。Paolieri等人[9]組合IABA總線仲裁器和共享L2緩存動態劃分來界定bank沖突延遲上限，該方法使用的L2緩存動態劃分包括bankization劃分或columnization劃分。其中，columnization劃分可以消除storage沖突，但存在bank訪問沖突；而bankization劃分可以同時消除storage沖突和bank訪問沖突，但要求任務獨占分配的bank，不能充分利用L2緩存，受bank數目的影響，限制了多核系統的工作負荷。Yoon等人[6]組合和諧輪詢總線仲裁策略和L2緩存的bank-column劃分來界定bank沖突上限。在該方法中，和諧輪詢總線仲裁策略將總線時槽固定地分配給不同的核，為了能夠界定bank沖突延遲上限需要優化總線時槽在核間的分配，該總線仲裁策略在實質上是一種TDMA總線仲裁策略。張吉贊等人[10]組合TDMA總線和L2緩存的bank-column劃分來分析bank沖突，并使用請求時間序列來估算bank沖突延遲。這種方法需要獲得每個硬實時任務的請求時間序列，以用來估算每個請求遭受的bank沖突延遲。

（2）總線沖突組合storage沖突。另有一些研究成果將storage沖突分析和總線訪問沖突分析結合起來進行WCET分析，但在分析時沒有考慮bank訪問沖突問題。Kelter等人[11]通過界定TDMA偏移量上界來分析總線沖突延遲，并使用擴展的緩存抽象解釋（abstract translation）方法分析了storage沖突。Chattopadhyay等人[8]提出融合共享緩存和TDMA總線的WCET分析框架，在分析總線訪問延遲時，根據執行上下文，令請求的總線訪問延遲為可能遭受的最大總線訪問延遲。Nagar等人[12]提出了WCIP（worst case interference placement）方法來分析storage沖突，并組合TDMA總線仲裁策略來估算多核系統的WCET。

（3）storage沖突。還有一些研究成果將分析重點僅放在storage沖突上，均沒有考慮bank沖突延遲和總線訪問延遲對WCET的影響。Chen等人[13]通過指令的取指時間關系，分析了進程在共享緩存上的storage沖突。Ding等人[14]提出動態鎖指令緩存的方法來消除storage沖突，該方法可靈活鎖定循環結構對應的緩存空間。康少華等人[15]使用緩存劃分技術來減少storage沖突，從而改善并行程序的WCRT。安立奎等人[16]使用軟件預取技術來減少storage沖突和WCET估算值。

本文著重研究bank沖突問題，與上述方法的不同之處在于：（1）組合IABA總線仲裁策略和bankcolumn緩存劃分對bank沖突延遲上限進行分析；（2）通過優化bank到核的映射關系減小bank沖突延遲上限。

3 系統模型及亟需解決的關鍵問題

3.1 嵌入式多核結構

一個嵌入式多核處理器含有Ncore個支持多發射有序流水線的同構核，表示為C={c1,c2,…,cNcore}。每個核有自己私有的第一級數據緩存和指令緩存。由所有核共享使用的第二級緩存（L2緩存）采用bankcolumn緩存劃分機制[6]，該緩存劃分機制先將L2緩存劃分成Nbank個大小相等的bank，表示為B={b1,b2,…,bNbank}，然后將每個bank進一步劃分成相等的Ncolumn個column。L2緩存完成一次請求需要的時間為LM個時鐘周期。連接L2緩存和核的實時總線是全雙工IABA總線[9]，總線完成一次請求所需要的時間為LB個時鐘周期。請求訪問L2緩存發生缺失時，需要訪問主存。

IABA總線仲裁器由兩層組件構成：（1）一個核間總線仲裁器XCBA（inter-core bus arbiter），對核間請求進行仲裁調度。XCBA在進行仲裁時，能判斷是否有總線沖突或bank沖突發生，若有沖突，則延遲后續請求訪問總線，以避免發生總線沖突和bank沖突。（2）每個核有一個核內部總線仲裁器ICBA（intracore bus arbiter），對來自同核的請求進行仲裁調度。若有多個請求同時申請訪問L2緩存，ICBA選擇一個請求轉發給XCBA，其他請求在ICBA中等待。

3.2 多任務應用模型

一個多任務實時應用由硬實時任務和非硬實時任務組成，用Γhrt表示硬實時任務集合。所有任務已通過非搶占式調度分配到Ncore核上，用Chrt(?C)表示分配有硬實時任務的核集，Nhrt(≤Ncore)是Chrt中的核數，只有一個核只分配有非硬實時任務，表示為cnhrt(∈C)。在最差情況下，Chrt中的所有核都在執行硬實時任務，即最多有Nhrt個硬實時任務同時運行。

完成任務向核的分配后，需要確定核需要的L2緩存的大小。首先，為帶有硬實時任務的核分配L2緩存，設HTi是分配到核ci的硬實時任務集合，任務τj(∈HTi)需要的L2緩存的大小為 Sj個column，則核ci需要的L2緩存的大小為Sz(ci)=max(Sj|1≤j≤ni)個column，其中ni為集合HTi中的任務數，分配給ci的L2緩存由HTi中的任務獨占使用；其次，為只帶有非硬實時任務的核分配緩存，若cnhrt≠?，則將剩余的column分配給該核，供該核的非硬實時任務獨占使用。這種分配方式具有如下特點：（1）任務獨占分配的column，不存在storage沖突；（2）一個bank可由多個核共享使用，當多個請求同時申請訪問同一個bank時，發生bank沖突；（3）Nbank×Ncolumn個column在Ncore個核間的不同分配對應著不同的bank到核映射。

另外，采用Li等人[17]提到的方法處理任務間的共享代碼和任務間的通信。如果多個任務共享使用某個函數或程序段，則為每個任務復制一份以取消任務間代碼共享。若任務間需要通信則采用郵箱機制來取消由同步帶來的影響。

3.3 亟需解決的關鍵問題

Paolieri等人[9]提出了用請求可能遭受的沖突延遲最大值UBD來估算沖突延遲的方法。在該方法中，多核結構帶有IABA和動態緩存劃分機制。L2緩存的動態劃分技術采用columnization劃分或bankization劃分，其中columnization劃分將片上L2緩存劃分成多路（way），每個硬實時任務獨占分配的路，不存在storage沖突，但硬實時任務共享一個bank，存在bank訪問沖突，若只有硬實時任務，UBD=(Nhrt-1)×LM，否則，UBD=(Nhrt-1)×LM-1；ba-nkization劃分將片上L2緩存劃分成多bank，每個硬實時任務獨占分配的bank，不存在storage沖突和bank訪問沖突，若只有硬實時任務，UBD=(Nhrt-1)×LB，否則，UBD=(Nhrt-1)×LB-1。受L2緩存容量的限制，若bankization劃分不能滿足硬實時任務的需求，則采用columization劃分。

雖然bankization劃分能使UBD最小，但要求硬實時任務獨占分配的bank，不能有效使用共享緩存。而在bank-column劃分中，L2緩存能在核間被靈活地分配，當bankization劃分不能滿足硬實時任務的需求時，使用bank-column劃分，并適當調整bank到核映射，能夠減小UBD。如在圖1所示的例子中，圖1（a）是columnization劃分，在一次XCBA調度中，HRT4(c4)的請求遭受的沖突延遲最大，12個時鐘周期，UBD=12個時鐘周期；圖1（b）是bank-column劃分的一個bank到核映射，在一次XCBA調度中，HRT4(c4)的請求遭受的沖突延遲最大，8個時鐘周期，UBD=8個時鐘周期。

Fig.1 Example of interference delay on XCBA圖1 請求在XCBA上的沖突延遲舉例

綜上所述，緩存的bank-column劃分能夠減小UBD的值，在不同的bank到核映射中，UBD的值也不盡相同。為此，本文擬通過優化bank到核映射來減小UBD的值，從而減小WCET的估算值。

4 利用bank到核映射優化UBD

4.1UBD分析

在最差情況下，Chrt中的Nhrt個核都在執行硬實時任務，設同時運行的Nhrt個硬實時任務為{HRT1,HRT2,…,HRT(Nhrt)}，對應的核為 {c1′,c2′,…,c(Nhrt)′}，當 Nhrt個硬實時任務同時請求總線時，來自HRTi(1≤i≤Nhrt)的請求是第i個被XCBA選中訪問總線。為了方便描述，用c0′表示只帶有非硬實時任務的核cnhrt。在XCBA的一次調度中，Nhrt個硬實時任務都有請求申請總線，來自HRT1,HRT2,…,HRT(Nhrt)的請求分別用q1,q2,…,q(Nhrt)表示，qi(1≤i≤Nhrt)可能遭受的最大任務間沖突延遲分別用di表示。若c0′≠?，用q0表示來自c0′的請求。分兩種情形分析UBD。

（1）c0′=?。q1不遭受任務間沖突，d1=0。請求qi(1≤i≤Nhrt)可能遭受的最大任務間沖突延遲可表示為式（1）：

其中，Zi表示前i個請求之間發生bank沖突的次數。

例如，在圖2所示的例子中，Z3=1，來自HRT3的請求遭受的最大任務間沖突延遲為2×LB+1×(LM-LB)=6個時鐘周期。請求q(Nhrt)可能遭受的任務間沖突延遲最大，為(Nhrt-1)×LB+Z(Nhrt)×(LM-LB)。由此，在無非硬實時任務時，UBD可表示為式（2）：

Fig.2 Example of inter-task interference delay without non hard real-time tasks圖2 無非硬實時任務時請求遭受的任務間沖突延遲舉例

（2）c0′≠?。q1可能遭受的最大任務間沖突延遲為(LB-1)+Z1×(LM-LB)。請求qi(1≤i≤Nhrt)可能遭受的最大任務間沖突延遲di為(LB-1)+(i-1)×LB+Zi×(LM-LB)，可表示為式（3）：

例如，在圖3所示的例子中，Z2=1，來自HRT2的請求可能遭受的最大任務間沖突延遲為2×LB+1×(LM-LB)-1=5個時鐘周期。請求q(Nhrt)可能遭受的任務間沖突延遲最大，為 Nhrt×LB+Z(Nhrt)×(LM-LB)-1。由此，存在非硬實時任務時，UBD可表示為式（4）：

Fig.3 Example of inter-task interference delay with non hard real-time tasks圖3 存在非硬實時任務時請求遭受的任務間沖突延遲舉例

4.2 優化問題描述

從式（2）和式（4）可知，減少請求發生bank沖突的次數能減小UBD的值，從而減小WCET的估算值。用xik表示bk(∈B)是否有column分配給ci(∈C)，若有，則xik=1；否則，xik=0。用ncik表示bk分配給ci(∈C)的column數目，如果xik=1，則 ncik＞0；否則，ncik=0。由于任務獨占分配給它的column，ncik是整數。以xik和ncik為決策變量，優化bank到核的映射關系使請求的沖突延遲上界最小的形式化描述如下。

（1）優化目標

根據式（2）和式（4），優化目標可表示為min(Z(Nhrt))。

（2）約束條件

當1≤i≤Nhrt，前i個請求之間發生bank沖突的次數Zi可表示為式（6）：

L2緩存容量應滿足硬實時任務的需求，即：

若c0′≠?，則將剩余的column分配給c0′，如式（8）所示：

分配給每個硬實時任務核的column數應滿足該核的需要，即：

在分配L2緩存時，應滿足每個bank的容量限制，即：

4.3 求解算法

前面描述的優化問題是一個資源分配問題，是NP難的。該問題的求解過程如下：

（1）為 Ncore個核分配L2緩存。Nbank×Ncolumn個column在Ncore個核間進行分配，可以形成多個bank到核映射。

（2）對于每個bank到核映射，根據式（5）和式（6）計算Z(Nhrt)。

（3）輸出最小 Z(Nhrt)。

該優化問題的一個遞歸回溯算法如算法1所示。在該算法中，第2～18行定義函數FindMinMapping(n)，第4行根據核次序Cseq[Ncore]作bank到核的映射，第5行計算bank沖突次數，第6～9行更新結果，第12～17行回溯搜索解空間。

算法1尋找一個bank到核的映射關系使Z(Nhrt)最小

輸入：C，Ncore，Chrt，Nhrt，cnhrt，B，Nbank，Ncolumn，Sz(ci)，?ci∈C

輸出：最小的Z(Nhrt)及對應的bank到核的映射MinMap[][]

1.Z(Nhrt)=infinity,used[i]=FALSE;

2.FunctionFindMinMapping(n)

3.If(n＞Ncore)then

4.根據Cseq[]作bank到核的映射BtoCMap[][]；

5.根據式（5）和式（6），計算在映射 BtoCMap[][]中的bank沖突次數(TempZ)；

6.If(TempZ＜Z(Nhrt))then

7.Z(Nhrt)=TempZ;

8.MinMap[][]=BtoCMap[][];

9.End if

10.Return

11.End if

12.For(i=1;i≤Ncore;i++)do

13.If(!used[i])then

14.Cseq[n]=ci;used[i]=TRUE;

15.FindMinMapping(n+1);used[i]=FALSE;

16.End if

17.End for

18.End function

19.調用FindMinMapping(1);

20.ReturnZ(Nhrt),MinMap[][];

算法1的第4行按照Ncore個核的某個次序作bank到核映射，根據核需要的L2緩存容量，分如下3種情形作bank到核的映射。

算法2給出了按照Ncore個核的某個次序作bank到核映射的算法。在該算法中，某個核序列存放在Cseq[]中，根據核序列Cseq[]作bank到核映射關系BtoCMap[Ncore][Nbank]。第2～11行處理第（1）種情形，作bank到核映射；第14～21行調整參與分配的column數；若是第（3）種情形，第17～20行調整每個bank參與分配的column數；若是第（2）種情形或第（3）種情形，第26～41行作bank到核映射。

算法2按照Ncore個核的一個次序作bank到核映射

輸入：C,Sz(ci)(ci∈C),Chrt,cnhrt,Ncore,B,Nbank,Ncolumn,Cseq[Ncore]

輸出：一個bank到核映射(BtoCMap[Ncore][Nbank])

//處理第（1）種情形

2.k=1;

3.For(i=1;i≤Ncore;i++)do

4.If(ci∈Chrt)then

7.End if

8.End for

9.If(k＜Nbankandcnhrt≠?)then

10.將b(k+1)～b(Nbank)分配給cnhrt;

11.End if

12.Else

14.For(i=1;i≤Nbank;i++)do

15.If(k==0)then

16.bank[i]=Ncolumn;

17.Else

//調整每個bank中參與分配的column數

20.End if

21.End for

22.nbank=1,ncol=bank[1];

23.While(i≤Ncore)do

//依照核的次序為各核分配緩存

24.將核Cseq[i]在核集C中對應的序號存放在j中，需要的column數存放在nc_col;

25.If(nc_col≥ncol)then

26.While(nc_col≥ncol)do

27.BtoCMap[j][nbank]=ncol;

28.nc_col=nc_col-ncol;nbank++;

29.ncol=bank[nbank];

30.End while

31.If(nc_col==0)then

32.i++;

33.Else

34.BtoCMap[j][nbank]=nc_col;

35.ncol=ncol-nc_col;i++;

36.End if

37.Else

38.BtoCMap[j][nbank]=nc_col;

39.ncol=ncol-nc_col;i++;

40.End if

41.End while

42.End if

43.ReturnBtoCMap[][];

上述算法需要計算在每個bank到核映射中bank沖突可能發生的最大次數，復雜性為O(Ncore!)。

5 WCET估算

根據優化后的結果，利用式（2）和式（4）可以計算出UBD的值。在支持IABA總線的多核系統中，一次L2緩存訪問所需要的時間應該包括：在ICBA中的等待時間、在XCBA上遭受的沖突延遲（UBD）和訪問L2緩存的時間(LM)。

請求在ICBA中的等待時間是從該請求申請總線開始到該請求被送至XCBA為止的時間間隔。由于與前一個請求（來自同一個核）之間存在時間重疊，則需要進行去重處理，此時，請求在ICBA中的等待時間是從前一個請求（來自同一個核）完成L2緩存訪問開始到該請求被送至XCBA為止的時間間隔。例如，圖4顯示了沒有非硬實時任務時請求在ICBA中的等待時間，請求在ICBA中的最大等待時間也是UBD。

Fig.4 Example of maximum waiting time in ICBA圖4 請求在ICBA中的最大等待時間舉例

由此，在使用UBD估算WCET時，每個訪問L2緩存的請求遭受的沖突延遲上限為2UBD。一次L2緩存訪問的時間可以估算為2LB+2UBD+LM，其中2LB為請求和取回的數據通過總線的時間。在某個bank到核映射中，2LB+2UBD+LM是常數，因此可以直接用單核WCET估算工具（如Chronos[18]）估算硬實時任務的WCET。

6 實驗驗證

6.1 實驗環境和測試程序

由8個同構核{c1,c2,…,c8}組成的多核系統中，每核有一個有序5級流水線，無分支預測功能，取指隊列大小為4，取指寬度為2，指令窗大小為8。每核有私自L1數據和L1指令緩存，大小均為64 Byte，1個bank，2路關聯，每line有8 Byte，1個時鐘周期的訪問時間，采用LRU替換策略。L2緩存為所有核共享，大小為4 KB，被均勻劃分成4個bank，每bank大小為1 KB，4路關聯，每line有32 Byte，4個時鐘周期訪問時間（即LM=4），采用LRU替換策略。每個bank又被均勻劃分成8個column。每個column的大小為128 Byte（即1組4路關聯的line）。連接L2緩存和核的總線為IABA實時總線，一次請求通過總線需要2個時鐘周期，即LB=2。主存為256 MB×16 DDR2-800C，并分為4個bank。請求訪問L2緩存發生缺失時，需訪問主存，使用Paolieri等人[19]的方法估算請求訪問主存的時間。

使用的所有測試程序是M?lardalen WCET benchmark測試程序集[20]的一部分，使用Chronos測量了這些測試程序在單核系統中分配給不同L2緩存大小時的WCET，根據測量結果給測試程序分配合適的L2緩存大小，如表1所示，在該表中也列出了實驗中采用的任務到核的映射關系。

Table1 Allocated L2 cache size and task to core mapping表1 分配的L2緩存大小以及任務到核映射

6.2 實驗結果

在表1中的任務都為硬實時任務或存在非硬實時任務（matmult為非硬實時任務）時，使用算法1得到的一個最優bank到核映射如表2所示，在該映射關系中，Zi=0(1≤i≤7)。

（1）當表1中的任務都為硬實時任務時，在表2所示的bank到核映射中，Zi=0(1≤i≤7)，由式（2）可知，UBD=(7-1)×2=12個時鐘周期；若使用Paolieri等人[9]的方法，只能采用columnization劃分，UBD=(7-1)×4=24個時鐘周期；使用本文提出的bank到核映射優化方法和Paolieri等人的方法分別估算了訪存請求延遲上限，并使用Chronos估算了任務的WCET，其結果如圖5所示。在該圖中，所有結果都是相對于任務不遭受共享資源沖突時的WCET（用Chronos獲得）。其中，“Opt_UBD”表示用優化bank到核映射估算的結果，“Base_UBD”表示用Paolieri等人的方法估算的結果。相對于Paolieri等人的方法，本文提出的bank到核映射優化方法平均減少了約29％的WCET估算值，其中對bsort100的WCET估算值改善程度最大，減少了約38％，而對select的WCET估算值改善程度最小，減少了約19％。

Table2 An optimal relation of bank to core mapping表2 一個最優bank到核映射關系

Fig.5 Estimation results without non hard real-time tasks圖5 不存在非硬實時任務時的估算結果

（2）matmult為非硬實時任務，其他為硬實時任務，在表2所示的bank到核映射中，由式（4）可知，UBD=6×2-1=11個時鐘周期；若使用Paolieri等人的方法，也只能采用columnization劃分，UBD=6×4-1=23個時鐘周期。分別使用兩種方法估算的WCET如圖6所示。相對于用Paolieri等人的方法，本文提出的bank到核映射優化方法平均減少了約30％的WCET估算值，其中對bsort100的WCET估算值改善程度最大，減少了約39％，而對select的WCET估算值改善程度最小，減少了約20％。

主要原因：首先，在bank-column緩存劃分中，L2緩存能夠在核間被靈活地分配，一個bank可以被不同的核共享使用，減小了發生bank沖突的機會，從而減小了UBD的值，通過優化bank到核映射可以得到具有最小bank沖突次數的bank到核映射關系；其次，硬實時任務WCET估算值的減小程度與該任務訪問L2緩存的次數和程序規模有關，訪問次數越多，減小程度越大，而程序規模越小，減小程度越大。

Fig.6 Estimation results with non hard real-time tasks圖6 存在非硬實時任務時的估算結果

7 結束語

本文提出了一種基于bank-column緩存劃分的沖突延遲上限優化方法，該方法通過優化bank到核映射來減小請求的沖突延遲上限。

對于帶有IABA總線和bank-column緩存劃分機制的多核系統，分析了訪存請求的沖突延遲上限；在此基礎上，根據bank沖突次數與沖突延遲上限的關系，利用bank到核映射優化沖突延遲上限。

實驗結果表明，與現有沖突延遲上限界定方法相比，提出的bank到核映射優化方法能減小約29％的WCET估算值。

[1]Thiele L,WilhelmR.Design for timing predictability[J].Real-Time Systems,2004,28(2/3):157-177.

[2]DavisR I,BurnsA.Asurvey of hard real-time scheduling for multiprocessor systems[J].ACM Computing Surveys,2011,43(4):1-44.

[3]WilhelmR,Mitra T,Mueller F,et al.The worst-case execution-time problem-overview of methods and survey of tools[J].ACM Transactions on Embedded Computing Systems,2008,7(3):36.

[4]Guan Nan,Stigge M,Wang Yi,et al.Cache-aware schedulingand analysis for multicores[C]//Proceedings of the 9th ACM&IEEE International Conference on Embedded Software,Grenoble,France,Oct 12-16,2009.New York:ACM,2009:245-254.

[5]Kaseridis D,Stuecheli J,John L K.Bank-aware dynamic cache partitioning for multicore architectures[C]//Proceedings of the 2009 International Conference on Parallel Processing,Vienna,Austria,Sep 22-25,2009.Washington:IEEE Computer Society,2009:18-25.

[6]Yoon M K,Kim J E,Sha L.Optimizing tunable WCET with shared resource allocation and arbitration in hard real-time multicore systems[C]//Proceedings of the 32nd Real-Time Systems Symposium,Vienna,Austria,Nov 29-Dec 2,2011.Washington:IEEE Computer Society,2011:227-238.

[7]Axer P,ErnstR,Falk H,et al.Building timing predictable embedded systems[J].ACM Transactions on Embedded Computing Systems,2014,13(4):82.

[8]Chattopadhyay S,Chong L K,RoychoudhuryA,et al.Aunified WCET analysis framework for multi-core platforms[C]//Proceedings of the 18th Real Time and Embedded Technology and Applications Symposium,Beijing,Apr 16-19,2012.Washington:IEEE Computer Society,2012:99-108.

[9]Paolieri M,Qui?ones E,Cazorla F J,et al.Hardware support for WCET analysis of hard real-time multicore systems[C]//Proceedings of the 36th International Symposium on Computer Architecture,Austin,USA,Jun 20-24,2009.New York:ACM,2009:57-68.

[10]Zhang Jizan,Gu Zhimin.Analyzing bank access conflict and minimizing bank conflict delay for shared cache in multicore[J].Chinese Journal of Computers,2016,39(9):1883-1899.

[11]Kelter T,Falk H,Marwedel P,et al.Bus-aware multicore WCET analysis through TDMA offset bounds[C]//Proceedings of the 23rd Euromicro Conference on Real-Time Systems,Porto,Portugal,Jul 5-8,2011.Washington:IEEE Computer Society,2011:3-12.

[12]Nagar K,Srikant Y N.Fast and precise worst-case interference placement for shared cache analysis[J].ACM Transactions on Embedded Computing Systems,2016,15(3):45.

[13]Chen Fangyuan,Zhang Dongsong,Wang Zhiying.Static analysis of run-time inter-thread interferences in shared cache multi-core architectures based on instruction fetching timing[C]//Proceedings of the 2011 IEEE International Conference on Computer Science and Automation Engineering,Shanghai,Jun 11-12,2011.Piscataway,USA:IEEE,2011:208-212.

[14]Ding Huping,Liang Yun,Mitra T.WCET-centric dynamic instruction cache locking[C]//Proceedings of the 2014 Conference on Design,Automation&Test in Europe,Dresden,Germany,Mar 24-28,2014.Piscataway,USA:IEEE,2014:1-6.

[15]Kang Shaohua,Gu Zhimin,Fu Yinxia,et al.Parallelization and WCRT analysis of space debris detector-DEBIE[J].Application Research of Computers,2015,32(11):3283-3290.

[16]An Likui,Gu Zhimin,Fu Yinxia,et al.WCET analysis of unified cache with software prefetching[J].Transactions of Beijing Institute of Technology,2015,35(7):730-736.

[17]Li Yan,Suhendra V,Liang Yun,et al.Timing analysis of concurrent programs running on shared cache multi-cores[C]//Proceedings of the 30th Real-Time Systems Symposium,Washington,Dec 1-4,2009.Washington:IEEE Computer Society,2009:57-67.

[18]Li Xianfeng,Liang Yun,Mitra T,et al.Chronos:a timing analyzer for embedded software[J].Science of Computer Programming,2007,69(13):56-67.

[19]Paolieri M,Mische J,Metzlaff S,et al.Ahard real-time capable multi-core SMT processor[J].ACM Transactions on Embedded Computing Systems,2013,12(3):1-25.

[20]Gustafsson J,BettsA,ErmedahlA,et al.The M?lardalen WCET benchmarks:past,present and future[C]//Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis,Brussels,Belgium,Jul 7-9,2010.Vienna,Austria:Austrian Computer Society,2010:136-146.

附中文參考文獻：

[10]張吉贊,古志民.多核共享緩存的bank沖突分析及其延遲最小化[J].計算機學報,2016,39(9):1883-1899.

[15]康少華,古志民,付引霞,等.空間碎片探測軟件的并行化及WCRT分析[J].計算機應用研究,2015,32(11):3283-3290.

[16]安立奎,古志民,付引霞,等.支持軟件預取的緩存WCET分析[J].北京理工大學學報,2015,35(7):730-736.

ZHANG Jizan was born in 1973.He is a Ph.D.candidate at School of Computer Science and Technology,Beijing Institute of Technology.His research interests include computer architecture and computer network,etc.張吉贊（1973—），男，山東青島人，北京理工大學計算機科學與技術學院博士研究生，主要研究領域為計算機體系結構，計算機網絡等。

《計算機工程與應用》投稿須知

中國科學引文數據庫（CSCD）來源期刊、北大中文核心期刊、中國科技核心期刊、RCCSE中國核心學術期刊、《中國學術期刊文摘》首批收錄源期刊、《中國學術期刊綜合評價數據庫》來源期刊，被收錄在《中國期刊網》、《中國學術期刊（光盤版）》、英國《科學文摘》（SA/INSPEC）、俄羅斯《文摘雜志》（AJ）、美國《劍橋科學文摘》（CSA）、美國《烏利希期刊指南》（Ulrich’s PD）、《日本科學技術振興機構中國文獻數據庫》（JST）、波蘭《哥白尼索引》（IC），中國計算機學會會刊

《計算機工程與應用》是由中華人民共和國中國電子科技集團公司主管，華北計算技術研究所主辦的面向計算機全行業的綜合性學術刊物。

辦刊方針堅持走學術與實踐相結合的道路，注重理論的先進性和實用技術的廣泛性，在促進學術交流的同時，推進科技成果的轉化。覆蓋面寬、信息量大、報道及時是本刊的服務宗旨。

報導范圍行業最新研究成果與學術領域最新發展動態；具有先進性和推廣價值的工程方案；有獨立和創新見解的學術報告；先進、廣泛、實用的開發成果。

主要欄目理論與研發，大數據與云計算，網絡、通信與安全，模式識別與人工智能，圖形圖像處理，工程與應用，以及其他熱門專欄。

注意事項為保護知識產權和國家機密，在校學生投稿必須事先征得導師的同意，所有稿件應保證不涉及侵犯他人知識產權和泄密問題，否則由此引起的一切后果應由作者本人負責。

論文要求學術研究：報道最新研究成果，以及國家重點攻關項目和基礎理論研究報告。要求觀點新穎，創新明確，論據充實。技術報告：有獨立和創新學術見解的學術報告或先進實用的開發成果，要求有方法、觀點、比較和實驗分析。工程應用：方案采用的技術應具有先進性和推廣價值，對科研成果轉化為生產力有較大的推動作用。

投稿格式1.采用學術論文標準格式書寫，要求文筆簡練、流暢，文章結構嚴謹完整、層次清晰（包括標題、作者、單位（含電子信箱）、摘要、關鍵詞、基金資助情況、所有作者簡介、中圖分類號、正文、參考文獻等，其中前6項應有中、英文）。中文標題必須限制在20字內（可采用副標題形式）。正文中的圖、表必須附有圖題、表題，公式要求用MathType編排。論文字數根據論文內容需要，不做嚴格限制，對于一般論文建議7 500字以上為宜。2.請通過網站（http://www.ceaj.org）“作者投稿系統”一欄投稿（首次投稿須注冊）。

Optimization of Upper Bound of Interference Delay in Multicore*

ZHANG Jizan1,YUAN Yajuan2+
1.School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China
2.Cangzhou Medical College,Cangzhou,Hebei 061001,China
+Corresponding author:E-mail:hbdlyyj@163.com

ZHANG Jizan,YUAN Yajuan.Optimization of upper bound of interference delay in multicore.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1224-1234.

The inter-task interferences on the shared resources of embedded multicore are the difficulty for the WCET(worst-case execution time)estimation of hard real-time tasks.Moreover,the decrease of the delay caused by the interferences on the shared resources can reduce the estimated WCET and improve the schedulability of hard real-time tasks.This paper proposes an optimization method to reduce the upper bound of inter-task interference delay in the multicore with interference-aware bus arbiter(IABA).According to the relationship between the upper bound of inter-task interference delay and the count of bank conflict,this paper optimizes bank to core mapping to reduce the count of bank conflict,and then reduces the upper bound of inter-task interference delay and the estimated WCET.Compared with existing methods,the proposed method can reduce about 29％of the estimated WCET.

multicore;hard real-time task;bank conflict;bank-column partitioning;bank to core mapping

an was born in 1979.She

the M.S.degree in computer science from North China Electric Power University in 2007.Her research interests include embedded system and computer architecture,etc. 苑雅娟（1979—），女，河北保定人，2007年于華北電力大學獲得碩士學位，主要研究領域為嵌入式系統，計算機結構等。

A

：TP302.7

*The National Natural Science Foundation of China under Grant No.61370062(國家自然科學基金).Received 2017-01,Accepted 2017-05.

CNKI網絡優先出版:2017-05-17,http://kns.cnki.net/kcms/detail/11.5602.TP.20170517.0944.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1224-11

10.3778/j.issn.1673-9418.1701043

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056