張吉贊，苑雅娟

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1UBD分析

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

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

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

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

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

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

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

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

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

從式（2）和式（4）可知，減少請(qǐng)求發(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)系使請(qǐng)求的沖突延遲上界最小的形式化描述如下。

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

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

（2）約束條件

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

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

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

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

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

4.3 求解算法

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

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

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

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

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

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

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

輸出：最小的Z(Nhrt)及對(duì)應(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個(gè)核的某個(gè)次序作bank到核映射，根據(jù)核需要的L2緩存容量，分如下3種情形作bank到核的映射。

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

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

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

輸出：一個(gè)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)整每個(gè)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中對(duì)應(yīng)的序號(hào)存放在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ì)算在每個(gè)bank到核映射中bank沖突可能發(fā)生的最大次數(shù)，復(fù)雜性為O(Ncore!)。

5 WCET估算

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

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

Fig.4 Example of maximum waiting time in ICBA圖4 請(qǐng)求在ICBA中的最大等待時(shí)間舉例

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

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

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

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

使用的所有測(cè)試程序是M?lardalen WCET benchmark測(cè)試程序集[20]的一部分，使用Chronos測(cè)量了這些測(cè)試程序在單核系統(tǒng)中分配給不同L2緩存大小時(shí)的WCET，根據(jù)測(cè)量結(jié)果給測(cè)試程序分配合適的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í)時(shí)任務(wù)或存在非硬實(shí)時(shí)任務(wù)（matmult為非硬實(shí)時(shí)任務(wù)）時(shí)，使用算法1得到的一個(gè)最優(yōu)bank到核映射如表2所示，在該映射關(guān)系中，Zi=0(1≤i≤7)。

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

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

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

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

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

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

7 結(jié)束語(yǔ)

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

對(duì)于帶有IABA總線和bank-column緩存劃分機(jī)制的多核系統(tǒng)，分析了訪存請(qǐ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]康少華,古志民,付引霞,等.空間碎片探測(cè)軟件的并行化及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)用》投稿須知

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

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

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

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

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

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

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

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

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(國(guó)家自然科學(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