張吉贊，苑雅娟

1.北京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 100081

2.滄州醫(yī)學(xué)高等?？茖W(xué)校，河北 滄州 061001

多核共享資源沖突延遲上限優(yōu)化方法*

張吉贊1，苑雅娟2+

1.北京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 100081

2.滄州醫(yī)學(xué)高等?？茖W(xué)校，河北 滄州 061001

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

多核結(jié)構(gòu)；硬實(shí)時任務(wù)；bank沖突；bank-column劃分；bank到核映射

1 引言

硬實(shí)時嵌入式系統(tǒng)對硬實(shí)時任務(wù)的執(zhí)行時間有著嚴(yán)格的要求，每個硬實(shí)時任務(wù)必須在它的截止期前完成，否則就可能發(fā)生災(zāi)難性事故[1]。硬實(shí)時系統(tǒng)通常依據(jù)硬實(shí)時任務(wù)的最差情況執(zhí)行時間（worstcase execution time，WCET）對硬實(shí)時任務(wù)進(jìn)行調(diào)度，以確保硬實(shí)時任務(wù)能在截止期前完成執(zhí)行[2]。為保證硬實(shí)時任務(wù)在任何情況下的執(zhí)行時間不會超過估算的WCET，分析并估算硬實(shí)時任務(wù)的WCET是至關(guān)重要的。

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 系統(tǒng)模型及亟需解決的關(guān)鍵問題

3.1 嵌入式多核結(jié)構(gòu)

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

IABA總線仲裁器由兩層組件構(gòu)成：（1）一個核間總線仲裁器XCBA（inter-core bus arbiter），對核間請求進(jìn)行仲裁調(diào)度。XCBA在進(jìn)行仲裁時，能判斷是否有總線沖突或bank沖突發(fā)生，若有沖突，則延遲后續(xù)請求訪問總線，以避免發(fā)生總線沖突和bank沖突。（2）每個核有一個核內(nèi)部總線仲裁器ICBA（intracore bus arbiter），對來自同核的請求進(jìn)行仲裁調(diào)度。若有多個請求同時申請?jiān)L問L2緩存，ICBA選擇一個請求轉(zhuǎn)發(fā)給XCBA，其他請求在ICBA中等待。

3.2 多任務(wù)應(yīng)用模型

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

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

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

3.3 亟需解決的關(guān)鍵問題

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

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

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

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

4 利用bank到核映射優(yōu)化UBD

4.1UBD分析

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

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

其中，Zi表示前i個請求之間發(fā)生bank沖突的次數(shù)。

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

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

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

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

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

4.2 優(yōu)化問題描述

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

（1）優(yōu)化目標(biāo)

根據(jù)式（2）和式（4），優(yōu)化目標(biāo)可表示為min(Z(Nhrt))。

（2）約束條件

當(dāng)1≤i≤Nhrt，前i個請求之間發(fā)生bank沖突的次數(shù)Zi可表示為式（6）：

L2緩存容量應(yīng)滿足硬實(shí)時任務(wù)的需求，即：

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

分配給每個硬實(shí)時任務(wù)核的column數(shù)應(yīng)滿足該核的需要，即：

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

4.3 求解算法

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

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

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

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

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

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

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

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

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

2.FunctionFindMinMapping(n)

3.If(n＞Ncore)then

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

5.根據(jù)式（5）和式（6），計(jì)算在映射 BtoCMap[][]中的bank沖突次數(shù)(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.調(diào)用FindMinMapping(1);

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

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

算法2給出了按照Ncore個核的某個次序作bank到核映射的算法。在該算法中，某個核序列存放在Cseq[]中，根據(jù)核序列Cseq[]作bank到核映射關(guān)系BtoCMap[Ncore][Nbank]。第2～11行處理第（1）種情形，作bank到核映射；第14～21行調(diào)整參與分配的column數(shù)；若是第（3）種情形，第17～20行調(diào)整每個bank參與分配的column數(shù)；若是第（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

//調(diào)整每個bank中參與分配的column數(shù)

20.End if

21.End for

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

23.While(i≤Ncore)do

//依照核的次序?yàn)楦骱朔峙渚彺?/p>

24.將核Cseq[i]在核集C中對應(yīng)的序號存放在j中，需要的column數(shù)存放在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[][];

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

5 WCET估算

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

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

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

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

6 實(shí)驗(yàn)驗(yàn)證

6.1 實(shí)驗(yàn)環(huán)境和測試程序

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

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

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

6.2 實(shí)驗(yàn)結(jié)果

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

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

Table2 An optimal relation of bank to core mapping表2 一個最優(yōu)bank到核映射關(guān)系

Fig.5 Estimation results without non hard real-time tasks圖5 不存在非硬實(shí)時任務(wù)時的估算結(jié)果

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

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

Fig.6 Estimation results with non hard real-time tasks圖6 存在非硬實(shí)時任務(wù)時的估算結(jié)果

7 結(jié)束語

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

對于帶有IABA總線和bank-column緩存劃分機(jī)制的多核系統(tǒng)，分析了訪存請求的沖突延遲上限；在此基礎(chǔ)上，根據(jù)bank沖突次數(shù)與沖突延遲上限的關(guān)系，利用bank到核映射優(yōu)化沖突延遲上限。

實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有沖突延遲上限界定方法相比，提出的bank到核映射優(yōu)化方法能減小約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.

附中文參考文獻(xiàn)：

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

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

[16]安立奎,古志民,付引霞,等.支持軟件預(yù)取的緩存WCET分析[J].北京理工大學(xué)學(xué)報(bào),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—），男，山東青島人，北京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士研究生，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)，計(jì)算機(jī)網(wǎng)絡(luò)等。

《計(jì)算機(jī)工程與應(yīng)用》投稿須知

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

《計(jì)算機(jī)工程與應(yīng)用》是由中華人民共和國中國電子科技集團(tuán)公司主管，華北計(jì)算技術(shù)研究所主辦的面向計(jì)算機(jī)全行業(yè)的綜合性學(xué)術(shù)刊物。

辦刊方針堅(jiān)持走學(xué)術(shù)與實(shí)踐相結(jié)合的道路，注重理論的先進(jìn)性和實(shí)用技術(shù)的廣泛性，在促進(jìn)學(xué)術(shù)交流的同時，推進(jìn)科技成果的轉(zhuǎn)化。覆蓋面寬、信息量大、報(bào)道及時是本刊的服務(wù)宗旨。

報(bào)導(dǎo)范圍行業(yè)最新研究成果與學(xué)術(shù)領(lǐng)域最新發(fā)展動態(tài)；具有先進(jìn)性和推廣價值的工程方案；有獨(dú)立和創(chuàng)新見解的學(xué)術(shù)報(bào)告；先進(jìn)、廣泛、實(shí)用的開發(fā)成果。

主要欄目理論與研發(fā)，大數(shù)據(jù)與云計(jì)算，網(wǎng)絡(luò)、通信與安全，模式識別與人工智能，圖形圖像處理，工程與應(yīng)用，以及其他熱門專欄。

注意事項(xiàng)為保護(hù)知識產(chǎn)權(quán)和國家機(jī)密，在校學(xué)生投稿必須事先征得導(dǎo)師的同意，所有稿件應(yīng)保證不涉及侵犯他人知識產(chǎn)權(quán)和泄密問題，否則由此引起的一切后果應(yīng)由作者本人負(fù)責(zé)。

論文要求學(xué)術(shù)研究：報(bào)道最新研究成果，以及國家重點(diǎn)攻關(guān)項(xiàng)目和基礎(chǔ)理論研究報(bào)告。要求觀點(diǎn)新穎，創(chuàng)新明確，論據(jù)充實(shí)。技術(shù)報(bào)告：有獨(dú)立和創(chuàng)新學(xué)術(shù)見解的學(xué)術(shù)報(bào)告或先進(jìn)實(shí)用的開發(fā)成果，要求有方法、觀點(diǎn)、比較和實(shí)驗(yàn)分析。工程應(yīng)用：方案采用的技術(shù)應(yīng)具有先進(jìn)性和推廣價值，對科研成果轉(zhuǎn)化為生產(chǎn)力有較大的推動作用。

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

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年于華北電力大學(xué)獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)，計(jì)算機(jī)結(jié)構(gòu)等。

A

：TP302.7

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

CNKI網(wǎng)絡(luò)優(yōu)先出版: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