基于多級(jí)一致性協(xié)議的多核處理器WCET分析方法

朱怡安 史先琛 姚 燁 李 聯(lián) 任鵬遠(yuǎn) 董威振 李佳鈺

1 （西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 西安 710072）

2 （西北工業(yè)大學(xué)軟件學(xué)院 西安 710072）

3 （西北工業(yè)大學(xué)倫敦瑪麗女王大學(xué)工程學(xué)院 西安 710072） （zhuya@nwpu.edu.cn）

嵌入式實(shí)時(shí)系統(tǒng)廣泛存在于生產(chǎn)和生活當(dāng)中，例如航空航天、軌道交通、無(wú)人駕駛、互聯(lián)通信等.在實(shí)時(shí)系統(tǒng)中，其正確性不僅僅依賴(lài)于邏輯結(jié)果的正確性，同時(shí)還依賴(lài)于結(jié)果產(chǎn)生的時(shí)間[1].實(shí)時(shí)系統(tǒng)中的任務(wù)執(zhí)行時(shí)間具有嚴(yán)格的約束，如果錯(cuò)過(guò)任務(wù)截止時(shí)間將會(huì)導(dǎo)致災(zāi)難性后果.因此，實(shí)時(shí)系統(tǒng)在任務(wù)調(diào)度設(shè)計(jì)和可調(diào)度性分析時(shí)都必須保證任務(wù)的執(zhí)行在一個(gè)安全的時(shí)間上界之內(nèi)，此上界的計(jì)算方法即任務(wù)的最壞情況執(zhí)行時(shí)間（worst-case execution time，WCET）分析.當(dāng)前主流的WCET分析方法分為靜態(tài)分析和動(dòng)態(tài)分析，動(dòng)態(tài)分析也稱(chēng)為基于測(cè)試的分析方法，通過(guò)大量的測(cè)試用例來(lái)獲取精確的WCET分析結(jié)果，由于無(wú)法窮盡所有的測(cè)試用例，動(dòng)態(tài)分析無(wú)法保證分析結(jié)果的安全性，工業(yè)界通常會(huì)在分析結(jié)果的基礎(chǔ)上增加一定的裕量（例如20%）[2]作為最終的WCET分析結(jié)果.靜態(tài)分析方法則是通過(guò)對(duì)處理器硬件結(jié)構(gòu)和程序流信息進(jìn)行分析估算程序的WCET值，靜態(tài)分析方法能夠保證分析結(jié)果的安全性，并且不需要運(yùn)行程序便可獲得WCET結(jié)果，所以大多數(shù)WCET分析工具都采用靜態(tài)分析方法.單核處理器WCET分析方法經(jīng)過(guò)多年的研究已經(jīng)取得較高的分析精度，然而多核處理器中加速部件的使用和共享資源干擾的存在，導(dǎo)致原有的單核處理器WCET分析方法無(wú)法直接適用于多核處理器，這對(duì)于多核處理器的WCET分析提出了新的挑戰(zhàn).

在硬件結(jié)構(gòu)方面，多核處理器的WCET分析主要考慮Cache、內(nèi)存、核間互聯(lián)和流水線(xiàn)等部件的影響[3]，Rapita Systems公司的實(shí)驗(yàn)表明，由于 L3 Cache的爭(zhēng)用導(dǎo)致YOLO算法的幀率降低90%左右.當(dāng)前對(duì)于Cache的研究主要集中在指令Cache帶來(lái)的干擾分析[4-7]，并已經(jīng)獲得了較高的分析精度，而對(duì)于數(shù)據(jù)Cache的關(guān)注則不足，其原因有2方面：1）處理器尋址方式的不同導(dǎo)致數(shù)據(jù)Cache的訪(fǎng)問(wèn)地址分析更加困難；2）數(shù)據(jù)Cache在循環(huán)的不同輪次中訪(fǎng)問(wèn)的數(shù)據(jù)不同，正是由于數(shù)據(jù)Cache和指令Cache在時(shí)空特性上的差異，造成數(shù)據(jù)Cache的分析更加復(fù)雜.如果簡(jiǎn)單將指令Cache的分析技術(shù)套用到數(shù)據(jù)Cache上，會(huì)導(dǎo)致分析結(jié)果過(guò)于悲觀(guān)[8].對(duì)于數(shù)據(jù)Cache的分析除了以上問(wèn)題之外，另一個(gè)需要特別關(guān)注的影響因素就是數(shù)據(jù)一致性協(xié)議.有研究表明，由于Cache一致性協(xié)議的影響，并行程序執(zhí)行比串行程序慢74%[9].但是相關(guān)的調(diào)研表明[10]，極少數(shù)研究人員關(guān)注Cache一致性造成的干擾.

針對(duì)現(xiàn)有多核處理器WCET分析方法對(duì)數(shù)據(jù)Cache一致性協(xié)議考慮不足的問(wèn)題，本文主要研究一種基于多級(jí)一致性協(xié)議的多核處理器WCET分析方法.該方法通過(guò)建立多級(jí)一致性域，抽象出一致性協(xié)議嵌套的共享數(shù)據(jù)管理機(jī)制，分別從一致性域內(nèi)部、跨一致性域2個(gè)層面來(lái)分析內(nèi)存訪(fǎng)問(wèn)延遲，從而實(shí)現(xiàn)對(duì)多核處理器中數(shù)據(jù)Cache的精確分析.

1 相關(guān)工作

Ferdinand等人[11]提出基于抽象解釋理論[12]的Cache行為分析方法，由于其具有較高的精確度和效率，在基于Cache的WCET分析中占據(jù)了統(tǒng)治地位[8].如圖1所示，基于抽象解釋的Cache分析方法對(duì)Cache的物理狀態(tài)和替換策略進(jìn)行抽象，得到抽象緩存狀態(tài)（abstract cache state）和函數(shù)Join、函數(shù)Update，通過(guò)May分析、Must分析和Persistence分析3種方法得出 Cache的“Cache命中/失效分類(lèi)”（cache hit miss classification, CHMC），從而確定 Cache 的訪(fǎng)問(wèn)延遲.Huynh等人[13]經(jīng)過(guò)分析證明了原有的Persistence分析方法存在不安全性，其原因在于更新函數(shù)未將可能被替換出去的內(nèi)存塊的年齡進(jìn)行增加，導(dǎo)致分析結(jié)果不正確.為解決此問(wèn)題，該小組提出Younger Set的概念，并將Younger Set引入到函數(shù)Join和函數(shù)Update中，保證了Persistence分析的安全性.在過(guò)去的20多年，研究人員對(duì)Persistence分析進(jìn)行了廣泛的研究，仍然不能保證其發(fā)現(xiàn)所有的 Persistent Cache塊，直到 Stock[14]給出Exact Persistence分析方法，才使得Persistence分析趨于完善.

Fig.1 Cache analysis based on abstract interpretation圖1 基于抽象解釋的Cache分析方法

模型檢測(cè)[15]方法是另一個(gè)廣泛研究的Cache行為分析方法，模型檢測(cè)作為實(shí)時(shí)系統(tǒng)中常用的時(shí)序驗(yàn)證手段，將各類(lèi)時(shí)序分析問(wèn)題轉(zhuǎn)化為時(shí)間自動(dòng)機(jī)的可達(dá)性問(wèn)題，從而實(shí)現(xiàn)對(duì)問(wèn)題的求解.Wilhelm[16]討論了模型檢測(cè)技術(shù)在WCET分析中的優(yōu)缺點(diǎn)，Metzner[17]認(rèn)為模型檢測(cè)方法能夠提高分析結(jié)果的精度.Dalsgaard等人[18]基于模型檢測(cè)方法實(shí)現(xiàn)了模塊化任務(wù)執(zhí)行時(shí)間分析框架；Gustavsson等人[19]的研究表明，UPPAAL可以用于多核處理器中并行任務(wù)的WCET分析，Cassez等人[20]將WCET分析問(wèn)題轉(zhuǎn)換為尋找最長(zhǎng)路徑的問(wèn)題，并通過(guò)擴(kuò)展模型檢測(cè)工具UPPAAL實(shí)現(xiàn)了一個(gè)任務(wù)WCET分析工具WUPPAAL；Lü等人[21]在開(kāi)源工具Chronos的基礎(chǔ)上，將模型檢測(cè)的方法用于Cache的行為分析，實(shí)現(xiàn)了一個(gè)多核處理器WCET分析工具M(jìn)cAiT；陳芳園等人[22]改進(jìn)多核處理器中Cache沖突分析方法，在取指階段考慮取指操作之間的時(shí)序關(guān)系，該方法能夠排除部分非干擾狀態(tài)，使得WCET計(jì)算精度最高提高12%.上述對(duì)于Cache行為分析多是針對(duì)指令Cache展開(kāi)的，而對(duì)于數(shù)據(jù)Cache的分析研究較少，尤其是對(duì)于多核處理器中Cache一致性協(xié)議的討論更為少見(jiàn).直到2015年，Uhrig等人[23]研究數(shù)據(jù)Cache對(duì)多核處理器WCET分析的影響，并研究了基于監(jiān)聽(tīng)的一致性協(xié)議和TDMA總線(xiàn)對(duì)多核處理器中延遲時(shí)間的影響，最終得出結(jié)論：采用寫(xiě)失效的基于總線(xiàn)監(jiān)聽(tīng)的一致性協(xié)議不具備可預(yù)測(cè)性，而采用寫(xiě)更新雙通道直接映射的bus-snarfing一致性協(xié)議配合TDMA總線(xiàn)能夠?qū)崿F(xiàn)時(shí)間可預(yù)測(cè).但文獻(xiàn)[23]未對(duì)Cache一致性協(xié)議帶來(lái)的內(nèi)存訪(fǎng)問(wèn)延遲進(jìn)行更為細(xì)致的分析.而Hassan等人[24]的分析也得出了基于總線(xiàn)監(jiān)聽(tīng)MSI一致性協(xié)議配合TDMA總線(xiàn)的多核處理器的WCET值不具有可預(yù)測(cè)性，重點(diǎn)分析了TDMA總線(xiàn)導(dǎo)致的不可預(yù)測(cè)性，而對(duì)于多核處理器中基于MESI一致性協(xié)議的WCET估計(jì)，同樣未給出詳細(xì)的分析方法.Tsoupidi[25]針對(duì)對(duì)稱(chēng)多處理器，提出一種考慮Cache一致性協(xié)議的WCET分析方法，該方法在計(jì)算共享Cache讀訪(fǎng)問(wèn)延遲時(shí)認(rèn)為上述情況僅發(fā)生在Cache使用寫(xiě)回（write-back）策略時(shí)，對(duì)于寫(xiě)直達(dá)（writethrough）策略，數(shù)據(jù)同時(shí)存在于私有Cache和共享Cache中，該計(jì)算方式存在較大的悲觀(guān)性，且該文僅僅討論了單級(jí)一致性協(xié)議下的WCET分析方法，而對(duì)于多核處理器中存在多級(jí)Cache一致性協(xié)議的情況，尚未見(jiàn)到相關(guān)的研究.

為此，本文針對(duì)數(shù)據(jù)Cache中共享數(shù)據(jù)的訪(fǎng)問(wèn)，提出了基于多級(jí)一致性協(xié)議的多核處理器WCET分析方法，解決多級(jí)一致性協(xié)議嵌套情況下的WCET分析問(wèn)題，完善了多核處理器Cache的分析框架，并實(shí) 現(xiàn) 一 個(gè) 基于 MESI（modify exclusive shared invalid）協(xié)議的高精度多核處理器WCET分析工具，為多核實(shí)時(shí)系統(tǒng)的WCET分析提供了支撐.

2 基于MESI協(xié)議的跨一致性域WCET分析方法

本節(jié)的核心工作在于提出一種多級(jí)一致性域的WCET分析方法，實(shí)現(xiàn)對(duì)多核處理器中多級(jí)一致性域的WCET分析.通過(guò)對(duì)一致性域內(nèi)部的Cache訪(fǎng)問(wèn)延遲和狀態(tài)轉(zhuǎn)換情況進(jìn)行分析，得出一致性域內(nèi)部的分析結(jié)果，根據(jù)是否進(jìn)行跨域數(shù)據(jù)訪(fǎng)問(wèn)決定下一步是否需要進(jìn)行跨域分析，從而實(shí)現(xiàn)一致性協(xié)議嵌套情況下的共享數(shù)據(jù)訪(fǎng)問(wèn)延遲分析.本文將該方法與當(dāng)前主要考慮指令Cache的分析方法相結(jié)合，增加了數(shù)據(jù)Cache中共享數(shù)據(jù)的訪(fǎng)問(wèn)分析，擴(kuò)展了多核處理器中Cache的干擾分析框架，進(jìn)一步完善了多核處理器WCET分析方法.

2.1 Cache組織結(jié)構(gòu)

共享存儲(chǔ)結(jié)構(gòu)是當(dāng)前應(yīng)用最為廣泛的多核處理器架構(gòu)，此種結(jié)構(gòu)對(duì)于每一個(gè)內(nèi)核而言都是對(duì)等的，每一個(gè)內(nèi)核的訪(fǎng)問(wèn)時(shí)間都是相同的，因此多核處理器屬于對(duì)稱(chēng)多處理器（symmetric multi-processor，SMP）.最初的多核處理器中只存在私有Cache和共享Cache，隨著CPU制造工藝的發(fā)展，當(dāng)前多核處理器已集成多級(jí)Cache.

采用SMP架構(gòu)的多處理器需要支持共享數(shù)據(jù)的Cache，通過(guò)讀寫(xiě)共享數(shù)據(jù)實(shí)現(xiàn)內(nèi)核之間的通信.在緩存共享數(shù)據(jù)時(shí)，可能會(huì)存在多個(gè)內(nèi)核對(duì)共享數(shù)據(jù)的爭(zhēng)用，也可能會(huì)在多個(gè)Cache中復(fù)制共享數(shù)據(jù)，導(dǎo)致多個(gè)數(shù)據(jù)副本不一致，因此共享數(shù)據(jù)Cache引入了一個(gè)新的問(wèn)題——Cache一致性問(wèn)題，需要引入一致性協(xié)議保證數(shù)據(jù)一致性.

MESI是一種典型的Cache一致性協(xié)議，也被稱(chēng)為Illinois MESI協(xié)議，是在原MSI協(xié)議的基礎(chǔ)上引入E狀態(tài)，用于表示獨(dú)占狀態(tài).在寫(xiě)入一個(gè)共享數(shù)據(jù)塊時(shí)，通常有2種寫(xiě)策略：寫(xiě)直達(dá)和寫(xiě)回.對(duì)于圖2所示的多級(jí)Cache組織結(jié)構(gòu)，由于寫(xiě)回策略對(duì)存儲(chǔ)器的帶寬要求低，能夠支持更多、更快速的處理器，所以最外層級(jí)別（簇（cluster）間）通常采用寫(xiě)回策略[3]；而對(duì)于簇內(nèi)的寫(xiě)入共享數(shù)據(jù)的策略，如果采用寫(xiě)回策略，會(huì)造成簇內(nèi)L1 Cache中數(shù)據(jù)和L2 Cache中的數(shù)據(jù)不一致的情況，在維護(hù)簇內(nèi)數(shù)據(jù)一致性的同時(shí)，還要考慮簇間一致性，造成一致性協(xié)議非常復(fù)雜，不利于硬件的實(shí)現(xiàn)，因此簇內(nèi)采用寫(xiě)直達(dá)的策略.

Fig.2 Multi-level Cache arrangement圖2 多級(jí)Cache組織結(jié)構(gòu)

寫(xiě)直達(dá)和寫(xiě)回適用于訪(fǎng)問(wèn)命中的情況，當(dāng)訪(fǎng)問(wèn)缺失時(shí)所采用的寫(xiě)策略為寫(xiě)分配（write allocation）和非寫(xiě)分配（no write allocation）兩種方式，通常寫(xiě)回與寫(xiě)分配策略配合使用，寫(xiě)直達(dá)和非寫(xiě)分配策略配合使用.

2.2 一致性域

多核處理器任務(wù)調(diào)度時(shí)存在多個(gè)內(nèi)核共同完成一個(gè)任務(wù)，或者將某些關(guān)鍵等級(jí)高的任務(wù)映射到特定的內(nèi)核上，因此，這些任務(wù)之間的數(shù)據(jù)交換僅僅在特定內(nèi)核之間進(jìn)行，如果使用一個(gè)一致性協(xié)議維護(hù)所有內(nèi)核的數(shù)據(jù)副本，將會(huì)產(chǎn)生大量的數(shù)據(jù)交互操作，造成網(wǎng)絡(luò)擁塞，降低執(zhí)行效率, 一種可行的方法是將所有的內(nèi)核進(jìn)行區(qū)域劃分[26]，每個(gè)區(qū)域使用獨(dú)立的一致性協(xié)議管理數(shù)據(jù)副本，該方法既能充分利用局部性原理，又能降低網(wǎng)絡(luò)負(fù)載.

定義1.一致性域.使用相同一致性協(xié)議管理數(shù)據(jù)副本的內(nèi)核集合，稱(chēng)之為一致性域.

一致性域的示意圖如圖3所示.

一致性域具有2個(gè)性質(zhì)：

性質(zhì)1.一致性域具有獨(dú)立性，即任意2個(gè)一致性域之間不存在交集.

性質(zhì)2.一致性協(xié)議在一致性域內(nèi)具有唯一性.

Fig.3 Coherence domain圖3 一致性域

2.3 多級(jí)一致性域

由于一致性協(xié)議只能維護(hù)域內(nèi)數(shù)據(jù)的一致性，當(dāng)存在跨域數(shù)據(jù)交互時(shí)，會(huì)導(dǎo)致無(wú)法保證域間數(shù)據(jù)的一致性，需要使用多級(jí)一致性協(xié)議進(jìn)行數(shù)據(jù)維護(hù)，相應(yīng)地，需要定義多級(jí)一致性域.多級(jí)一致性域采用分層劃域的思想，下層一致性域是上層一致性域的一個(gè)結(jié)點(diǎn)（clump）.

針對(duì)如圖2所示的硬件架構(gòu)，根據(jù)一致性域的定義，簇內(nèi)為1級(jí)一致性域，整個(gè)多核處理器構(gòu)成2級(jí)一致性域.處理器內(nèi)核在訪(fǎng)問(wèn)數(shù)據(jù)時(shí)，首先會(huì)訪(fǎng)問(wèn)私有Cache，如果訪(fǎng)問(wèn)缺失，則會(huì)訪(fǎng)問(wèn)下一級(jí)共享Cache，即簇內(nèi)共享Cache，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)范圍仍在一致性域內(nèi).如果訪(fǎng)問(wèn)命中，只需進(jìn)行域內(nèi)WCET分析即可；如果訪(fǎng)問(wèn)缺失，根據(jù)存儲(chǔ)器層次結(jié)構(gòu)訪(fǎng)問(wèn)次序，則需要進(jìn)行跨一致性域WCET分析.

2.4 關(guān)鍵參數(shù)說(shuō)明

在進(jìn)行多核處理器的Cache行為分析時(shí)，假設(shè)總線(xiàn)是完美的并且不存在讀和寫(xiě)隊(duì)列的限制，在此基礎(chǔ)上分析Cache一致性協(xié)議對(duì)內(nèi)存訪(fǎng)問(wèn)時(shí)間的影響.

首先假設(shè)處理器擁有私有Cache、共享Cache和內(nèi)存，Cache采用寫(xiě)回和寫(xiě)分配策略，Cache的訪(fǎng)問(wèn)分為讀和寫(xiě)，讀和寫(xiě)都會(huì)出現(xiàn)訪(fǎng)問(wèn)命中或缺失，我們從讀和寫(xiě)2個(gè)方面對(duì)Cache行為進(jìn)行分析，在開(kāi)始分析之前定義如下符號(hào)：

1） ψR(shí)(m,m′)/ψW(m,m′).表示域內(nèi) Cache 讀/寫(xiě)訪(fǎng)問(wèn)時(shí)間延遲和狀態(tài)轉(zhuǎn)換情況，m表示被訪(fǎng)問(wèn)的數(shù)據(jù)，m'表示被訪(fǎng)問(wèn)數(shù)據(jù)的副本.

2）HLi.表示在第i級(jí)Cache訪(fǎng)問(wèn)命中時(shí)間延遲.

3）LLi→Lj.表示數(shù)據(jù)從第i級(jí)Cache加載到第j級(jí)Cache的時(shí)間延遲.

4）Hmemory.表示主存訪(fǎng)問(wèn)命中時(shí)間延遲.

5）Inv/Inv′.表示 域內(nèi)/跨 域使其 他數(shù)據(jù)副本 失效的時(shí)間延遲.

6） ψ′R(m,m′)/ψ′W(m,m′).表示跨域 Cache 讀/寫(xiě)訪(fǎng)問(wèn)時(shí)間延遲和狀態(tài)轉(zhuǎn)換情況.

7）ms/m′s.表示本地/遠(yuǎn)程Cache狀態(tài).

8） Replacement /? Replacement.表示被訪(fǎng)問(wèn)共享數(shù)據(jù)被替換出Cache，導(dǎo)致替換缺失發(fā)生/未發(fā)生.

2.5 考慮一致性協(xié)議的WCET分析框架

現(xiàn)有工作對(duì)于Cache的分析主要集中在指令Cache，對(duì)于數(shù)據(jù)Cache的分析也僅限于本地?cái)?shù)據(jù)的分析.本文在基于抽象解釋的多級(jí)Cache分析框架基礎(chǔ)上，擴(kuò)展了共享數(shù)據(jù)分析這一功能.

如圖4所示，該分析框架的輸入為待分析程序和Cache模型.其中待分析程序提供控制流、地址信息，Cache模型中包括了Cache組織結(jié)構(gòu)、替換策略、讀寫(xiě)策略以及一致性協(xié)議，這些參數(shù)作為分析框架的輸入信息，提供給Cache分析方法.Cache的分析可分為2部分：數(shù)據(jù)Cache和指令Cache，其中數(shù)據(jù)Cache中共享數(shù)據(jù)的分析為本文的主要工作，將在后文中詳細(xì)介紹.最后，根據(jù)分析結(jié)果得出內(nèi)存訪(fǎng)問(wèn)的分類(lèi)以及訪(fǎng)問(wèn)的時(shí)間延遲，從而得出WCET的分析結(jié)果.

Fig.4 WCET analysis framework based on coherence protocol圖4 基于一致性協(xié)議的WCET分析框架

2.6 域內(nèi)WCET分析

2.6.1 域內(nèi)讀訪(fǎng)問(wèn)

當(dāng)內(nèi)核發(fā)出讀數(shù)據(jù)m的讀請(qǐng)求時(shí)，如果m存在于L1中，其狀態(tài)可能為E或者S并且未發(fā)生替換缺失，在L1中能夠讀命中，數(shù)據(jù)訪(fǎng)問(wèn)延遲為HL1，所有Cache塊的狀態(tài)不會(huì)發(fā)生改變.

如果數(shù)據(jù)m在域內(nèi)，m的狀態(tài)為E或者S但是發(fā)生替換缺失，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲為讀取L2中數(shù)據(jù)的時(shí)間，同時(shí)需要將數(shù)據(jù)從L2 Cache加載到本地L1 Cache中，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)延遲為max(,LL2→L1)，Cache狀態(tài)不發(fā)生變化，如圖5 (a)(b)所示.

如果數(shù)據(jù)m在域內(nèi)，m的狀態(tài)為I，且副本m'的狀態(tài)為E或者S時(shí)，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲為讀取L2中數(shù)據(jù)的時(shí)間，同時(shí)需要將數(shù)據(jù)從L2 Cache加載到本地L1 Cache中，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)延遲為max(,LL2→L1)，m的狀態(tài)轉(zhuǎn)換為S，副本m'的狀態(tài)轉(zhuǎn)換為 S，如圖5 (c)所示.

如果數(shù)據(jù)m不在域內(nèi)，在L2 Cache中會(huì)出現(xiàn)訪(fǎng)問(wèn)缺失，假定訪(fǎng)問(wèn)L2 Cache的時(shí)間為對(duì)于的取值我們將在2.7.1節(jié)中進(jìn)行分析.此時(shí)m的狀態(tài)由I轉(zhuǎn)換為E，L2 Cache的狀態(tài)需要根據(jù)L2的一致性協(xié)議進(jìn)一步分析，如圖5(d)所示.

根據(jù)以上分析，可以得出Cache域內(nèi)讀訪(fǎng)問(wèn)時(shí)間延遲和狀態(tài)轉(zhuǎn)換的狀態(tài)更新函數(shù)：

2.6.2 域內(nèi)寫(xiě)訪(fǎng)問(wèn)

當(dāng)內(nèi)核發(fā)出寫(xiě)m的請(qǐng)求時(shí)，如果m僅存在本地L1 Cache且狀態(tài)為E時(shí)，此時(shí)會(huì)發(fā)生Cache寫(xiě)命中.首先需要將數(shù)據(jù)寫(xiě)入到L1中，由于使用寫(xiě)直達(dá)策略，需要同時(shí)寫(xiě)入到L2當(dāng)中，因此數(shù)據(jù)訪(fǎng)問(wèn)時(shí)間為HL1+，Cache狀態(tài)不發(fā)生改變，如圖6(a)所示；如果m存在于L1 Cache中且狀態(tài)為S時(shí)，此時(shí)會(huì)發(fā)生Cache寫(xiě)命中，數(shù)據(jù)訪(fǎng)問(wèn)延遲為HL1+，狀態(tài)轉(zhuǎn)換為E，由于采用寫(xiě)失效的一致性協(xié)議，因此需要將副本的狀態(tài)修改為I，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)最終的延遲為 m ax(HL1+,Inv)，如圖6(b)所示.

如果數(shù)據(jù)m位于本地L1 Cache中，m的狀態(tài)為E或者S，并且發(fā)生替換缺失，此時(shí)會(huì)出現(xiàn)寫(xiě)缺失.如果m的狀態(tài)為E，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)時(shí)間為，并且狀態(tài)轉(zhuǎn)換為I，如圖6(c)所示；如果m的狀態(tài)為S，在進(jìn)行L2 Cache寫(xiě)操作之后，需要對(duì)其他副本進(jìn)行寫(xiě)失效，所以訪(fǎng)問(wèn)時(shí)間為 m ax(ψ′W,Inv)，m和副本m'的狀態(tài)都轉(zhuǎn)換為I，如圖6(d)所示.

Fig.5 Read-visit latency and state transition diagram of intra-domain圖5 域內(nèi)讀訪(fǎng)問(wèn)時(shí)間延遲及狀態(tài)轉(zhuǎn)換圖

Fig.6 Write-visit latency and state transition diagram of intra-domain圖6 域內(nèi)寫(xiě)訪(fǎng)問(wèn)時(shí)間延遲及狀態(tài)轉(zhuǎn)換圖

如果數(shù)據(jù)m在域內(nèi),m的狀態(tài)為I且副本m'的狀態(tài)為E或者S時(shí)，此時(shí)會(huì)對(duì)L2進(jìn)行寫(xiě)操作, 并將其他副本中的數(shù)據(jù)寫(xiě)失效, 考慮數(shù)據(jù)連貫性要求, 數(shù)據(jù)的寫(xiě)延遲為 m ax(ψ′W,Inv), 由于采用非寫(xiě)分配的方式, 本地L1的狀態(tài)不發(fā)生改變，其他副本的狀態(tài)從E/S轉(zhuǎn)換為 I, 如圖6(e)所示.

如果數(shù)據(jù)m不在域內(nèi)，類(lèi)比讀訪(fǎng)問(wèn)的情況，假定寫(xiě)L2 Cache的訪(fǎng)問(wèn)時(shí)間為.由于域內(nèi)采用非寫(xiě)分配法，所以此時(shí)m的狀態(tài)不發(fā)生任何變化，如圖6(f)所示.

根據(jù)以上分析，可以得出Cache域內(nèi)寫(xiě)訪(fǎng)問(wèn)時(shí)間延遲和狀態(tài)轉(zhuǎn)換的狀態(tài)更新函數(shù)：

2.7 跨域WCET分析

2.7.1 跨域讀訪(fǎng)問(wèn)

當(dāng)內(nèi)核發(fā)出讀數(shù)據(jù)m的讀請(qǐng)求時(shí)，如果需要對(duì)L2 Cache進(jìn)行讀訪(fǎng)問(wèn)，此時(shí)將會(huì)由上級(jí)一致性協(xié)議管理共享數(shù)據(jù).

如果數(shù)據(jù)m存在于域內(nèi)，并且位于本地L2 Cache中，對(duì)應(yīng)域內(nèi)讀訪(fǎng)問(wèn)的圖5(a)~(c)，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)時(shí)間為HL2，域間所有的Cache的狀態(tài)都不發(fā)生變化，如圖7(a)所示.

當(dāng)被訪(fǎng)問(wèn)數(shù)據(jù)m存在于L2 Cache中并且發(fā)生替換缺失，對(duì)應(yīng)域內(nèi)讀訪(fǎng)問(wèn)的圖5(d)，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲為HL3，同時(shí)需要將數(shù)據(jù)加載到L1 Cache中，考慮到連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)的延時(shí)為 m ax（HL3,LL3→L1），如果m的狀態(tài)為M或者E，則狀態(tài)會(huì)轉(zhuǎn)換為E，如果m的狀態(tài)為S，則狀態(tài)不發(fā)生改變，副本m'的狀態(tài)不發(fā)生改變，如圖7(b)(c)所示.

如果被訪(fǎng)問(wèn)數(shù)據(jù)m不存在于域內(nèi)，對(duì)應(yīng)域內(nèi)讀訪(fǎng)問(wèn)的圖5(d)，存在2種可能性：1）數(shù)據(jù)m本身不存在Cache中；2）數(shù)據(jù)m存在于其他域的Cache中.如果數(shù)據(jù)m不存在Cache中，此時(shí)需要通過(guò)內(nèi)存來(lái)讀取數(shù)據(jù)m，數(shù)據(jù)訪(fǎng)問(wèn)延遲為Hmemory，同時(shí)需要將數(shù)據(jù)從內(nèi)存中寫(xiě)回到L1 Cache中，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)延遲為 m ax(Hmemory,Lm→L1)，L2的狀態(tài)從I轉(zhuǎn)換為E，如圖7(d)所示.

如果數(shù)據(jù)存在于其他域中，即存在數(shù)據(jù)副本m'，如果其狀態(tài)是M，首先要將數(shù)據(jù)從其他域的L2 Cache中加載到本地域的L2中，然后再加載到L1中，最后從L1中讀取數(shù)據(jù)，其訪(fǎng)問(wèn)延遲為L(zhǎng)L2→L2+LL2→L1+HL1，此時(shí)L2中數(shù)據(jù)m的狀態(tài)從I轉(zhuǎn)換為S，其他域L2中數(shù)據(jù)副本m'狀態(tài)從M轉(zhuǎn)換為S，如圖7(e)所示.

如果數(shù)據(jù)副本m'的狀態(tài)為E或者S，將會(huì)在L3中讀取命中數(shù)據(jù)，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲為HL3，與此同時(shí)，數(shù)據(jù)將會(huì)加載到L1中，考慮連貫性要求，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲應(yīng)取 m ax(HL3,LL3→L1)，此時(shí)L2中數(shù)據(jù)m的狀態(tài)從I轉(zhuǎn)換為S，其他域L2中數(shù)據(jù)副本m'狀態(tài)換為S，如圖7(f)所示.

根據(jù)以上分析，可以得出Cache跨域讀訪(fǎng)問(wèn)時(shí)間和狀態(tài)轉(zhuǎn)換的狀態(tài)更新函數(shù)：

2.7.2 跨域?qū)懺L(fǎng)問(wèn)

當(dāng)內(nèi)核發(fā)出寫(xiě)數(shù)據(jù)m的寫(xiě)請(qǐng)求時(shí)，如果需要對(duì)L2 Cache進(jìn)行寫(xiě)訪(fǎng)問(wèn)，此時(shí)將由上級(jí)一致性協(xié)議管理共享數(shù)據(jù).

如果數(shù)據(jù)m在域內(nèi)（對(duì)應(yīng)域內(nèi)寫(xiě)訪(fǎng)問(wèn)圖6(a)~(e)的情況），并且位于本地L2 Cache中，狀態(tài)為S，需要將其他副本中的數(shù)據(jù)寫(xiě)失效，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)時(shí)間為 m ax(HL2,Inv′)，狀態(tài)轉(zhuǎn)換為M，副本的狀態(tài)由S轉(zhuǎn)換為I，如圖8(a)所示；如果m的狀態(tài)為M或者E，此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)時(shí)間為HL2，狀態(tài)轉(zhuǎn)換為M，其他Cache狀態(tài)不變，如圖8(b)所示.

Fig.7 Read-visit latency and state transition diagram of cross-domain圖7 跨域讀訪(fǎng)問(wèn)時(shí)間延遲及狀態(tài)轉(zhuǎn)換圖

如果被訪(fǎng)問(wèn)數(shù)據(jù)m不存在于域內(nèi)（對(duì)應(yīng)域內(nèi)寫(xiě)訪(fǎng)問(wèn)圖6(f)的情況）, 存在2種可能性：1）數(shù)據(jù)m本身不存在Cache中；2）數(shù)據(jù)m存在于其他域的Cache中.如果數(shù)據(jù)m不存在Cache中, 由于域間采用寫(xiě)分配，首先要將數(shù)據(jù)從內(nèi)存加載到L2 Cache中, 然后在L2 Cache中修改數(shù)據(jù), 此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲為HL2+Lm→L2，L2 Cache 的狀態(tài)從 I轉(zhuǎn)換為 M, 如圖8(c)所示.

如果數(shù)據(jù)存在于其他域內(nèi)，數(shù)據(jù)m的狀態(tài)為I，如果數(shù)據(jù)副本m'的狀態(tài)為M，首先要將數(shù)據(jù)從其他域加載到本地L2中，然后修改本地L2 Cache中的數(shù)據(jù)，狀態(tài)轉(zhuǎn)換為M，并且要將其他副本寫(xiě)失效，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)延遲為 m ax(HL2+LL2→L2,Inv′)，其他副本的狀態(tài)轉(zhuǎn)換為I，如圖8(d)所示；如果副本的狀態(tài)為E或者S，此時(shí)需要將數(shù)據(jù)從L3 Cache加載到本地L2 Cache中，狀態(tài)轉(zhuǎn)換為M，并且要將其他副本寫(xiě)失效，考慮連貫性要求，數(shù)據(jù)訪(fǎng)問(wèn)延遲為max(HL2+LL3→L2,Inv′)，副本的狀態(tài)準(zhǔn)換為I，如圖8(e)所示.

如果m為M,E,S狀態(tài)并且發(fā)生替換缺失時(shí)（對(duì)應(yīng)域內(nèi)寫(xiě)訪(fǎng)問(wèn)圖6(f)的情況）, 此時(shí)會(huì)發(fā)生Cache寫(xiě)缺失.首先將數(shù)據(jù)從 L3 Cache 加載到 L2 Cache, 然后執(zhí)行寫(xiě)操作.對(duì)于m的狀態(tài)為M和E的情況, 此時(shí)數(shù)據(jù)訪(fǎng)問(wèn)延遲為HL2+LL3→L2,m的狀態(tài)轉(zhuǎn)換為M, 如圖8(f)所示；如果m的狀態(tài)為S, 需要將其他副本中的數(shù)據(jù)寫(xiě)失效, 考慮連貫性要求, 數(shù)據(jù)訪(fǎng)問(wèn)延遲為max(HL2+LL3→L2,Inv′),m的 狀 態(tài) 由 S變 為 I, 如 圖8(g)所 示.

根據(jù)以上分析，可以得出Cache跨域?qū)懺L(fǎng)問(wèn)時(shí)間和狀態(tài)轉(zhuǎn)換的狀態(tài)更新函數(shù)：

Fig.8 Write latency and state diagram of cross-domain圖8 跨域?qū)懺L(fǎng)問(wèn)時(shí)間延遲及狀態(tài)轉(zhuǎn)換圖

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

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文在實(shí)驗(yàn)室原有多核處理器WCET分析工具的基礎(chǔ)上，擴(kuò)展其中數(shù)據(jù)Cache的分析方法，增加了對(duì)MESI一致性協(xié)議的支持，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)支持Cache一致性協(xié)議的多核處理器WCET分析工具Roban.通過(guò)該工具對(duì)多核處理器進(jìn)行WCET分析，并將分析結(jié)果與GEM5仿真工具模擬執(zhí)行得到的時(shí)間進(jìn)行對(duì)比，從而驗(yàn)證分析方法的有效性.

實(shí)驗(yàn)針對(duì)4核處理器展開(kāi)分析，每2個(gè)內(nèi)核組成1簇，即2個(gè)1級(jí)一致性域和1個(gè)2級(jí)一致性域，處理器存儲(chǔ)結(jié)構(gòu)參照?qǐng)D2，關(guān)鍵參數(shù)配置如表1所示.從M?lardalen大學(xué)WCET研究小組測(cè)試用例集中選取典型測(cè)試用例進(jìn)行測(cè)試.

Table 1 Parameters Configuration of Multi-Core Processor表1 多核處理器參數(shù)配置

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

實(shí)驗(yàn)一共分為2組，第1組Cache相聯(lián)度為4路組相聯(lián)，第2組Cache相聯(lián)度為8路組相聯(lián).分別調(diào)整 L1，L2，L3 Cache的容量，得出在不同 Cache配置情況下的WCET值，結(jié)果如圖9所示.

從圖9可以看出, Roban工具得到的WCET分析結(jié)果均大于GEM5仿真得到的結(jié)果,證明了本文方法的安全性.

為了驗(yàn)證本文方法的有效性，采用Spearman相關(guān)性分析法對(duì)圖9中Roban分析結(jié)果與GEM5仿真結(jié)果進(jìn)行相關(guān)性分析，得出的相關(guān)性系數(shù)矩陣如圖10所示，其中橫坐標(biāo)為Roban分析工具對(duì)應(yīng)的測(cè)試結(jié)果，縱坐標(biāo)表示GEM5仿真結(jié)果.從圖10中可以看出，帶有數(shù)字標(biāo)簽的矩陣元素為相同測(cè)試用例在不同Cache參數(shù)配置情況下得到WCET結(jié)果的相關(guān)性系數(shù)，相關(guān)性系數(shù)不小于0.98，說(shuō)明Roban和GEM5兩種工具得出的結(jié)果顯著相關(guān)，同時(shí)表明了圖9中的曲線(xiàn)變化趨勢(shì)基本一致.

Fig.9 Comparison of GEM5 simulation results and analysis results圖9 GEM5仿真結(jié)果與分析結(jié)果對(duì)比

Fig.10 Correlation coefficient matrix diagram of GEM5 and Roban圖10 GEM5與Roban相關(guān)性系數(shù)矩陣圖

為了驗(yàn)證本文提出分析方法的精確性，采用過(guò)估計(jì)率這一指標(biāo)對(duì)分析結(jié)果進(jìn)行評(píng)估，過(guò)估計(jì)率 R 計(jì)算方式為

過(guò)估計(jì)率的統(tǒng)計(jì)結(jié)果如圖11所示.由圖11可知，本文方法分析得出的過(guò)估計(jì)率最大值為1.476，最小值為1.158，平均值為1.30，對(duì)比瑞典皇家理工學(xué)院[25]設(shè)計(jì)實(shí)現(xiàn)的 WCET分析工具 KTA（KTH’s timing analysis），其平均過(guò)估計(jì)率為2.08，本文方法的過(guò)估計(jì)率降低了0.78.

Fig.11 Statistical results of over estimation rate圖11 過(guò)估計(jì)率統(tǒng)計(jì)結(jié)果

4 結(jié) 論

本文通過(guò)分析多級(jí)一致性協(xié)議體系架構(gòu)下的Cache狀態(tài)轉(zhuǎn)換和內(nèi)存訪(fǎng)問(wèn)延遲，得出多級(jí)一致性域WCET分析方法.實(shí)驗(yàn)表明，本文方法能夠精確估算出多核處理器任務(wù)WCET，在改變Cache配置參數(shù)的情況下，GEM5仿真結(jié)果與本文工具Roban分析結(jié)果相關(guān)性系數(shù)不低于0.98，表明本文方法分析結(jié)果的變化趨勢(shì)與GEM5仿真結(jié)果一致；通過(guò)與當(dāng)前分析方法進(jìn)行對(duì)比，證明本文方法相比現(xiàn)有方法的過(guò)估計(jì)率降低了0.78.

本文在進(jìn)行Cache行為分析時(shí)，將總線(xiàn)假設(shè)為理想狀態(tài)，而在實(shí)際的一致性協(xié)議中，如果存在大量的數(shù)據(jù)交互，將會(huì)導(dǎo)致總線(xiàn)發(fā)生阻塞，在以后的工作中，應(yīng)將Cache之間共享總線(xiàn)納入到分析范圍中，進(jìn)一步提高WCET分析結(jié)果的準(zhǔn)確性.另外本文在考慮一致性協(xié)議時(shí)僅考慮了MESI協(xié)議，而在實(shí)際工程領(lǐng)域存在多種一致性協(xié)議，如Intel i7使用的MESIF協(xié)議、AMD Opteron使用的MOESI協(xié)議等，在后續(xù)的工作中將針對(duì)不同的一致性協(xié)議展開(kāi)分析.

作者貢獻(xiàn)聲明：朱怡安提出研究思路和指導(dǎo)意見(jiàn)；史先琛提出了算法并撰寫(xiě)論文；姚燁、李聯(lián)負(fù)責(zé)實(shí)現(xiàn)算法并設(shè)計(jì)實(shí)驗(yàn)方案；任鵬遠(yuǎn)、董威振、李佳鈺參與實(shí)驗(yàn)方案設(shè)計(jì)并整理實(shí)驗(yàn)數(shù)據(jù).