安立奎，韓麗艷

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

?

支持指令預(yù)取和緩存劃分的多核實(shí)時(shí)系統(tǒng)緩存WCRT最小化

安立奎*，1，韓麗艷2

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

對(duì)嵌入式多核實(shí)時(shí)系統(tǒng)，為了保證任務(wù)的可調(diào)度性和可靠性，最壞情況下的性能是一個(gè)優(yōu)先考慮的問(wèn)題．順序指令預(yù)取可以提高實(shí)時(shí)任務(wù)的最壞情況下的性能，但對(duì)于實(shí)時(shí)系統(tǒng)中不同的子任務(wù)，在不同預(yù)取度下，指令預(yù)取獲得的最壞情況下性能效率也不同，因此會(huì)影響整個(gè)實(shí)時(shí)系統(tǒng)的最壞情況下響應(yīng)時(shí)間WCRT (Worst-Case Response Time)．本文利用緩存劃分技術(shù)消除多核實(shí)時(shí)系統(tǒng)中多個(gè)子任務(wù)在共享緩存上的干擾，然后提出了多核實(shí)時(shí)系統(tǒng)的WCRT優(yōu)化方法．該方法建立ILP(Integer-Linear Programming)方程，通過(guò)調(diào)整共享緩存劃分因子和系統(tǒng)中子任務(wù)的指令預(yù)取度來(lái)最小化系統(tǒng)的WCRT．實(shí)驗(yàn)對(duì)多核上的DEBIE系統(tǒng)進(jìn)行實(shí)例分析，結(jié)果表明優(yōu)化算法在保證DEBIE系統(tǒng)滿足時(shí)間截止期的情況下，使得優(yōu)化后的WCRT比不同預(yù)取度下的WCRT平均減少12.2 %．

最壞情況下響應(yīng)時(shí)間；指令預(yù)取度；緩存劃分

0 引言

在多核實(shí)時(shí)系統(tǒng)中，任務(wù)執(zhí)行時(shí)間必須滿足時(shí)間截止期(Deadline)，否則將會(huì)引起災(zāi)難性后果．最壞情況執(zhí)行時(shí)間WCET(Worst-Case Execution Time)分析能夠獲得實(shí)時(shí)任務(wù)最壞情況下的執(zhí)行時(shí)間，多核實(shí)時(shí)系統(tǒng)的WCRT(Worst-Case Response Time)是運(yùn)行在所有核上任務(wù)的結(jié)束時(shí)間的最大值，它與實(shí)時(shí)系統(tǒng)中每個(gè)子任務(wù)的WCET有密切關(guān)系．減少WCRT對(duì)于實(shí)時(shí)系統(tǒng)中任務(wù)的可靠性和可調(diào)度性來(lái)說(shuō)非常重要．

許多嵌入式多核系統(tǒng)支持順序指令預(yù)取技術(shù)，由于Next-N-Line指令預(yù)取代價(jià)小且容易實(shí)現(xiàn)，它已被許多商業(yè)處理器所采用．當(dāng)訪問(wèn)L1指令緩存行pi時(shí)，指令預(yù)取器會(huì)預(yù)取緩存行pi+1,pi+2，…，pi+N這里N是指令預(yù)取度．順序指令預(yù)取可以覆蓋取指令過(guò)程中短的非連續(xù)流，但是它并不能消除由于長(zhǎng)距離的轉(zhuǎn)移而引起的指令缺失，因此順序指令預(yù)取的性能獲益和缺失時(shí)預(yù)取的緩存塊N有很大關(guān)系．因此對(duì)具有并發(fā)多任務(wù)的實(shí)時(shí)系統(tǒng)，所有子任務(wù)采用相同預(yù)取度，不益于提高整個(gè)系統(tǒng)的WCRT．

在多核下實(shí)時(shí)系統(tǒng)緩存WCRT分析方面：文獻(xiàn)〔1〕對(duì)并發(fā)程序建立MSC(Message Sequence Chart)圖，通過(guò)分析并發(fā)多個(gè)任務(wù)在共享緩存上的干擾，提出了WCRT分析方法．文獻(xiàn)〔2〕優(yōu)化任務(wù)到核的映射，減少任務(wù)在共享緩存上的干擾和實(shí)時(shí)應(yīng)用系統(tǒng)的WCRT．在文獻(xiàn)〔1〕和〔2〕中考慮的僅是共享指令緩存，并沒(méi)有分析數(shù)據(jù)在共享緩存上的干擾，也沒(méi)有關(guān)注指令預(yù)取對(duì)實(shí)時(shí)系統(tǒng)的WCET的影響．單核下最壞情況下指令預(yù)取效率方面：文獻(xiàn)〔3〕研究了基于Next-N-Line 的指令硬件預(yù)取技術(shù)對(duì)WCET的影響；為改進(jìn)文獻(xiàn)〔3〕中Next-N-Nine指令預(yù)取器的有效性，文獻(xiàn)〔4〕提出一種基于循環(huán)的預(yù)取優(yōu)化機(jī)制和一種針對(duì)WCET的指令預(yù)取方法．文獻(xiàn)〔5〕提出支持指令預(yù)取和鎖緩存的模型來(lái)優(yōu)化實(shí)時(shí)單任務(wù)的WCET 和WCEC(Worst-Case Energy Consumption)．在文獻(xiàn)〔3〕、〔4〕和〔5〕中，它們也僅考慮的是單核下的單層指令緩存的指令預(yù)取效率，并沒(méi)有考慮多核下實(shí)時(shí)系統(tǒng)的指令預(yù)取效率．通過(guò)查閱文獻(xiàn)后得知，目前沒(méi)有研究人員針對(duì)嵌入式多核下結(jié)合指令預(yù)取和緩存劃分的最壞情況下性能優(yōu)化工作展開(kāi)深入研究．

本文的研究目的是利用順序指令預(yù)取提高多核實(shí)時(shí)系統(tǒng)的WCRT ，為此采用基于組(Set)緩存劃分技術(shù)〔6〕，消除實(shí)時(shí)系統(tǒng)中并發(fā)多任務(wù)在共享緩存上干擾，保證系統(tǒng)WCRT可分析性，提出了多核實(shí)時(shí)系統(tǒng)的支持指令預(yù)取和緩存劃分的WCRT優(yōu)化算法．所做的貢獻(xiàn)主要有：

1)實(shí)驗(yàn)驗(yàn)證了指令預(yù)取度對(duì)于實(shí)時(shí)任務(wù)的WCRT的重要影響．

2)設(shè)計(jì)了結(jié)合指令預(yù)取和緩存劃分的ILP(Integer-Linear Programming)方程，在保證多核實(shí)時(shí)系統(tǒng)滿足時(shí)間截止期的情況下，最小化其WCRT．

3)對(duì)實(shí)時(shí)系統(tǒng)DEBIE進(jìn)行實(shí)例分析，驗(yàn)證了優(yōu)化算法的有效性．

1 嵌入式多核模型和研究動(dòng)機(jī)

1.1 嵌入式多核結(jié)構(gòu)和任務(wù)模型

圖1是一種支持指令預(yù)取的嵌入式多核模型．有NC個(gè)同構(gòu)的處理器核．每個(gè)核有私有的L1指令/數(shù)據(jù)緩存，所有的核共享L2聯(lián)合緩存．緩存的替換策略是LRU (Least Recently Used)．L1和L2緩存通過(guò)實(shí)時(shí)總線連接．順序指令預(yù)取器采用支持Prefetch-on-miss預(yù)取策略的Next-N-Line指令預(yù)?。?/p>

執(zhí)行環(huán)境是一個(gè)基于靜態(tài)優(yōu)先級(jí)的非搶占系統(tǒng)，每一個(gè)任務(wù)被分配給唯一的一個(gè)靜態(tài)優(yōu)先級(jí)，如果多個(gè)任務(wù)被映射到同一核上執(zhí)行，優(yōu)先級(jí)高的任務(wù)先執(zhí)行．如果任務(wù)開(kāi)始執(zhí)行，在它完成前，不允許被別的任務(wù)搶占．任務(wù)之間的通信和同步是通過(guò)郵箱(Mailbox)，并且郵箱足夠大，消息不會(huì)溢出．消息在系統(tǒng)內(nèi)部的通信狀況通過(guò)MSC描述．

1.2 支持指令預(yù)取的WCET分析

如果L2緩存劃分因子已經(jīng)分配給L2緩存，對(duì)于一個(gè)實(shí)時(shí)任務(wù)Ti，Tpipeline是流水線執(zhí)行時(shí)間，TM是總的訪存時(shí)間，支持指令預(yù)取的緩存WCETi可以通過(guò)公式(1)計(jì)算：

WCETi=Tpipeline+TM=LhitL1*nhitL1+LmissL1*nmissL1+LmissL2*nmissL2

(1)

這里L(fēng)hitL1是在L1緩存命中一次延遲，nhitL1是在L1緩存命中次數(shù)，LmissL1是在L1緩存缺失一次延遲，nmissL1是在L1緩存缺失次數(shù)，LmissL2是在L2緩存缺失一次延遲，nmissL2是在L2緩存缺失次數(shù).nhitL1,nmissL1,nmissL2通過(guò)指令預(yù)取擴(kuò)展的緩存WCET分析工具——chronos〔7〕測(cè)得．

1.3 研究動(dòng)機(jī)

對(duì)文獻(xiàn)〔8〕中的實(shí)時(shí)M?lardalen wcet benchmarks，圖3是不同預(yù)取度下正規(guī)化的支持指令預(yù)取的緩存WCET，當(dāng)預(yù)取度N是0表示沒(méi)有指令預(yù)取，關(guān)閉預(yù)取器．這里L(fēng)1 指令/數(shù)據(jù)緩存是256B，直接映射，分配給每個(gè)任務(wù)的L2緩存是512B，2路組關(guān)聯(lián)．支持指令預(yù)取的緩存WCET通過(guò)擴(kuò)展緩存分析工具〔7〕的支持指令預(yù)取語(yǔ)義獲得，L1緩存命中是1 circle，L1緩存缺失是6 circles，L2緩存缺失是30 circles．

通過(guò)上面的分析可以看出指令的預(yù)取度與它在最壞情況下性能獲益沒(méi)有線性關(guān)系，這是由于程序跳轉(zhuǎn)目標(biāo)的不確定性，大的預(yù)取度一方面會(huì)減少緩存的缺失，降低WCET，另一方面也可能會(huì)增加緩存的干擾，增加任務(wù)執(zhí)行時(shí)候的緩存缺失和降低性能，所以較大預(yù)取度并不一定會(huì)提高任務(wù)的最壞情況下的性能，還會(huì)增加更多的系統(tǒng)負(fù)載和能量消耗．運(yùn)行在多核系統(tǒng)上的實(shí)時(shí)系統(tǒng)具有多個(gè)相互依賴的實(shí)時(shí)任務(wù)，這樣對(duì)于所有任務(wù)采用相同的預(yù)取度，不利于減少WCRT，提高實(shí)時(shí)系統(tǒng)的最壞情況下性能效率，因此就非常有必要對(duì)實(shí)時(shí)系統(tǒng)中不同的任務(wù)的指令預(yù)取度進(jìn)行調(diào)整，優(yōu)化系統(tǒng)的WCRT．

2 WCRT優(yōu)化框架

如果實(shí)時(shí)系統(tǒng)中的所有子任務(wù)被映射到相應(yīng)的處理器核，我們優(yōu)化實(shí)時(shí)系統(tǒng)的WCRT．由于太大的預(yù)取度會(huì)給多核系統(tǒng)的負(fù)載帶來(lái)沉重負(fù)擔(dān)，影響系統(tǒng)性能，這里我們?cè)O(shè)定預(yù)取度的取值范圍是從0到4，0表示關(guān)閉指令預(yù)取器，最大預(yù)取度閾值為4．

2.1 優(yōu)化目標(biāo)

實(shí)時(shí)系統(tǒng)RS={T,D,M,L,P,WCRTs}組成，T是其所有子任務(wù)的集合T={T1,T2,…,TNT}，D是順序指令預(yù)取度集合D={d1,d2,…,dND}，M是任務(wù)T到預(yù)取度D的映射：M:T→D．L2緩存劃分因子集合P={p1,…,pNP}，pi=i,(i=1,2,…,NP)．L是任務(wù)T到L2緩存劃分因子集合P的映射：L:T→P．WCRTs是實(shí)時(shí)系統(tǒng)的最壞情況又響應(yīng)時(shí)間.

用Pred(Ti)來(lái)表示任務(wù)Ti的前驅(qū)的集合，只有Pred(Ti)中的任務(wù)都執(zhí)行結(jié)束，任務(wù)Ti才可以執(zhí)行．用Starti(L,M)表示任務(wù)Ti在映射L和M下的開(kāi)始時(shí)間，用Finishi(L,M)表示任務(wù)Ti在映射L和M下的結(jié)束時(shí)間．那么任務(wù)Ti的開(kāi)始時(shí)間是Ti所有前驅(qū)任務(wù)完成時(shí)間的最大值，如公式(2).任務(wù)Ti的結(jié)束時(shí)間是Ti開(kāi)始時(shí)間與任務(wù)Ti本身在映射L和M下最壞執(zhí)行時(shí)間WCETi(L,M)的和，如公式(3)．

Starti(L,M)=Max(Finishj(L,M)),Tj∈Pred(Ti)

(2)

Finishi(L,M)=Starti(L,M)+WCETi(L,M)

(3)

實(shí)時(shí)系統(tǒng)在映射L和M下的支持指令預(yù)取的WCRT是運(yùn)行在所有核上任務(wù)的結(jié)束時(shí)間的最大值，如公式(4)所示：

WCRT(L,M)=Max(Finishi(L,M)),1≤i≤NT

(4)

我們的優(yōu)化目標(biāo)是尋找映射L和M，使得多核實(shí)時(shí)系統(tǒng)的WCRT最小，即：

Min(Max(Finishi(L,M))),1≤i≤NT

(5)

2.2 優(yōu)化方程

C1. 任務(wù)到核的映射約束

首先定義0-1變量Cij，表示任務(wù)Ti是否被映射到核Cj上，

0≤Cij≤1,where 1≤i≤NTand 1≤j≤NC

每一個(gè)任務(wù)只允許被映射到一個(gè)處理器核上，因此對(duì)于?i

C2.核到L2緩存劃分的約束

如果L2緩存共有W個(gè)組，可以被劃分的組的集合P={p1,…,pNP}，定義0-1變量Lij，表示核Ci是否被分配了pj組，

0≤Lij≤1,where 1≤i≤NCand 1≤j≤NP

每一個(gè)核只允許分配一個(gè)組，因此對(duì)于?i

同時(shí)所有核分配的總組數(shù)不能大于W，因此有

C3.任務(wù)選擇WCET的約束

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

用數(shù)組W[i][j][k]存儲(chǔ)任務(wù)Ti采用預(yù)取度dj， L2緩存劃分因子是pk下的WCET，用整型變量Wi表示任務(wù)Ti應(yīng)該選擇的WCET，因此有

定義0-1變量Aijkm，表示每一任務(wù)Ti被分配了唯一的處理器核Cj，預(yù)取度dk, L2緩存劃分是pm,對(duì)1≤i≤NT,1≤j≤NC,1≤k≤ND,1≤m≤NP有

Aijkm-Cij<=0

Aijkm-Ljm<=0

Aijkm-Tikm<=0

Aijkm-Cij-Ljm-Tikm≥-2

C4. WCRT計(jì)算約束

為了計(jì)算所有任務(wù)的WCRT，我們需要計(jì)算所有核上任務(wù)的最晚結(jié)束時(shí)間．定義0-1變量Mijk表示任務(wù)Ti與任務(wù)Tj是否映射到核Ck上，有

把上面的方程線性化，有

Cik+Cjk-Mijk≤1

Cik+Cjk-2Mijk≥0

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

把上面的方程線性化

Mij≥Mijk,?k,1≤k≤NC

如果兩個(gè)任務(wù)Ti與Tj映射到同一個(gè)處理器核上，定義0-1變量Bij，表示任務(wù)Ti在任務(wù)Tj之前執(zhí)行，定義0-1變量Bji表示任務(wù)Tj在任務(wù)Ti之前執(zhí)行，對(duì)于1≤i≤NT-1,i≤j≤NT有

Bij≤1

Bji≤1

Bij+Bji+Mij=2

對(duì)于任務(wù)Ti，用整型變量Si表示任務(wù)Ti的開(kāi)始時(shí)間，用整型變量Fi表示任務(wù)Ti的結(jié)束時(shí)間，那么被映射到同一核上的任務(wù)，先執(zhí)行的任務(wù)的結(jié)束時(shí)間要小于后執(zhí)行任務(wù)的開(kāi)始時(shí)間，如果沒(méi)有映射到同一核上，則沒(méi)有此限制，則對(duì)于1≤i≤NT-1,i≤j≤NT,有

Si-Fj+MW*Bij≥0

Sj-Fi+MW*Bji≥0

這里MW是比所有任務(wù)的WCET的和都大的一個(gè)常量．

對(duì)于所有的任務(wù)根據(jù)公式(3)，

Fi-Si-Wi=0,1≤i≤NT

對(duì)所有任務(wù)的WCRTs，有

WCRTs-Fi≥0,1≤i≤NT

C5.優(yōu)化目標(biāo)

我們優(yōu)化的目標(biāo)是滿足時(shí)間截止期(Deadline)的情況下最小化WCRTs，即

WCRTs≤DEADLINE

Min WCRTs

3 實(shí)驗(yàn)評(píng)估

這部分我們?cè)u(píng)估實(shí)時(shí)系統(tǒng)的基于指令預(yù)取的WCRT優(yōu)化算法．N是指令預(yù)取的預(yù)取度，當(dāng)N為0時(shí)，表示沒(méi)有指令預(yù)取，關(guān)閉預(yù)取器．

3.1 評(píng)估環(huán)境

我們嵌入式多核假設(shè)有4個(gè)同構(gòu)的處理器核，對(duì)于每一個(gè)核，有5階段流水，順序執(zhí)行，分支預(yù)測(cè)是完美的(Perfect)．L1指令/數(shù)據(jù)緩存是512B，直接映射，緩存行大小是16B．L2緩存的總大小是8KB，被4個(gè)處理器核共享，4路組關(guān)聯(lián)，緩存行是32B，有64組．L1緩存的命中延遲是1 circle，缺失延遲是6 circles．L2緩存的缺失延遲是30 circles．利用IBM CPLEX12.2 ILP solver〔9〕來(lái)求解 WCRT優(yōu)化方程.

實(shí)驗(yàn)使用的benchmark是DEBIE是由Patria Finavitec 和UniSpace Kent聯(lián)合開(kāi)發(fā)的空間碎片探測(cè)器系統(tǒng)〔10〕，所有的實(shí)驗(yàn)運(yùn)行在Intel(R) Core(TM) i5-3230 機(jī)器上，有4GB內(nèi)存，運(yùn)行Ubuntu Linux 8.04操作系統(tǒng)．

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

3.2.1 指令預(yù)取對(duì)實(shí)時(shí)任務(wù)最壞情況性能的影響

圖4比較了DEBIE系統(tǒng)不支持指令預(yù)取和支持指令預(yù)取在不同預(yù)取距度下的最壞情況的WCRT．預(yù)取度N從1，2，3到4．實(shí)驗(yàn)結(jié)果被沒(méi)有預(yù)取的WCRT(N是 0)結(jié)果歸一化了．

從圖4中可以看出，在不同的預(yù)取度下，系統(tǒng)的最壞情況下的性能得到了提升．DEBIE系統(tǒng)的WCRT平均被提高了53.9%．當(dāng)預(yù)取度是4時(shí)候，最壞情況下的性能提高的最明顯，達(dá)到了56.5%．指令預(yù)取效率比較高主要有兩個(gè)方面的原因：一方面是緩存WCET分析工具〔7〕本身分析的保守性，擴(kuò)大了指令預(yù)取在最壞情況下的效率；另外一方面這是由于DEBIE系統(tǒng)中一些WCET較大的任務(wù)都是事務(wù)密集型的，數(shù)據(jù)計(jì)算量非常小，指令預(yù)取大大減少了這些任務(wù)指令訪存次數(shù)，從而節(jié)省了訪存延遲，提高了實(shí)習(xí)系統(tǒng)在最壞情況下的性能．同時(shí)指令預(yù)取度是2的情況下的最壞情況下的性能比指令預(yù)取度是3的最壞情況下的性能要好．這也表明并不是指令預(yù)取度越大，預(yù)取的效率就越高．

3.2.2 優(yōu)化算法對(duì)最壞情況性能的影響

圖5是DEBIE系統(tǒng)優(yōu)化后的WCRT和不同預(yù)取度下的WCRT比值．預(yù)取度從0，1，2，3到4，這里當(dāng)N是0表示沒(méi)有預(yù)取，關(guān)閉預(yù)取器．

從圖5可以看出優(yōu)化后的支持指令預(yù)取的最壞情況下的性能比沒(méi)有預(yù)取的最壞情況下的性能提高了59.7%，這是由于整個(gè)系統(tǒng)的指令較多，需要進(jìn)行的數(shù)據(jù)計(jì)算很少，指令預(yù)取提高最壞情況下的性能明顯．同時(shí)經(jīng)過(guò)優(yōu)化后的WCRT比不同預(yù)取度下的WCRT平均減少了12.2%，這說(shuō)明本文的實(shí)時(shí)系統(tǒng)緩存WCRT優(yōu)化方法是有效的．

4 結(jié)論

對(duì)于性能有很高要求的并發(fā)多任務(wù)多核實(shí)時(shí)系統(tǒng)，我們利用緩存劃分技術(shù)消除多個(gè)任務(wù)在共享緩存上的干擾，提出支持指令預(yù)取的WCRT優(yōu)化方法．該方法建立ILP方程，在保證實(shí)時(shí)系統(tǒng)滿足時(shí)間截止期的情況下，通過(guò)調(diào)整子任務(wù)的預(yù)取度和L2緩存劃分因子來(lái)最小化多核實(shí)時(shí)系統(tǒng)的WCRT．通過(guò)對(duì)粒子探測(cè)系統(tǒng)DEBIE的分析，實(shí)驗(yàn)表明本文優(yōu)化的算法是有效的，在一定范圍內(nèi)指令預(yù)取能夠提高DEBIE的最壞情況下的性能．如果任務(wù)的并行度越高，優(yōu)化的效果就會(huì)更明顯．

今后我們希望能夠把指令預(yù)取和緩存劃分結(jié)合起來(lái)對(duì)實(shí)時(shí)系統(tǒng)的最壞情況下的能耗進(jìn)行優(yōu)化．

〔1〕LIANGY,DINGH,MITRAT,etal.Timinganalysisofconcurrentprogramsrunningonsharedcachemulti-cores.Real-TimeSystem〔J〕. 2012, 48(6): 638-680.

〔2〕DIHG H， LINGY Y, MITRA T.Shared Cache Aware Task Mapping for WCRT Minimization 〔C〕. Design Automation Conference, 2013.

〔3〕YAN J, ZHANG W. WCET analysis of instruction caches with prefetching〔J〕. ACM SIGPLAN Notices, 2007, 42(7): 175-184.

〔4〕DING Y, YAN J, ZHANG W. Optimizing Instruction Prefetching to Improve Worst-Case Performance for Real-Time Applications〔J〕. JCSE, 2009, 3(1): 59-71.

〔5〕GRAN R, SEGARRA J, RODRIGUEZ C, et al. Optimizing a combined WCET-WCEC problem in instruction fetching for real-time systems〔J〕. Journal of Systems Architecture, 2013, 59(9): 667-678.

〔6〕YU C, PETROV P.Off-chip memory bandwidth minimization through cache partitioning for multi-core platforms〔C〕.47th ACM/EDAC/IEEE Design Automation Conference, 2000.

〔7〕CHATTOPADHYAY S, ROYCHOUDHURY A. Unified cache modeling for WCET analysis and layout optimizations〔C〕.Proc of 2009 30th IEEE Real-Time Systems Symposium, 2009.

〔8〕M?lardalen Real-Time Research Center. WCET Benchmarks [EB/OL]. [2013-10]. http://www.mrtc.mdh.se/projects/wcet/benchmarks.html.

〔9〕IBM. ILOG CPLEX[EB/OL]. [2013-05]. http://www.ibm.com/software/.

〔10〕KUITUNEN J, DROLSHAGEN G, MCDONNELL J A M, et al. DEBIE - first standard in-situ debris monitoring instrument〔C〕.Proc of the Third European Conference on Space Debris, 2001.

Cache WCRT minimization for multi-cores real-time system with instruction prefetching and cache partitioning

AN Li-kui1, HAN Li-yan2

(1. School of Mathematics and Physics, Bohai University,Jinzhou 121013, China; 2. School of Information Science and Technology, Bohai University,Jinzhou 121013, China)

For the real-time system on the embedded multi-cores, the worst-case performance is a prior to be considered to guarantee the schedulability and the reliability of the tasks. Sequent instruction prefetching can improve the worst-case performance of real-time tasks. But for different subtasks in real-time system, under the different prefetching degrees, the worst-case performance efficiency gained by instruction prefetching are different, which will influence the WCRT (Worst-Case Response Time) of the whole real-time system. This paper first uses cache partitioning technology to eliminate interferences of multiple real-time subtasks on the shared cache, and then puts forward the WCRT optimization method for the multi-cores real-time system. This method establishes IIP(Integer-linear programming) to minimize the WCRT of real-time system through adjusting instruction prefetching degrees and cache partitioning factors. DEBIE system on the multi-cores is analyzed in experiment, the experiment results show that the optimization method can reduce the WCRT of the DEBIE system 12.2% on an average than those under the different instruction prefetching degrees when guarantees the DEBIE system meet the time deadline.

worst-case response time; instruction prefetching degree; cache partitioning

2016-08-08.

遼寧省自然科學(xué)基金項(xiàng)目(No：LN2014160)；遼寧省教育廳項(xiàng)目(No： L2013424).

安立奎(1978-)，男，講師，主要從事計(jì)算機(jī)體系結(jié)構(gòu)、實(shí)時(shí)計(jì)算方面的研究.

anlikui2012@126.com．

TP314

A

1673-0569(2016)04-0365-08