苑風(fēng)凱+季振洲

摘要： 關(guān)鍵詞： 中圖分類號(hào)： 文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 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可以提供諸多優(yōu)勢(shì)：更小的Cache訪問延遲、天然的性能隔離性、更好的可擴(kuò)展性以及功耗優(yōu)化簡易性。然而，私有LLC剔除了Cache容量共享的能力，擁有閑置LLC資源的處理器核無法向LLC資源緊缺的處理器核提供未被充分利用的Cache容量，因而導(dǎo)致更多片外缺失，影響了系統(tǒng)性能。協(xié)作緩存[1]（Cooperative Caching，CC）機(jī)制允許本地LLC驅(qū)逐的犧牲塊通過溢出（Spill）操作放置到另一個(gè)處理器核可能擁有空閑Cache容量的遠(yuǎn)程LLC上，達(dá)到共享片上LLC資源的目的。

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

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

1重用位置分布

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

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

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

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

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

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

2RAPCC機(jī)制的實(shí)現(xiàn)算法

基于上述對(duì)RPD的分類，RAPCC機(jī)制在運(yùn)行時(shí)根據(jù)L2的RPD所表達(dá)的重用性和抗干擾性預(yù)期動(dòng)態(tài)地調(diào)整L2的接受溢出角色，具有較強(qiáng)的可行性，容易實(shí)現(xiàn)。本文提供運(yùn)行時(shí)易實(shí)現(xiàn)的RPD類型識(shí)別算法，研究可得運(yùn)行內(nèi)容如下。

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

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

基準(zhǔn)系統(tǒng)的實(shí)驗(yàn)結(jié)果未能出現(xiàn)在圖5中，因?yàn)锳SCC機(jī)制將所有L2組（Set）的接收溢出角色均決策為溢出者，導(dǎo)致整體運(yùn)行過程中沒有發(fā)生任何的溢出操作，因此ASCC的性能表現(xiàn)完全等同于基準(zhǔn)系統(tǒng)。在圖5的HPKI部分，本地命中和遠(yuǎn)程命中分別使用不同的顏色進(jìn)行區(qū)分。所有機(jī)制均將omnetpp.s判斷為溢出者，RAPCC在HPKI方面的性能表現(xiàn)優(yōu)于DSR和CBS機(jī)制，得益于其旁路機(jī)制增強(qiáng)了運(yùn)行l(wèi)ibquantum.r的L2作為接收者的接納能力。CC系統(tǒng)要求omnetpp.s同時(shí)作為接收者，雖然貢獻(xiàn)了可觀的遠(yuǎn)程命中次數(shù)，CC機(jī)制下運(yùn)行omnetpp.s的處理器核未能獲得應(yīng)有的IPC提升，因?yàn)榻邮胀鈦硪绯鲂性斐傻母蓴_減少了其遠(yuǎn)程命中次數(shù)，如圖4中的omnetpp.si所示。Hmmer.e在RAPCC系統(tǒng)中被給予接收溢出角色EITHER，既作為接收者同時(shí)又作為溢出者，在圖5中獲得了最多的遠(yuǎn)程命中次數(shù)，同時(shí)在表1中貢獻(xiàn)了256次遠(yuǎn)程命中。DSR將hmmer.e判斷為接收者，CBS則將其判斷為溢出者，結(jié)果，DSR系統(tǒng)未能使運(yùn)行hmmer.e的處理器核獲得HPKI提升，而CBS在IPC方面的性能表現(xiàn)僅與ASCC系統(tǒng)持平。Soplex.n在RAPCC系統(tǒng)中被給予接收溢出角色NEITHER，既不作為接收者也不作為溢出者，保護(hù)了本地命中的次數(shù)未受外來溢出行干擾的影響。DSR和CBS將soplex.n判斷為接收者，結(jié)果在HPKI方面的性能表現(xiàn)尚不如CC，因?yàn)槎卟辉试Ssoplex.n作為溢出者，相比CC機(jī)制錯(cuò)過了遠(yuǎn)程命中的補(bǔ)救機(jī)會(huì)。RAPCC與ASCC系統(tǒng)相同，運(yùn)行soplex.n的處理器核在IPC方面獲得最優(yōu)的性能表現(xiàn)。除ASCC外的所有機(jī)制均判斷l(xiāng)ibquantum.r為接收者。如表1中l(wèi)ibquantum.r行，RAPCC的旁路機(jī)制幫助libquantum.r貢獻(xiàn)了最多的遠(yuǎn)程命中次數(shù)762。此外，表1中CC貢獻(xiàn)了最多的遠(yuǎn)程命中次數(shù)3 251，然而，受到損失的本地命中次數(shù)導(dǎo)致CC系統(tǒng)最差的IPC性能表現(xiàn)。整體上，RAPCC在HPKI方面優(yōu)于CC、DSR、CBS以及ASCC機(jī)制分別達(dá)38%、35%、39%和8%，在IPC方面優(yōu)于CC、DSR、CBS以及ASCC分別已達(dá)17%、11%、13%和3%。

4結(jié)束語

本文借助重用位置分布（RPD）與重用性和抗干擾性預(yù)期相關(guān)聯(lián)，提出重用性和抗干擾性可預(yù)測(cè)的協(xié)作緩存（RAPCC）機(jī)制，采用運(yùn)行時(shí)的RPD類型識(shí)別算法，監(jiān)控周期性的RPD并動(dòng)態(tài)地調(diào)整LLC的接受溢出角色，同時(shí)也實(shí)際增強(qiáng)了私有LLC的Cache容量共享能力。實(shí)驗(yàn)結(jié)果表明，RAPCC在HPKI和IPC方面均超越了CC、DSR、CBS和ASCC機(jī)制，具備解決復(fù)雜私有LLC資源共享難題的能力，進(jìn)一步增強(qiáng)了協(xié)作緩存機(jī)制的Cache共享效率。

參考文獻(xiàn)：

[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