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

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

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

1.1 緩存分區(qū)

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

1.2 全局預(yù)取控制

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

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

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

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

2.1 CPAP 整體架構(gòu)

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

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

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

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

2.2.1 檢測預(yù)取友好型程序

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

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

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

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

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

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

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

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

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

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

2.3.1 調(diào)整預(yù)取的激進(jìn)程度

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

表1 預(yù)取器激進(jìn)程度Tab.1 Prefetcher aggressiveness

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

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

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

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

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

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

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

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

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

3.1 實驗方法

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

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

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

表3 CPAP 閾值Tab.3 CPAP threshold

3.2 動態(tài)調(diào)整預(yù)取激進(jìn)程度

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

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

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

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

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

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

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

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

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

圖5 基于分類的自適應(yīng)調(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 幾乎為每個基準(zhǔn)測試提供了最佳靜態(tài)分區(qū)策略的性能。對于非內(nèi)存密集型程序，CPAP 選擇最優(yōu)的分區(qū)策略（即基本分區(qū)），大大減少其它經(jīng)程序?qū)Ψ莾?nèi)存密集型程序的干擾，使其IPC 提高了61%（與不預(yù)取相比）。因此，運(yùn)行時通過對應(yīng)用程序的分類來動態(tài)調(diào)整分區(qū)策略，可以選擇出基于步幅預(yù)取器的性能最佳的分區(qū)方案。

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

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

圖6 CPAP 機(jī)制的性能評估Fig.6 Performance evaluation of CPAP

（1）不預(yù)?。?/p>

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

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

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

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

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

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

4 結(jié)束語

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

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