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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

2.2 一致性域

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

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

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

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

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

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

Fig.3 Coherence domain圖3 一致性域

2.3 多級一致性域

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

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

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

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

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

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

2）HLi.表示在第i級Cache訪問命中時(shí)間延遲.

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

4）Hmemory.表示主存訪問命中時(shí)間延遲.

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

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

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

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

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

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

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

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

如果數(shù)據(jù)m在域內(nèi)，m的狀態(tài)為E或者S但是發(fā)生替換缺失，此時(shí)數(shù)據(jù)訪問延遲為讀取L2中數(shù)據(jù)的時(shí)間，同時(shí)需要將數(shù)據(jù)從L2 Cache加載到本地L1 Cache中，考慮連貫性要求，數(shù)據(jù)訪問延遲為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ù)訪問延遲為讀取L2中數(shù)據(jù)的時(shí)間，同時(shí)需要將數(shù)據(jù)從L2 Cache加載到本地L1 Cache中，考慮連貫性要求，數(shù)據(jù)訪問延遲為max(,LL2→L1)，m的狀態(tài)轉(zhuǎn)換為S，副本m'的狀態(tài)轉(zhuǎn)換為 S，如圖5 (c)所示.

如果數(shù)據(jù)m不在域內(nèi)，在L2 Cache中會出現(xiàn)訪問缺失，假定訪問L2 Cache的時(shí)間為對于的取值我們將在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)讀訪問時(shí)間延遲和狀態(tài)轉(zhuǎn)換的狀態(tài)更新函數(shù)：

2.6.2 域內(nèi)寫訪問

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

如果數(shù)據(jù)m位于本地L1 Cache中，m的狀態(tài)為E或者S，并且發(fā)生替換缺失，此時(shí)會出現(xiàn)寫缺失.如果m的狀態(tài)為E，此時(shí)數(shù)據(jù)訪問時(shí)間為，并且狀態(tài)轉(zhuǎn)換為I，如圖6(c)所示；如果m的狀態(tài)為S，在進(jìn)行L2 Cache寫操作之后，需要對其他副本進(jì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)讀訪問時(shí)間延遲及狀態(tài)轉(zhuǎn)換圖

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

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

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

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

2.7 跨域WCET分析

2.7.1 跨域讀訪問

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

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

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

如果被訪問數(shù)據(jù)m不存在于域內(nèi)，對應(yīng)域內(nèi)讀訪問的圖5(d)，存在2種可能性：1）數(shù)據(jù)m本身不存在Cache中；2）數(shù)據(jù)m存在于其他域的Cache中.如果數(shù)據(jù)m不存在Cache中，此時(shí)需要通過內(nèi)存來讀取數(shù)據(jù)m，數(shù)據(jù)訪問延遲為Hmemory，同時(shí)需要將數(shù)據(jù)從內(nèi)存中寫回到L1 Cache中，考慮連貫性要求，數(shù)據(jù)訪問延遲為 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ù)，其訪問延遲為LL2→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，將會在L3中讀取命中數(shù)據(jù)，此時(shí)數(shù)據(jù)訪問延遲為HL3，與此同時(shí)，數(shù)據(jù)將會加載到L1中，考慮連貫性要求，此時(shí)數(shù)據(jù)訪問延遲應(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跨域讀訪問時(shí)間和狀態(tài)轉(zhuǎn)換的狀態(tài)更新函數(shù)：

2.7.2 跨域?qū)懺L問

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

如果數(shù)據(jù)m在域內(nèi)（對應(yīng)域內(nèi)寫訪問圖6(a)~(e)的情況），并且位于本地L2 Cache中，狀態(tài)為S，需要將其他副本中的數(shù)據(jù)寫失效，考慮連貫性要求，數(shù)據(jù)訪問時(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ù)訪問時(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 跨域讀訪問時(shí)間延遲及狀態(tài)轉(zhuǎn)換圖

如果被訪問數(shù)據(jù)m不存在于域內(nèi)（對應(yīng)域內(nèi)寫訪問圖6(f)的情況）, 存在2種可能性：1）數(shù)據(jù)m本身不存在Cache中；2）數(shù)據(jù)m存在于其他域的Cache中.如果數(shù)據(jù)m不存在Cache中, 由于域間采用寫分配，首先要將數(shù)據(jù)從內(nèi)存加載到L2 Cache中, 然后在L2 Cache中修改數(shù)據(jù), 此時(shí)數(shù)據(jù)訪問延遲為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，并且要將其他副本寫失效，考慮連貫性要求，數(shù)據(jù)訪問延遲為 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，并且要將其他副本寫失效，考慮連貫性要求，數(shù)據(jù)訪問延遲為max(HL2+LL3→L2,Inv′)，副本的狀態(tài)準(zhǔn)換為I，如圖8(e)所示.

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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