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

有效

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

一種支持指令預取的多核緩存WCET分析方法，屬于嵌入式實時系統應用技術領域。本發明在基于共享緩存的多核架構基礎上，針對指令預取中的WCET分析問題，通過對指令預取語義進行擴展，引入緩存提前訪問分類，來分析出指令預取對私有L1指令緩存和共享L2指令緩存狀態的影響。以提高應用程序WCET分析的精確度。本發明可廣泛應用于實時系統中任務的可調度分析，以獲得精確，緊湊的WCET估值。

技術領域

本發明涉及一種任務最壞情況執行時間(Worst Case Execution Time,WCET)分析方法，尤其是一種支持指令預取的多核緩存WCET分析方法，屬于嵌入式實時系統應用領域。

背景技術

隨著半導體技術的快速發展，多核處理器開始廣泛被應用于無人機、高鐵、汽車、工廠自動化等嵌入式實時控制系統。與傳統的通用計算機系統不同，在這類嵌入式實時系統中，任務的執行有著嚴格的時間約束，系統中所有任務必須在規定的截止期前完成，否則可能會引發嚴重甚至災難性的后果。因此，在設計這類實時系統時，需要提前獲知系統中任務WCET估值，獲得任務最差情況執行時間的過程稱為WCET分析，WCET分析不僅是實時系統時間特性驗證的核心任務，也是實時系統可調度分析的基礎。

目前，在多核處理器中，為了提升應用程序的訪存性能，通常采用指令預取來隱藏存儲器訪問延遲。該技術的基本思想是：提前將程序將來需要但目前不在緩存中的指令預取到緩存中，當處理器核需要訪問此指令時，由于該指令已經被預取到緩存中，從而避免了處理器核在訪問緩存時的失效行為，同時處理器核可以與低層存儲系統中取指令的時間重疊，減少了流水線停頓對程序執行時間的影響，提高了系統的性能。然而,預取雖然可以減少程序在緩存中的缺失數，但是也會改變指令在私有L1緩存和共享L2緩存中的命中\缺失狀態，從而導致任務的WCET分析變得復雜。現有研究在分析指令預取對任務執行時間的影響時，假設預取總是影響指令在所有緩存層中的命中缺失狀態，以簡化WCET分析。然而，指令請求訪問數據時并不一定要訪問所有的緩存層,因此，現有的分析方法通常導致任務WCET估算過于保守。基于這一原因，本發明實現了一種支持指令預取的WCET分析方法。

發明內容

本發明的目的在于克服現有多核共享緩存WCET分析技術過于復雜以及任務WCET估算過于保守的局限性，提出了一種支持指令預取的多核緩存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：更新函數：一個抽象緩存狀態更新函數：用來更新抽象緩存狀態；