基于分類的預取感知緩存分區(qū)機制

陳玲玲，焦童，汪玲，安鑫，李建華

（1 合肥工業(yè)大學 計算機與信息學院，合肥 230009；2 安徽交通職業(yè)技術(shù)學院，合肥 230051）

0 引言

多核處理器（Chip Multiprocessor，簡稱為CMP）是當前通用處理器的主流架構(gòu)，該架構(gòu)下多個核心共享最后一級緩存（Last－Level Cache，簡稱LLC）和片外帶寬等共享資源。多個核心共享LLC 會導致訪存干擾，從而影響系統(tǒng)性能和融合多核處理器的服務質(zhì)量。具體來說，當不同的應用程序運行在多核處理器的不同核心上時，會同時發(fā)出內(nèi)存請求，彼此相互沖突，增加內(nèi)存訪問延遲，使得每個應用程序比單獨運行時更慢。

硬件預取是減少內(nèi)存訪問延遲的主流技術(shù)之一。通過學習當前程序的訪存模式來預測程序之后一段時間內(nèi)的訪存行為，并在程序發(fā)出訪存請求之前將數(shù)據(jù)預取進高速緩沖寄存器，來隱藏內(nèi)存訪問延遲［1］。但預取也可能會導致緩存層次結(jié)構(gòu)污染，并在內(nèi)存系統(tǒng)中產(chǎn)生過多的流量和爭用，增加核間干擾。因此，配備預取機制的多核處理器，減少核間干擾是提升系統(tǒng)性能的主要瓶頸之一。

先前的大量工作提出了基于預取來減少核間干擾的一些方案。但是，大多數(shù)預取方案都沒有考慮過非內(nèi)存密集型程序的特殊性。由于其在運行期間發(fā)出的訪存請求遠低于其它程序，若不對其優(yōu)先處理，就容易造成以下問題：

（1）發(fā)出的訪存指令少導致預取器難以找到程序的訪存規(guī)律，若非內(nèi)存密集程序盲目的配置，過于激進的預取，由于其局部性不強，容易將其它潛在有用的數(shù)據(jù)踢出緩存，造成嚴重的緩存污染，從而影響其它應用程序的性能。

（2）如果簡單地將LLC 平均分給各個應用程序，非內(nèi)存密集型程序很容易被內(nèi)存密集型程序發(fā)出的頻繁訪存請求擠出緩存，增加非內(nèi)存密集型程序的缺失率。

因此本文提出了基于分類的預取感知緩存分區(qū)機制（簡稱CPAP）。該機制基于非內(nèi)存密集型程序的特點，進一步研究緩存分區(qū)和預取控制的方式。

1 相關(guān)工作

硬件預取是提升處理器性能的核心技術(shù)之一，之前已經(jīng)有很多關(guān)于提升預取性能的研究［2］。下面將介紹與本文研究內(nèi)容相關(guān)的一些預取的技術(shù)。

1.1 緩存分區(qū)

緩存分區(qū)可以將受預取干擾嚴重的程序單獨放入一個分區(qū)中，避免數(shù)據(jù)塊被擠出LLC，導致內(nèi)存訪問延遲增大。Selfa等提出了一種基于集群的緩存分區(qū)機制，以提高多核處理器的公平性，該機制根據(jù)二級緩存停頓周期數(shù)將核心上的應用歸類為集群，為不同的應用分配不同的緩存路數(shù)［3］；Qureshi等提出了一種基于程序?qū)嵱眯缘木彺娣謪^(qū)機制（簡稱UCP），在多個應用程序之間劃分共享的LLC，UCP 根據(jù)應用程序利用緩存空間的實用性高低為其分配合適數(shù)量的緩存路數(shù)，以提升緩存空間的使用效率［4］；Sun等提出了協(xié)調(diào)控制預取和緩存分區(qū)技術(shù)（簡稱CMM）來提高多核系統(tǒng)性能，CMM 根據(jù)預取是否激進將其分為2 類，為預取激進的程序分配較小數(shù)量的緩存路數(shù)，其它程序共享剩余緩存路數(shù)［5］。

1.2 全局預取控制

Ebrahimi等提出了一種分層控制預取激進程度的方法來動態(tài)控制多核處理器中的硬件預取器，該方法可動態(tài)地識別出引起核心間干擾的應用程序，并限制其預取的激進程度，以減少對其它應用的干擾［6］；Panda等提出了一種協(xié)調(diào)控制預取器激進程度的機制來提高多核系統(tǒng)的公平性，該機制探索了預取器的控制決策之間的相互作用，并基于多核系統(tǒng)的公平性來控制預取器，協(xié)調(diào)了預取器與整體公平性的關(guān)系［7］。

1.3 其它預取相關(guān)的研究

除了控制預取的激進程度之外，如何提升預取的精度同樣重要。本文并未提出新的預取技術(shù)，主要是基于步幅預取器的優(yōu)化，可以將本文提出的機制運用到其它經(jīng)硬件預取器上，比如反饋指導預取［8］，沙箱預?。?］等等。Selfa等［10］提出了激活／停用預提取器來正確處理內(nèi)存帶寬，從而改善性能。Navarro等［11］提出了帶寬感知的預取配置（簡稱BAPC）來提高多程序工作負載的性能。Seshadri等［12］提出了基于信息的預取塊替換策略。該機制只將預測準確的預取塊以高優(yōu)先級方式插入到緩存中，從而緩解緩存污染。Huang等［13］提出了通過控制預取距離來減少預取污染，該方法估算特定應用的預取距離上限，然后分析增加預取距離對共享緩存污染的影響，以此來減少共享的緩存污染。Lee等［14］提出了預取感知DRAM 控制器來動態(tài)調(diào)整預取請求優(yōu)先級技術(shù)，該方法預取請求的有用性，并根據(jù)估算值動態(tài)調(diào)整其調(diào)度和緩沖區(qū)管理策略，實現(xiàn)最大程度地提高有用的預取的性能。Ebrahimi等［15］提出了預取感知共享資源管理器，該方法既可以利用預取的優(yōu)勢，又可以管理多核芯片的共享資源以獲得高性能和公平性。Wu等［16］提出了預取感知緩存管理，該方法通過修改緩存插入策略和命中率提升策略來以不同方式對待需求和預取請求，消除了預取對替換策略的影響。

2 基于分類的預取感知緩存分區(qū)機制

2.1 CPAP 整體架構(gòu)

CPAP 的目標是減少非內(nèi)存密集型程序因預取引起的核間干擾而性能降低。CPAP 先識別非內(nèi)存密集型程序，通過預取控制和緩存分區(qū)來限制其資源使用，以減少核間干擾，從而提高系統(tǒng)性能和公平性。CPAP 被設(shè)計成一種前端和后端分離的結(jié)構(gòu)，如圖1所示。前端負責檢測，主要檢測2 類程序：非內(nèi)存密集型程序和預取友好程序；后端負責控制，根據(jù)前端檢測分類的結(jié)果，進行相應的預取配置和緩存分區(qū)方案。

圖1 CPAP 整體架構(gòu)Fig.1 CPAP architecture

CPAP 將應用程序的執(zhí)行過程分為多個間隔（Interval），在每個執(zhí)行周期結(jié)束時，該機制的前端會收集運行時的統(tǒng)計信息并檢測當前程序是否為非內(nèi)存密集型程序，判斷預取的準確性的高低。隨后，后端會通過該機制的類別做出相應的預取控制，下一個執(zhí)行時期就會使用該預取配置進行操作。

2.2 前端：收集數(shù)據(jù)并檢測

2.2.1 檢測預取友好型程序

預取友好程序是指程序通過預取獲得了很好的性能提升。根據(jù)這個特性，本文使用預取的激進程度（Aggressiveness，簡稱Agg）和每周期執(zhí)行指令數(shù)加速比（IPC Speedup，簡稱IS）這一組合指標來判斷預取是否友好。其中，預取的激進程度表示預取是否開啟，IS 代表性能是否提升。

在文中所提出的方案中，預取的激進程度主要取決于預取的準確性（Accuracy，簡稱Acc），準確性計算主要使用2 個計數(shù)器：

（1）預取計數(shù)器（pref－total）：用于記錄預取器發(fā)出的預取請求次數(shù)；

（2）有用預取計數(shù)器（use－total）：記錄預取的緩存塊被CPU 命中的次數(shù)。預取準確性的計算如公式（1）所示。

IS 主要用來判斷性能是否提升，如公式（2）所示，IPCcurrent是當前間隔中獲得的IPC，IPCprevious是在上一個間隔中獲得的IPC。

判斷程序是否友好的具體流程，如圖2 所示。首先，判斷預取是否打開（即預取的激進程度大于0），若預取并未打開，則認為預取不友好；若預取打開，則判斷當前預取是否帶來性能提升，若能帶來性能提升，則當前程序為預取友好。反之，當前程序預取不友好。

圖2 預取友好性程序檢測流程Fig.2 Prefetch－friendly application detection process

2.2.2 檢測非內(nèi)存密集型程序

非內(nèi)存密集型程序是指該類程序在整個運行過程中，發(fā)出的訪存指令明顯少于其它程序。如果處理器的訪存指令發(fā)生了緩存未命中時，必然會對下一級內(nèi)存結(jié)構(gòu)發(fā)出進一步的訪問請求，所以可以依據(jù)每1 000 條指令的緩存未命中數(shù)（Misses per 1K Instructions，簡稱MPKI）這一指標用來計算該程序有多少訪存指令需要訪問下一級內(nèi)存結(jié)構(gòu)，從而判斷該程序是否為非內(nèi)存密集型程序。在每個間隔的結(jié)束，CPAP 判斷當前核心上運行程序的MPKI 是否小于預先設(shè)定的閾值（TMPKI），若小于則將該程序設(shè)置為非內(nèi)存密集型程序；反之，則設(shè)置為內(nèi)存密集型程序。當前間隔檢測的結(jié)果用于下一個間隔的運行控制和資源分配。

2.3 后端：自適應調(diào)整機制

2.3.1 調(diào)整預取的激進程度

預取的激進程度是決定預取技術(shù)是否能帶來性能提升的一個重要原因，預取的激進程度主要表現(xiàn)為預取距離（Prefetch Distance）和預取度（Prefetch Degree）2 方面。預取的激進程度越大，預取距離和預取度的值越大。表1 給出了預取器的4 種不同的預取激進程度配置，其中OFF 代表關(guān)閉預取。

表1 預取器激進程度Tab.1 Prefetcher aggressiveness

預取準確性是指預取器預測程序，即將訪問的內(nèi)存地址的準確程度的度量，對預取性能具有巨大影響，CPAP 主要通過預取的準確性來決定預取的激進程度。在間隔結(jié)束時，CPAP 會計算出預取的準確性，若準確性高于閾值，則在下一個間隔運行時提升預取的激進程度；反之，若低于閾值，則降低預取的激進程度。在本文中，步幅預取器的初始激進程度設(shè)為2。

CPAP 還明確了何時打開預取，如何處理非內(nèi)存密集型程序。

（1）若預取器處于關(guān)閉狀態(tài)（OFF），但是性能卻依舊處于下降趨勢，這很可能是因為內(nèi)存訪問延遲過大而導致的性能下降，則應打開預取，避免性能進一步損失；

（2）非內(nèi)存密集型程序發(fā)出的訪存請求少，局部性不強，難以準確預測。所以非內(nèi)存密集型程序的準確性閾值要高于其它程序，盡量減少非內(nèi)存密集型程序長期配置過高的預取激進程度。同時，非內(nèi)存密集型程序的最大預取激進程度不能超過“中等”配置。通過這2 項限制條件，可以有效的控制非內(nèi)存密集型程序的預取激進程度，使得其既可以獲得預取帶來的性能提升，又可以避免對其它應用程序的干擾，保證其它應用程序可以保持應有的性能。

2.3.2 調(diào)整緩存分區(qū)

非內(nèi)存密集型程序發(fā)出的訪存請求較少，對路數(shù)（way）的需求自然不高，較小的路數(shù)就可以保證性能。同時，預取友好的程序最多只需2－way 就可以達到其最優(yōu)性能的90%，因此CPAP 將非內(nèi)存密集型程序放入一個較小的分區(qū)中，將預取友好型程序放入另外一個分區(qū)中，在保證性能的同時，避免相互干擾。

CPAP 的調(diào)整緩存分區(qū)根據(jù)前端收集的信息，首先，判斷多核系統(tǒng)中是否有非內(nèi)存密集型程序，其次，再考慮是否存在預取友好程序，最后，在圖3 中選擇最合適的緩存分區(qū)方式，以此來減少其它程序?qū)Ψ莾?nèi)存密集型程序的影響。

圖3 緩存分區(qū)方式Fig.3 Cache partitioning

3 實驗及結(jié)果分析

3.1 實驗方法

本文使用ChampSim［19］仿真片上多核處理器系統(tǒng)對CPAP 機制進行評估。使用的基準硬件預取器是步幅預取器，基準測試程序是SPEC CPU 2017。表2 給出了仿真的多核處理器系統(tǒng)的核心參數(shù)。因為本文所研究的問題主要關(guān)注片上共享資源分配的問題，為了避免L1 和L2 的預取請求對LLC 預取策略產(chǎn)生干擾，本文的預取只發(fā)生在LLC 與主存之間。

表2 仿真參數(shù)Tab.2 Simulation parameters

CPAP 方案的閾值設(shè)置，表3 提供了用于實施CPAP 機制的閾值。本文對所有的基準測試程序，基于5 種不同的參數(shù)組合，分別運行了1 000次，就整體而言，表3 的配置可以帶來最佳的性能提升。其中，TnAcc表示的非內(nèi)存密集型程序的準確性閾值；TAcc表示其它經(jīng)程序的準確性閾值；TIS表示IS的閾值；TMPKI表示MPKI的閾值。

表3 CPAP 閾值Tab.3 CPAP threshold

3.2 動態(tài)調(diào)整預取激進程度

首先，本文評估了CPAP 機制的動態(tài)調(diào)整預取器激進程度的性能，與不包含動態(tài)反饋的3 種傳統(tǒng)配置進行比較：無預取，保守預取和激進預取。圖4顯示了20 種基準測試程序在4 種預取配置下的IPC 性能變化。動態(tài)調(diào)整預取器的激進程度可在所有配置中提供最佳的平均性能。整體上看，使用動態(tài)地調(diào)整預取器的激進程度，與“激進”配置相比，平均IPC 提高了6.2%，與不預取相比，IPC 提高了15%。幾乎在所有基準測試中，動態(tài)調(diào)整預取激進程度的性能都非常接近每個基準測試性能最佳的傳統(tǒng)預取器配置所實現(xiàn)的性能。因此，該動態(tài)機制能夠基于每個基準檢測，并為步幅預取器采用最佳性能的激進程度。

如圖4 所示，動態(tài)調(diào)整預取激進程度幾乎完全消除了由于激進的預取而導致的非內(nèi)存密集型測試程序性能大幅下降。在3 種傳統(tǒng)配置中，激進的預取器配置提供了整體最佳的平均性能，但對于x264，deepsjeng等非內(nèi)存密集型程序而言，激進的預取會大大降低性能，與不預取相比，激進的預取使非內(nèi)存密集型測試程序性能平均損失了10%。因為傳統(tǒng)的激進預取忽視了非內(nèi)存密集型程序發(fā)出的請求少，局部性不強的特性，盲目的使用激進的預取配置，導致內(nèi)存結(jié)構(gòu)污染，性能下降；相反，動態(tài)調(diào)整預取激進程度對非內(nèi)存密集型的預取控制更加嚴格，使非內(nèi)存密集型程序性能平均提高了56%。

圖4 基于分類的自適應調(diào)整激進程度Fig.4 Adaptive adjustment of aggressiveness based on classification

3.3 動態(tài)調(diào)整緩存分區(qū)

為了更直觀評估CPAP 機制的動態(tài)調(diào)整緩存分區(qū)的性能，將CPAP 的性能與3 種靜態(tài)分區(qū)策略進行比較：

（1）不預取且不分區(qū)；

（2）保守預取且基本分區(qū)（如圖3（b）所示）；

（3）保守預取且不分區(qū)（如圖3（d）所示）。

圖5 顯示了20 種基準測試程序在4 種緩存分區(qū)策略下IPC 的性能變化。整體上看，與不預取且不分區(qū)相比，基本分區(qū)方式使IPC 僅上升了1%，不分區(qū)方式使IPC 上升了7%?；痉謪^(qū)方式雖然可以緩解非內(nèi)存密集型程序受到其它經(jīng)程序干擾，但整體的性能提升幾乎可以忽略不計，這是因為當CMP 中沒有非內(nèi)存密集型程序時，基本分區(qū)中Non－intensive 部分不可使用，使得有效的LLC 空間減少，導致LLC 爭用更加嚴重，cam4 和roms等內(nèi)存密集型程序受到的影響最為嚴重。

圖5 基于分類的自適應調(diào)整緩存分區(qū)Fig.5 Adaptive adjustment of cache partition based on classification

CPAP 可以比任何靜態(tài)分區(qū)策略提供更高的性能。整體上看，與基本分區(qū)相比，CPAP 實現(xiàn)了16.5%的性能提高；與不分區(qū)相比，CPAP 的性能提高了9.3%，CPAP 幾乎為每個基準測試提供了最佳靜態(tài)分區(qū)策略的性能。對于非內(nèi)存密集型程序，CPAP 選擇最優(yōu)的分區(qū)策略（即基本分區(qū)），大大減少其它經(jīng)程序?qū)Ψ莾?nèi)存密集型程序的干擾，使其IPC 提高了61%（與不預取相比）。因此，運行時通過對應用程序的分類來動態(tài)調(diào)整分區(qū)策略，可以選擇出基于步幅預取器的性能最佳的分區(qū)方案。

3.4 合并：動態(tài)調(diào)整預取控制和緩存分區(qū)

本節(jié)研究了CPAP 機制動態(tài)調(diào)整預取程序的激進程度和緩存分區(qū)的效果。圖6 顯示CPAP 與其3種機制的IPC 性能比較，從左到右分別是：

圖6 CPAP 機制的性能評估Fig.6 Performance evaluation of CPAP

（1）不預??；

（2）保守預取且基本分區(qū)；

（3）動態(tài)調(diào)整預取激進程度；

（4）動態(tài)調(diào)整預取激進程度和緩存分區(qū)（CPAP）。

整體上看，CPAP 可提供最佳性能，與不預取相比，可將IPC 平均提高17.8%，此性能提升要大于僅動態(tài)調(diào)整預取激進程度或最優(yōu)的靜態(tài)緩存分區(qū)策略所提供的性能提升。因此，動態(tài)調(diào)整預取器行為（預取激進程度和緩存分區(qū)策略）的2 個方面都可以提供互補的性能優(yōu)勢。

對于一些內(nèi)存密集型程序，如omnetpp，對LLC有效空間大小變化不敏感，CPAP 可獲得最佳性能提升。但對于大多數(shù)內(nèi)存密集型程序，會因為LLC有效空間減少，導致性能明顯下降，如cam4，但CPAP 可以通過動態(tài)調(diào)整分區(qū)策略，緩解這一問題，使性能得到明顯提升，僅略低于動態(tài)調(diào)整預取激進程度，約1%。

對于非內(nèi)存密集型程序，CPAP 不僅減少了其它程序?qū)ζ涓蓴_，而且?guī)缀跬耆擞捎诩みM預取而導致的性能損失，如exchange2，相比于動態(tài)調(diào)整激進程度，CPAP 提升了6%。

4 結(jié)束語

在多核處理器中，硬件預取在掩藏內(nèi)存延遲的同時，也會在內(nèi)存系統(tǒng)中產(chǎn)生過多的流量和爭用，增加核間干擾。其中，非內(nèi)存密集型程序受到的來自預取的干擾十分嚴重。首先，由于其在運行期間發(fā)出內(nèi)存請求指令少，局部性弱，直接給予過于激進的預取配置，會將潛在有用的數(shù)據(jù)擠出LLC，增加緩存污染；其次，其它經(jīng)預取友好的程序也會將非內(nèi)存密集型程序擠出LLC，增大其內(nèi)存訪問延遲。

為了既能保證預取所帶來的的性能優(yōu)勢，又能消除預取給非內(nèi)存密集型程序帶來性能下降，本文提出了CPAP 機制，一種基于分類的預取感知緩存分區(qū)機制，主要通過監(jiān)視應用程序的預?。彺嫘袨椋詣討B(tài)和協(xié)調(diào)的方式管理硬件預取器和LLC 分區(qū)方式。實驗結(jié)果表明，使用緩存分區(qū)來隔離具有不同預取行為的應用程序，并結(jié)合預取限制，可以有效的減少預取器引起的核間干擾，以最大程度地提高系統(tǒng)性能。