[發明專利]一種基于采樣的應用程序CPU末級高速緩存缺失率曲線的預測方法

有效

• 申請號: 201911309038.6
• 申請日: 2019-12-18
• 公開（公告）號: CN111258927B
• 公開（公告）日: 2022-05-03
• 發明（設計）人: 向耀程;肖俊;汪小林;羅英偉
• 申請（專利權）人: 北京大學;鵬城實驗室
• 主分類號: G06F12/0802
• 分類號: G06F12/0802;G06F12/0893
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 陳艷

本發明提出一種基于采樣的應用程序CPU末級高速緩存缺失率曲線的預測方法，屬于計算機體系結構領域，包括以下步驟：讓目標程序在處理器上運行，設計一組訪存模式可控的微程序來訪問指定末級高速緩存LLC組，與目標程序在指定LLC組發生資源競爭；通過采樣收集一段時間內不同LLC組上的緩存缺失數量；通過控制微程序的訪存模式改變它所占用的緩存塊數量，改變目標程序所在指定LLC組上占用的緩存大小；計算未被微程序影響的LLC組上的緩存缺失數與受影響的組上緩存缺失數之差，據此得到目標程序的缺失率曲線。本方法既能消除事離線探測方法的局限性，又能避免在線預測方法對程序性能的干擾。

技術領域

本發明涉及一種基于采樣的應用程序CPU末級高速緩存缺失率曲線的高效探測方法，屬于計算機體系結構領域。

背景技術

在現代多核處理器中，人們通常加入高速緩存(Cache)來減小應用程序的訪存延遲。基本原理是利用應用程序的局部性，將可能被重用的數據放入更快的存儲介質Cache中。Cache通常以層次性的結構構建，目前主流多核處理器大都采用3級Cache的結構(見圖1)，越靠近計算核心的Cache延遲越低同時容量也越小。計算核心在訪問內存時，首先會從第一級高速緩存(L1 Cache)中尋找數據，如果發現數據缺失則從第二級高速緩存(L2Cache)中尋找，若仍然缺失則從末級高速緩存(LLC)中尋找。如果末級緩存中仍然沒有目標數據則訪問主存，并將該數據依次存放于各級高速緩存中方便下次使用。其中，L1和L2Cache由本地的計算核心私有，而第三級的LLC則由同一CPU芯片上的所有計算核心共享。

如何緩解各計算核心在LLC上的資源競爭一直是云計算廠商面臨的重要問題。目前的主流處理器中都實現了LLC隔離機制來根據每個計算核心的需求分配LLC，例如Intel處理器的CAT(Cache Allocation Technology)和ARM處理器的MPAM(Memory SystemResource Partitioning and Monitoring)。這些技術為LLC的資源分配提供了硬件支持，但仍然需要根據每個計算核心上負載的應用程序的特征選擇合適的LLC分配方案。LLC一般采用最近最少用(Least Recently Used，LRU)的替換策略，默認最近被訪問的數據最可能被重新訪問，而最久沒被訪問的數據最可能不再被訪問。在多計算核心共享LLC的場景下，可能存在一個訪存速度很快但沒有數據重用的LLC污染型程序。它不能從更大的LLC中獲益，但它會將LLC中大量的數據塊替換成自己的數據，使得其他應用程序的性能下降。為解決這類問題，首先需要研究應用程序對LLC的敏感性，即程序的緩存缺失率與它所分配到的LLC大小之間的關系。業界通常用缺失率曲線(Miss Ratio Curve，MRC)來描述這種關系。MRC的橫軸為程序的緩存大小，縱軸為程序在給定大小的緩存上的缺失率。

目前主要有兩種探測應用程序LLC MRC的方法：(1)事先單獨運行目標程序多次，每次分配給它不同大小的LLC。然后利用硬件計數器測量每次運行過程中的LLC訪問次數和LLC缺失次數，從而得到不同LLC大小下應用程序的緩存缺失率。(2)在應用程序的運行過程中，收集目標程序訪問LLC的地址序列，并根據這些地址序列實時預測目標程序的MRC。但這兩種方法都存在明顯的缺陷。方法1需要在離線環境下事先多次運行程序，它無法支持數據中心中實時調度的任務。方法2則會因為收集訪存序列引入過多的額外存儲開銷而影響目標程序性能。并且這兩種方法實時收集到的訪存序列總是存在一定程度上的缺失，因此這種方法直接預測出的MRC往往不夠精確。

發明內容

本發明的目的是利用訪存地址采樣技術，實現一種低開銷、高精度的實時LLC MRC預測方法，既能消除事離線探測方法的局限性，又能避免在線預測方法對程序性能的干擾。

本方法基于應用程序在每個LLC組上的訪存行為與程序整體的訪存行為一致，并且少量LLC組占用量的減少不影響程序的總體性能。

據此本發明提出一種基于采樣的應用程序CPU末級高速緩存缺失率曲線的預測方法，包括以下步驟：