一種改進的抗干擾性可預測的協作緩存機制

苑風凱+季振洲

摘要： 關鍵詞： 中圖分類號： 文獻標志碼： A文章編號： 2095-2163

Abstract： The Last Level Cache （LLC） in private configurations offers lower access delay and better isolation performance， but extinguishes the ability of sharing underutilized cache resources. Cooperative Caching （CC） provides capacity sharing by spilling a line evicted from one cache （spiller） to another （receiver）. The CC successors took efforts to efficient cache sharing， however no approach had undertook both the reusability of evicted lines for spillers and the anti-interference to the spilled lines for receivers. This paper proposes Reusability and Anti-Interference Predictable Cooperative Caching （RAPCC） to further improve the cache sharing ability of CMPs with private LLCs. RAPCC exploits the Reuse Position Distribution （RPD） to predict the reusability and anti-interference for the determination of a private LLC to be a spiller， receiver， neither， or either （a novel neutral spilling state to both spill and receive）. Experimental results have proven RAPCC performs best in HPKI and IPC among previously proposed CC， DSR， CBS， and ASCC.

0引言

將Last Level Cache（LLC）配置成私有LLC可以提供諸多優勢：更小的Cache訪問延遲、天然的性能隔離性、更好的可擴展性以及功耗優化簡易性。然而，私有LLC剔除了Cache容量共享的能力，擁有閑置LLC資源的處理器核無法向LLC資源緊缺的處理器核提供未被充分利用的Cache容量，因而導致更多片外缺失，影響了系統性能。協作緩存[1]（Cooperative Caching，CC）機制允許本地LLC驅逐的犧牲塊通過溢出（Spill）操作放置到另一個處理器核可能擁有空閑Cache容量的遠程LLC上，達到共享片上LLC資源的目的。

CC機制的缺陷是任意LLC都可作為溢出者，同時任意LLC都需要承擔接受者的義務，沒有考慮到溢出者是否可以通過額外的容量獲益，也沒有考慮到接受者是否可以提供額外的容量而保證自身性能不受影響，削弱了私有LLC結構的性能隔離性優勢。后繼的CC研究試圖解決CC機制的盲目溢出問題，進化出可以動態地調整接收溢出角色的機制：作為溢出者，可以獲知是否有可觀的可能性重用溢出塊；作為接受者，可以獲知是否擁有未利用的容量可供分享，同時不會損害自身的性能。此外，一種中立的接收溢出角色已經被提出，既不作為接收者也不作為溢出者，避免接收者和溢出者中的任何一個角色對性能造成損害。

本文提出重用性和抗干擾性可預測的協作緩存（Reusability and Anti-Interference Predictable Cooperative Caching，RAPCC）機制，進一步增強私有LLC的Cache容量共享能力，利用重用位置分布（Reuse Position Distribution，RPD），借助干擾注入實驗，根據重用性和抗干擾性預期，將RPD劃分為4種類型，采用運行時的RPD類型識別算法，監控周期性的RPD并動態地決定LLC的接受溢出角色。RAPCC提出另一種全新、中立的接受溢出角色，即LLC既可以作為溢出者，同時又可以作為接收者，有助于私有LLC更合理地分配片上存儲資源。此外，RAPCC引入旁路機制，進一步擴展具有特殊RPD的接收者的接納能力。實驗結果表明，RAPCC機制在HPKI和IPC兩方面的性能表現均超越了CC、DSR[2]、CBS[3]以及ASCC[4]機制。

1重用位置分布

本文遵從Tiled多核處理器作為基準架構，每個tile擁有本地的私有L2，且L1和L2為獨占關系，最大限度地利用Cache存儲空間。L1s和L2分別配置為16 KB 4-way和1 MB 8-way。在典型的協作緩存機制研究中，每個Cache塊只有一次溢出的機會，然后在另一個LLC經歷第二次LRU棧行走，直至遠程命中或者被替換并驅逐出片上Cache系統。因此，本文將L2的LRU棧擴展加倍，如圖1所示，利用擴展的LRU棧保存被驅逐Cache行（Line）的物理地址并追蹤重用情況，就像當前已被溢出并獲得第二次機會進行LRU棧行走一樣。

圖1左右兩側的Cache替換操作分解動作解釋了擴展LRU棧的運作方式：左側為驅逐動作，原始棧（Primary）和擴展棧（Expanded）均為滿棧狀態，分別需要選擇LRU位置的Cache行H和P作為犧牲行進行驅逐操作；右側為插入動作，原始棧驅逐H后將新入Cache行插入到MRU位置，擴展棧驅逐P后將原始棧驅逐的H插入MRU位置，模擬H溢出后獲得第二次LRU棧行走機會。圖1中每個LRU棧被劃分為兩個區域，MRU端白色的HIGH區和LRU端灰色的LOW區。本文定義每10 000個已提交的處理器核對L1的訪問請求為一個周期，定義10 000為周期的間隔。在每個周期，記錄每個LRU棧區域的命中次數，對L2的雙棧四區域重用位置分布（Reuse Position Distribution，RPD）進行統計。圖2展示了具有應用程序階段特點的周期性RPD，統計數據通過使用全系統仿真工具GEM5[5]運行SPEC CPU2006測試集獲取。通過觀察可以看出，應用程序的不同而RPD不同，甚至應用程序內的階段不同而RPD改變，如圖2中應用程序bzip2.x、bwaves.x和soplex.x。本文將四個區域的命中次數分別命名為PH、PL、EH和EL。一方面，P數值（PH/L）和E數值（EH/L）分別反映了應用程序對本地和額外L2容量的重視程度。顯然，RPD中較大數值的EH或EL，如圖2中應用程序x.s，確保L2能夠通過溢出高重用性的犧牲行獲益明顯（本文提到的重用性泛指L2中Cache行群體的重用性而非個體重用性）。另一方面，H/L比率可以幫助預測L2作為接收者的抗干擾性。圖3對于重用位置高低不同的Cache行在干擾存與否情況下的LRU棧行走的過程進行描述。endprint

在圖3的中央部分，Cache行Re開啟了從插入位置MRU開始的LRU棧行走過程。左側為高重用位置行走過程的描述，在圖3上部沒有遭遇干擾的情況下，Re經歷重用時間間隔ΔTH后在HIGH區獲得命中，然而，在圖3下部遭遇干擾的情況下，Re經歷相同的ΔTH后，受到外來干擾行IN的推移效應影響，最終在LOW區獲得命中。相對地，右側為低重用位置行走過程的描述，在圖3上部沒有遭遇干擾的情況下，Re經歷重用時間間隔ΔTL后在LOW區獲得命中，然而，在圖3下部遭遇干擾的情況下，Re經歷相同的ΔTL后，本應在LOW區命中卻被外來干擾行推移出LRU棧導致了缺失的發生。考慮到外來干擾行的推移效應，高重用位置的Cache行相比低重用位置的Cache行的抗干擾能力更強。因此，本文提出假說：擁有H明顯占優于L的RPD的L2具有較強的抗干擾性，能夠勝任接收者角色。為了證實此假說的正確性，本文設計了干擾注入實驗，對比干擾行注入前后L2的RPD的變化。圖2中虛線隔出應用程序的干擾注入實驗統計數據被繪制RPD注入前后對比情況如圖4所示。本文提出的假說得到了干擾注入實驗的證明。為了模仿外來溢出塊，本文設計干擾注入器，產生無效的、物理地址不相關的Cache行，以具有代表性的頻度200/周期插入L2作為干擾行。以下根據RPD的分類論述具有各種類型RPD的L2的抗干擾性，RPD共分為如下四類：1）接受者（RECEIVER）。此類RPD沒有E數值而且PH相比PL較大，如圖2中的gromacs.r和bwaves.r。具有此類RPD的L2不能通過額外的Cache容量獲益，同時高比率的高重用位置Cache行保障了對外來溢出塊的干擾免疫性。特殊實例為圖2中的libquantum.r，甚至沒有P數值，擁有天然的、無限制的抗干擾能力。接收者RPD的抗干擾性得到了圖4中的bwaves.ri的證實，并擁有與bawaves.r相同的P總量（PH+PL），即外來干擾行只是將一部分命中從PH推移到PL，未能影響整體性能。

2）NEITHER。此類RPD沒有E數值而且PH與PL相比未能占據主導地位，如圖2中的bzip2.n、tonto.n和soplex.n。圖4中注入后的soplex.ni顯示了此類RPD較差的抗干擾性。干擾行的推移效應驅逐了部分本應貢獻PL命中數的Cache行，這些Cache行被擴展LRU?；厥詹⑥D化為EH，即E_HIGH區域的命中數。缺失的Cache行造成了L2所在處理器核的性能損失，因此，具有此類RPD的L2既不應作為溢出者也不應作為接收者。

3）溢出者（SPILLER）。此類RPD具有E數值而且至少有一個H數值（P/EH）相比同棧的L數值（P/EL）未能占據主導地位，如圖2中的bzip2.s、mcf.s、omnetpp.s和soplex.s。具有此類RPD的L2可以通過額外的Cache容量獲益，卻受制于其H/L比率，不適合作為接收者。不同于P區域（P_HIGH/LOW），E區域（E_HIGH/LOW）的推移效應源于受外來干擾行影響增多的溢出行。圖4中注入后的omnetpp.si的E總量（EH+EL）相比omnetpp.s大幅降低，即增多的溢出行將競爭有限的接收者Cache容量，導致遠程命中的減少造成性能損失。另外，即使新增溢出行能夠得到等價的遠程命中數（從PL轉換為EH），片上遠程取回操作相比本地命中既耗時又耗能，本文傾向于將PL保留在本地而不受外來干擾行的影響。因此，圖2中的bzip2.s因為高比率的PL而不適合作為接收者。

4）EITHER。這是首次被提出的中立類型RPD。此類RPD具有E數值而且所有的H數值相比同棧的L數值均占據主導地位（H/L數值均為0為特殊情況），如圖2中的bwaves.e和hmmer.e。圖4中注入后的hmmer.ei的P和E總量均于hmmer.e相同。具有此類RPD的L2既可以作為溢出者通過額外的Cache容量獲益，同時可以作為接收者貢獻自身的Cache容量而不會影響性能，這歸功于本文發現并利用獨特的RPD。

2RAPCC機制的實現算法

基于上述對RPD的分類，RAPCC機制在運行時根據L2的RPD所表達的重用性和抗干擾性預期動態地調整L2的接受溢出角色，具有較強的可行性，容易實現。本文提供運行時易實現的RPD類型識別算法，研究可得運行內容如下。

每個L2需要添加兩個1-bit的標志位：Spill和Receive，指示L2當前的接收溢出角色。接收溢出狀態的命名采用RPD類型的名稱，如上文程序中符號“※”后的注釋。在本文中，溢出者需要找到接收者才能完成溢出操作，否則待溢出行將被寫回內存。標志位Spill指示L2是否對遭驅逐犧牲行執行溢出操作，Receive則回答溢出者的問詢指示此L2是否可以作為接收者。ThrP、ThrE、ThrPx、ThrEx和RHL均為算法參數。其中，ThrP和ThrE分別定義特定周期間隔下應用程序運行性能具有實質意義的P和E總量（amount）。當判斷L2是否適合作為接收者時，在程序中的邏輯表達式{1}和{2}中，除了安全比率RHL確保H數值相比同棧L數值占據主導地位，Px和Ex數值也要小于閾值ThrPx和ThrEx。圖1和圖3中，極限區域以深灰色在LOW區高亮出來，重用位置落入極限區域的Cache行明顯更容易受到干擾的影響。因此，閾值ThrPx和ThrEx定義了作為接收者所能承受的極限區域風險。

為了加大溢出行的重用可能，本文增強特定接收者（非保護類）的接納能力，如圖2中的libquantum.r，此類接收者不需要任何的防干擾措施，不但不能利用L2的存儲容量，反而不斷地向L2插入無重用性的L1替換行，徒然加速外來溢出行被驅逐的進程。借助獨占的L2配置，本文采用旁路機制，將L1替換行直接寫回至內存，延長外來溢出行的存活時間，增大遠程命中機會。程序中，第二行判斷L2為非保護類接收者之后將標志位Bypass打開，指示直接向內存寫回L1替換行。值得注意的是，盡管直接執行寫回內存操作，但是L1替換行的物理地址仍然被保存在擴展LRU棧中，以監控應用程序新階段的L2命中。另如程序中的第四行所示，當監測到實質性的E總量，標志位Bypass和Receive均被關閉以保護應用程序新階段的運行性能，如行6所示。endprint

3實驗結果與分析

本文使用全系統仿真工具GEM5評估RAPCC機制，對比運行RAPCC機制的系統（RAPCC系統）與CC、DSR、CBS、ASCC以及基準系統在HPKI（Hits per Kilo Instructions）和IPC兩方面的性能表現。基準系統為四核Tile多核處理器，私有、獨占關系的L2。L1和L2使用與本文第一節相同的配置參數。所有系統均采用DP&TB[6-7]協議維護Cache一致性，運行相同的四線程工作負載[8]（Workload）。工作負載由SPEC CPU2006測試集中的四個不同基準測試程序段混合而成，運行四個程序段的L2具有不同的RPD類型，分別為omnetpp.s、hmmer.e、libquantum.r和soplex.n，如圖2和4所示。本文設計此工作負載以模擬運行時復雜的片上Cache資源共享環境，檢驗運行各機制的系統應對復雜局面的挑戰，解決私有LLC容量共享能力的難題。

圖5描述了RAP（CC）系統相比CC、DSR、CBS以及AS（CC）系統在HPKI和IPC兩個方面的性能表現情況，實驗結果分別歸一化到RAPCC和ASCC系統。所有系統均未能影響libquantum.r的性能，因此，運行此程序段線程的處理器核性能表現被從圖5中濾除。Libquantum.r的主要作用是作為接收者貢獻遠程命中，如表1所示。

基準系統的實驗結果未能出現在圖5中，因為ASCC機制將所有L2組（Set）的接收溢出角色均決策為溢出者，導致整體運行過程中沒有發生任何的溢出操作，因此ASCC的性能表現完全等同于基準系統。在圖5的HPKI部分，本地命中和遠程命中分別使用不同的顏色進行區分。所有機制均將omnetpp.s判斷為溢出者，RAPCC在HPKI方面的性能表現優于DSR和CBS機制，得益于其旁路機制增強了運行libquantum.r的L2作為接收者的接納能力。CC系統要求omnetpp.s同時作為接收者，雖然貢獻了可觀的遠程命中次數，CC機制下運行omnetpp.s的處理器核未能獲得應有的IPC提升，因為接收外來溢出行造成的干擾減少了其遠程命中次數，如圖4中的omnetpp.si所示。Hmmer.e在RAPCC系統中被給予接收溢出角色EITHER，既作為接收者同時又作為溢出者，在圖5中獲得了最多的遠程命中次數，同時在表1中貢獻了256次遠程命中。DSR將hmmer.e判斷為接收者，CBS則將其判斷為溢出者，結果，DSR系統未能使運行hmmer.e的處理器核獲得HPKI提升，而CBS在IPC方面的性能表現僅與ASCC系統持平。Soplex.n在RAPCC系統中被給予接收溢出角色NEITHER，既不作為接收者也不作為溢出者，保護了本地命中的次數未受外來溢出行干擾的影響。DSR和CBS將soplex.n判斷為接收者，結果在HPKI方面的性能表現尚不如CC，因為二者不允許soplex.n作為溢出者，相比CC機制錯過了遠程命中的補救機會。RAPCC與ASCC系統相同，運行soplex.n的處理器核在IPC方面獲得最優的性能表現。除ASCC外的所有機制均判斷libquantum.r為接收者。如表1中libquantum.r行，RAPCC的旁路機制幫助libquantum.r貢獻了最多的遠程命中次數762。此外，表1中CC貢獻了最多的遠程命中次數3 251，然而，受到損失的本地命中次數導致CC系統最差的IPC性能表現。整體上，RAPCC在HPKI方面優于CC、DSR、CBS以及ASCC機制分別達38%、35%、39%和8%，在IPC方面優于CC、DSR、CBS以及ASCC分別已達17%、11%、13%和3%。

4結束語

本文借助重用位置分布（RPD）與重用性和抗干擾性預期相關聯，提出重用性和抗干擾性可預測的協作緩存（RAPCC）機制，采用運行時的RPD類型識別算法，監控周期性的RPD并動態地調整LLC的接受溢出角色，同時也實際增強了私有LLC的Cache容量共享能力。實驗結果表明，RAPCC在HPKI和IPC方面均超越了CC、DSR、CBS和ASCC機制，具備解決復雜私有LLC資源共享難題的能力，進一步增強了協作緩存機制的Cache共享效率。

參考文獻：

[1] CHANG Jichuan， SOHI G S. Cooperative caching for chip multiprocessors[C]//International Symposium on Computer Architecture. Boston， Massachusetts：ACM， 2006：264-276.

[2] QURESHI M K. Adaptive spillreceive for robust highperformance caching in CMPs[C]//International Symposium on High PERFORMANCE Computer Architecture. Raleigh， NC：IEEE， 2009：45-54.

[3] JIA Xiaomin， JIANG Jiang， ZHAO Tianlei， et al. Towards online application cache behaviors identification in CMPs[C]//International Conference on High Performance Computing and Communications.Washington， DC， USA：IEEE， 2010：1-8.

[4] ROLN D， FRAGUELA B B， DOALLO R. Adaptive set-granular cooperative caching[C]//International Symposium on High Performance Computer Architecture. Washington， DC， USA：IEEE， 2012：1-12.

[5] BINKERT N， BECKMANN B， BLACK G， et al. The gem5 simulator[J]. ACM SIGARCH Computer Architecture News， 2011， 39（2）： 1-7.

[6] YUAN Fengkai， JI Zhenzhou. DP&TB： A coherence filtering protocol for manycore chip multiprocessors[J]. Journal of Supercomputing， 2013， 66（1）： 249-261.

[7] YUAN Fengkai， JI Zhenzhou， ZHU Suxia. Setgranular regional distributed cooperative caching[J]. IEEE Computer Architecture Letters， 2015， 14（1）： 75-78.

[8] QURESHI M K， PATT Y N. Utilitybased cache partitioning： A lowoverhead， highperformance， runtime mechanism to partition shared caches[C]//International Symposium on Microarchitecture. Orlando， Florida， USA：ACM， 2006：423-432.endprint