[發明專利]一種支持指令預取的多核緩存WCET分析方法

有效

• 申請號: 201710996826.1
• 申請日: 2017-10-19
• 公開（公告）號: CN107844380B
• 公開（公告）日: 2020-10-27
• 發明（設計）人: 付引霞;甘志華;張銘泉;安立奎;古志民
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F11/00
• 分類號: G06F11/00;G06F11/34
• 代理公司: 北京正陽理工知識產權代理事務所(普通合伙) 11639
• 代理人: 唐華

1.一種支持指令預取的多核緩存WCET分析方法，其特征在于：改善傳統WCET分析中不考慮預取指令對請求在緩存中狀態的影響，為了判斷預取指令是否影響請求在私有L1緩存和共享L2緩存中的狀態，在緩存訪問分類(Cache Access Classification，CAC)的基礎上，引入緩存提前訪問分類(Cache Preceding Access Classification，CPAC)并進行語義擴展分析，以確定提前訪問緩存的預取操作對緩存狀態(Cache State Classification，CSC)的影響，提高了任務WCET分析的精確度；

具體實現步驟如下：

步驟1：識別預取指令；

步驟2：構建請求的緩存提前訪問分類CPAC；

步驟2在步驟1分析得到預取指令的基礎上，基于請求的緩存訪問分類CAC構建提前訪問分類CPAC，所述步驟2具體又包括子步驟2.1和步驟2.2；

步驟2.1請求的緩存狀態分析；

本步驟2.1對程序中一段順序的執行序列,只有一個入口,只有一個出口的基本塊所映射的內存塊進行緩存抽象狀態分析，通過使用以下3種緩存分析方法：Must緩存語義分析、May緩存語義分析和Persistence緩存語義分析獲得每個基本塊所映射內存塊的抽象狀態；

(A)Must緩存語義分析

對于一個內存塊訪問，本步驟(A)判定對該內存塊的引用是否是必然命中的(AlwaysHit，AH)；若則可判斷內存塊m在緩存上是必然命中的，這里x表示內存塊m在抽象組緩存中的位置，其中，位置就是指緩存組相對年齡；步驟(A)中用函數分別對抽象組和抽象緩存狀態進行更新，表示把y映射到z；函數和用公式(2)和(3)表達：

令分別是抽象組和抽象緩存狀態聯合函數，則表達為公式(4)和(5)：

對于內存塊m，如果對于任意y,1≤y≤A,則能確定對內存塊m的訪問在緩存上是AH的；

(B)May緩存語義分析

對于一個內存塊訪問，本步驟(B)判定對該內存塊的引用是否是必然缺失(AlwaysMiss，AM)，若對于任意y,1≤y≤A,則該內存塊一定不在緩存中，步驟(B)中用函數分別對抽象組和抽象緩存狀態進行更新，具體采用公式(6)和(7)進行更新；

令分別是抽象組和抽象緩存狀態聯合函數，則

and x＝max(a,b)}

對于內存塊m，如果對于任意y,1≤y≤A,則能確定對內存塊m的訪問在緩存上是AM的；

(C)Persistence緩存語義分析

對于一個內存塊訪問，本步驟(C)判定對該內存塊的引用是否是第一次訪問是缺失，其余次的訪問是命中；每個緩存組引入了一個額外的緩存行l_⊥，收集被移除緩存的內存塊；步驟(C)中用函數分別對抽象組和抽象緩存狀態進行更新，具體采用公式(9)和(10)進行更新；

令分別是抽象組和抽象緩存狀態更新函數，則和分別表述為：

x＝max(a,b)}

對內存塊m的訪問在緩存上是PS的，其中PS為Persistence的縮寫，表示指令一旦被取入緩存，將不會替換出去；

步驟2.2擴展請求的緩存狀態

針對步驟2.1，設M_IP(i)＝{mem(1)+1,mem(1)+2,…,mem(2)+N}代表指令i順序預取下N個指令緩存行，這些被預取的N行指令將會更新指令i在指令緩存的acs_out(i)，即將預取指令融入到緩存狀態分析中，令分別表示指令i在步驟2.1中Must，May和Persistence分析下支持指令預取語義的緩存狀態更新函數，則有：

其中表示用緩存行imem(i)+1,…,imem(i)+N依次更新acs_in(i)；

對于一條指令k，其CPAC可分為“總提前訪問”(Always Preceding，AP)、“從不提前訪問”(Never Preceding，NP)、“第一次提前訪問”(First Preceding，FP)和“不確定是否提前訪問”(Uncertain Preceding，UP)：這里AP意味著k總是提前訪問L2緩存；NP意味著k從不提前訪問L2緩存；FP意味著k第一次會提前訪問L2緩存，其余則不會；UP意味著不能確定是否會訪問L2緩存；

對于集合I中任意一條指令k，用CPAC(k)表示它在L2緩存上的CPAC，CPAC(k)依賴于支持指令預取的L1指令緩存分析結果，其由可以預取它的前驅指令在L1指令緩存的命中/缺失狀態決定，用下面公式(14)計算指令k的CPAC：

對于指令k，用acs_omust(k)，acs_omust(k)，acs_omust(k)分別表示指令k在Must，May和Persistence緩存分析下的抽象緩存輸出狀態，這里有：

上述(A)、(B)以及(C)三種緩存語義分析的執行順序如下：

首先，執行(A)Must緩存語義分析，如果指令k沒有被預取，表示所有能夠預取指令k的指令在L1指令緩存上都是命中，指令k從不會被預取，其CPAC(k)是NP，跳至步驟3；

其次，執行(B)May緩存語義分析，如果指令k被預取，表示預取指令k的指令在L1緩存上總是缺失；指令k在L1緩存上一定不是命中，指令k總會被預取，其CPAC(k)是AP，跳至步驟3；

第三，如果CPAC(k)不是NP也不是AP，執行(C)Persistence緩存語義分析，如果在Persistence緩存語義分析中指令k被預取，表示預取指令k的指令在L1緩存上不是總命中，也不是總缺失，而是第一次缺失，指令k在第一次會被預取，其CPAC(k)是FP；其它情況則不確定指令k何時被預取，其CPAC(k)是UP；

步驟3：任務的L1緩存狀態分析；

步驟4：任務的L2緩存狀態分析；

步驟5：計算任務的WCET；

至此，從步驟1到步驟5，完成了一種支持指令預取任務WCET的分析方法；

有關符號和術語的含義如下：設各級緩存均為A-way組關聯型緩存結構，各級緩存均使用LRU替換策略；令capacity表示緩存容量，linesize表示緩存行大小，緩存缺失時，從下一級存儲取得的連續字節數，則緩存可以容納n＝capacity/linesize個緩存行，緩存組的集合可表示為F＝f₁,f₂,…f_n/A，其中，n/A是緩存的組數；f_i(i≤n/A)表示一個組緩存行序列L＝l₁,l₂,…l_n/A，令函數adr:M→N₀計算內存塊的地址，函數計算內存塊所映射到的緩存組，則set函數可表示為(1)：

set(m)＝f_i； (1)

其中，i＝adr(m)％(n/A)+1，％表示取余操作；

用Φ代表一個任務的緩存行沒有映射到的內存塊，則M'＝M∪Φ；

定義1：抽象組狀態：一個抽象組狀態是對應一個函數其中表示所有抽象組狀態的集合，L表示一個組緩存行序列；

定義2：抽象緩存狀態：一個抽象緩存狀態(ACS)是一個函數其中表示所有抽象緩存狀態的集合；

定義3：更新函數：一個抽象緩存狀態更新函數：用來更新抽象緩存狀態；

定義4：聯合函數：在任務的控制流程圖中，對具有多個前驅的結點進行抽象緩存狀態聯合，一個抽象緩存狀態聯合函數表示為：