方 娟 李成艷 王 帥 姚治成

?

一種基于頻率的多核共享Cache替換算法

方 娟*李成艷 王 帥 姚治成

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 北京 100124)

LRU替換算法在單核處理器中得到了廣泛應(yīng)用，而多核環(huán)境大都采用多核共享最后一級(jí)Cache(LLC)的策略，隨著LLC容量和相聯(lián)度的增加以及多核應(yīng)用的工作集增大，LRU替換算法和理論最優(yōu)替換算法之間的差距越來越大。該文提出了一種平均劃分下基于頻率的多核共享Cache替換算法(ALRU-F)。該算法將當(dāng)前所需要的部分工作集保留在Cache內(nèi)，逐出無(wú)用塊，同時(shí)還提出了塊粒度動(dòng)態(tài)劃分下基于頻率的替換算法(BLRU-F)。該文提出的ALRU-F算法相比傳統(tǒng)的LRU算法缺失率降低了26.59%, CPU每一時(shí)鐘周期內(nèi)所執(zhí)行的指令數(shù)IPC(Instruction Per Clock)則提升了13.59%。在此基礎(chǔ)上提出的塊粒度動(dòng)態(tài)劃分下，基于頻率的BLUR-F算法相比較傳統(tǒng)的LRU算法性能提高更大，缺失率降低了33.72%，而IPC 則提升了16.59%。提出的兩種算法在性能提升的同時(shí)，并沒有明顯地增加能耗。

多核處理器；共享Cache；劃分；替換算法

1 引言

隨著制造工藝的發(fā)展和體系結(jié)構(gòu)的進(jìn)步，單核環(huán)境已經(jīng)無(wú)法滿足人們對(duì)高性能計(jì)算的追求，片上多核(Chip Multi-Processor, CMP)已成為主流發(fā)展趨勢(shì)。目前絕大多數(shù)的主流CMP處理器都使用私有一級(jí)(或一級(jí)和二級(jí))Cache，共享二級(jí)(或三級(jí)) Cache的片上存儲(chǔ)結(jié)構(gòu)來提供快速的資源訪問[1]。通過共享最后一級(jí)Cache結(jié)構(gòu)，最大限度地提高了資源利用率，降低訪問開銷。有效地管理最后一級(jí)Cache將會(huì)提高各個(gè)核的利用率，同時(shí)提高各個(gè)核之間的公平性[2]。

LRU替換算法及其改進(jìn)算法一直是單核處理器下的默認(rèn)標(biāo)準(zhǔn)替換算法，該算法與其它算法相比能更好地提高命中率。但是最近的研究顯示，多核系統(tǒng)中LLC呈現(xiàn)出更大容量及更高相聯(lián)度的發(fā)展趨勢(shì)，這使得LRU替換算法和理論最優(yōu)替換算法之間的差距越來越大，尤其是Cache缺失次數(shù)嚴(yán)重增加[3, 4]。但是在多核條件下，LRU并沒有將各個(gè)核之間的相互干擾以及各個(gè)核訪問Cache的訪問頻率信息考慮在內(nèi)[5]，這使得多核下的Cache利用率越來越低。

針對(duì)LRU不適應(yīng)多核環(huán)境的問題，學(xué)者們提出了很多改進(jìn)策略，主要分為3個(gè)部分：路粒度的Cache劃分[6,7]，動(dòng)態(tài)插入推舉策略[8]，以及改進(jìn)的替換算法[9,10]。其中大部分研究集中體現(xiàn)在以下3個(gè)環(huán)節(jié)：信息的收集，策略的選取以及策略的實(shí)施。信息收集給出提高性能的關(guān)鍵突破點(diǎn)，策略的選取通過收集的信息給出提高性能方法，最后給出實(shí)施方案，通過實(shí)驗(yàn)驗(yàn)證策略的有效性。

本文主要探討如何將Cache劃分，Cache插入推舉和Cache訪問頻率信息有效地結(jié)合起來，綜合考慮各個(gè)方面去獲得更好的性能提升。為了充分考慮各個(gè)核的訪問模式差異，本文提出了基于頻率的多核共享Cache替換算法ALRU-F；并在此基礎(chǔ)上提出了塊粒度動(dòng)態(tài)劃分下基于頻率的替換算法BLRU-F。

2 平均劃分下的基于頻率的ALRU-F替換算法

2.1 算法評(píng)估模型

多核處理器的產(chǎn)生是人們追求高性能的最終結(jié)果，其性能可由式(1)得出，因此提高處理器性能可以從兩方面出發(fā)，一是提高主頻，另一個(gè)是提高CPU每一時(shí)鐘周期內(nèi)所執(zhí)行的指令數(shù)IPC (Instruction Per Clock)。

2.2 Cache劃分策略

本文采用平均劃分策略，即將Cache路平均分劃分給每個(gè)核，保證每個(gè)核擁有屬于自己的Cache路空間。

2.3 插入推舉策略

在LRU替換算法中，Cache缺失時(shí)，選擇最近最久未使用的Cache塊逐出。由于一級(jí)Cache的過濾，0重復(fù)利用塊所占的比例很大，幾乎可以達(dá)到50%[11]，再加上相聯(lián)度的提高，死時(shí)間會(huì)越來越長(zhǎng)，嚴(yán)重影響了Cache空間的有效利用率。在ALRU-F中，使用插入/推舉策略去平衡無(wú)用塊長(zhǎng)期占用Cache空間這一問題。如圖1所示，Cache含有16列，邏輯上從左到右優(yōu)先級(jí)逐漸降低。本文算法中，Cache塊的優(yōu)先級(jí)就是訪問的順序。

圖1(a), 1(b)為傳統(tǒng)LRU和學(xué)者提出的SIP (Speculative Insertion Policy)的逐出策略。圖1(c)假設(shè)O為綜合考慮各種因素選出的逐出塊。其中是綜合考慮LRU信息以及Cache訪問信息提出的候選列數(shù)。越大考慮的LRU信息越少，為0，則相當(dāng)于LRU替換算法。

2.4 基于訪問頻率的策略

文獻(xiàn)[11]提出，訪問頻率也是Cache訪問的重要參考信息，因此將Cache訪問頻率信息考慮在內(nèi)，通過一個(gè)計(jì)數(shù)器來記錄每個(gè)Cache塊的訪問頻率信息，Cache塊每次被訪問相應(yīng)的計(jì)數(shù)器進(jìn)行自增操作。針對(duì)每一組維護(hù)個(gè)候選塊，在進(jìn)行Cache替換時(shí)，將從個(gè)候選塊中進(jìn)行選擇。

2.5 ALRU-F替換算法

綜合以上介紹的基于訪問頻率的策略，基于Cache劃分的策略以及插入推舉策略，提出多核Cache平均劃分下基于頻率的Cache替換算法ALRU-F流程如下：

圖1 插入策略對(duì)比

(1)初始化

(b)當(dāng)處理器核core發(fā)出一個(gè)L2 Cache的訪問請(qǐng)求時(shí)，根據(jù)所要訪問的地址確定地址所映射的Cache組和core的列劃分信息表確定屬于core的Cache存儲(chǔ)單元集合，并在存儲(chǔ)單元集合中判斷是否命中：如果命中，存取Cache存儲(chǔ)單元，命中單元即為請(qǐng)求所要訪問的單元，執(zhí)行步驟(3)；否則執(zhí)行步驟(2)；

(2)Cache替換

(a)根據(jù)Cache組對(duì)應(yīng)的候選路信息M，核core的列劃分信息選擇逐出單元：

如果候選路信息M對(duì)應(yīng)的存儲(chǔ)單元存在屬于core的存儲(chǔ)單元C，則C為逐出單元，繼續(xù)執(zhí)行步驟(2)(b)；否則選擇候選路信息M中訪問頻率最低的存儲(chǔ)單元作為逐出單元；

(b)將要存取的數(shù)據(jù)塊插入到Cache組中優(yōu)先級(jí)為的存儲(chǔ)單元中，更新的訪問頻率信息，執(zhí)行步驟(4)；

(3) 提升優(yōu)先級(jí)

(a)如果命中的存儲(chǔ)單元屬于候選路M，則將命中的存儲(chǔ)單元的優(yōu)先級(jí)提升一級(jí)；

(b)將命中的Cache存儲(chǔ)單元的優(yōu)先級(jí)提升為最近訪問的列的優(yōu)先級(jí)；

(4)回溯階段：程序運(yùn)行時(shí)間后，如果程序沒有結(jié)束，清除所有Cache存儲(chǔ)單元訪問頻率信息表，并返回步驟(1)(b)；否則，輸出運(yùn)行結(jié)果，分析缺失率、功耗以及整體IPC。

3 塊粒度Cache劃分下基于頻率的BLRU-F算法

ALRU-F算法是基于Cache列的平均劃分，粒度較大，本文在此基礎(chǔ)上提出基于Cache塊的劃分BLRU-F，更細(xì)粒度的劃分，旨在提高各個(gè)核對(duì)共享Cache的利用率，盡可能地降低缺失率，提高性能。

圖2 BLFU-F算法訪問存儲(chǔ)過程流程圖

當(dāng)出現(xiàn)Cache缺失時(shí)，若該核的Cache列未命中，則判斷核core是否竊取了其它核的列；如果核core竊取了核core的列，根據(jù)路竊取信息表確定被竊取的核core的存儲(chǔ)單元對(duì)應(yīng)的組號(hào)集合；若屬于，搜索組中核core對(duì)應(yīng)的存儲(chǔ)單元；判斷是否命中；若命中，存取Cache單元，繼續(xù)步驟(4)；若不屬于并且未命中，執(zhí)行步驟(2)；若核core未竊取其它核的列，執(zhí)行步驟(2)；

圖3 BLFU-F算法Cache缺失流程圖

在進(jìn)行逐出單元的選擇時(shí)，判斷是否有核core竊取了核core的存儲(chǔ)單元；如果存在core竊取了核core的存儲(chǔ)單元，且竊取的是組中的Cache存儲(chǔ)單元，將組中所對(duì)應(yīng)的存儲(chǔ)單元選為逐出單元，更新路竊取信息表，執(zhí)行步驟(2)(b)；

如果竊取的不是組中的Cache，或不存在core竊取核core的存儲(chǔ)單元，那么如果候選路信息M對(duì)應(yīng)的存儲(chǔ)單元屬于core的存儲(chǔ)單元C，則C為逐出單元，繼續(xù)執(zhí)行步驟(2)(b)；否則根據(jù)路竊取信息表，選擇候選路信息M中訪問頻率最低的單元逐出，更新路竊取信息，執(zhí)行步驟(2)(b)；其余步驟與FLRU-A相同。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用的系統(tǒng)模擬器為Virtutech Simics，它是一個(gè)靈活的全系統(tǒng)模擬器，可以模擬多種目標(biāo)平臺(tái)的體系結(jié)構(gòu)。GEMS(General Execution-driven Multi-processor Simulator)是Virtutech Simics的一組模塊，它使Virtutech Simics能更詳細(xì)地模擬多處理器系統(tǒng)。實(shí)驗(yàn)選取了4核，8核，16核，并分別選取了8路，16路，32路，64路進(jìn)行了實(shí)驗(yàn)。表1是實(shí)驗(yàn)環(huán)境配置。

表1 實(shí)驗(yàn)環(huán)境配置

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)共模擬了3個(gè)替換策略：ALRU-F, BLRU- F和LRU。選取了SpecOMP[12]的wupwise_m, swim_m, grid_m, applu_m, equake_m, apsi_m, fma3d_m, art_m作為測(cè)試程序，分別對(duì)比了各個(gè)算法在性能、功耗和二級(jí)Cache缺失率3方面的效果。

圖4是4核下缺失率，IPC和功耗變化對(duì)比圖。圖4(a)給出了缺失率對(duì)比，由圖得出，ALRU與LRU相比缺失率降低了9.52%。

圖5是8核下缺失率，IPC和功耗變化對(duì)比圖。從圖5(a) 8核下缺失率對(duì)比可得，整體缺失次數(shù)有所降低，ALRU-F與LRU相比平均價(jià)低了14.04%；BLRU-F與LRU相比平均降低了26.41%；圖5(b)是8核下IPC對(duì)比圖，可得出IPC提升7.81%, ALRU-F與LRU相比平均提升了12.5%。

圖6是16核下缺失率，IPC和功耗情況變化對(duì)比圖。如圖6(a)可以得出，BLRU-F與ALRU-F相比缺失率平均降低了20.32%，與LRU相比缺失率降低了32.88%。圖6(b)給出了16核下IPC對(duì)比，BLRU-F相比ALRU-F相比較IPC平均提升了3.26%，與LRU相比IPC平均提升了14.46%；圖6(c)展示的是16核下功耗對(duì)比圖，由圖6看出，功耗基本沒有變化。

本文提出的BLRU-F改進(jìn)了劃分策略，在列劃分的基礎(chǔ)上，根據(jù)多核訪存需求變化以塊為單位進(jìn)行重分配，并且在Cache替換時(shí)通過逐出的方式回收Cache塊資源。這種基于列劃分的塊粒度的動(dòng)態(tài)重分配，既節(jié)省了開銷又達(dá)到了細(xì)粒度的動(dòng)態(tài)劃分。

5 LLC共享時(shí)的算法效率分析

本文提出的兩種算法都采用了相應(yīng)的劃分策略，這主要是針對(duì)多核競(jìng)爭(zhēng)訪問最后一級(jí)共享Cache的情形，將Cache空間進(jìn)行劃分，消除競(jìng)爭(zhēng)帶來的性能降低問題。尤其是第2種算法BLRU-F采用了更細(xì)粒度的劃分，同時(shí)巧妙利用塊竊取方法來平衡各個(gè)核的訪問差異，使得各個(gè)核更加充分地利用有限的Cache資源。算法都考慮到了Cache路的訪問頻率信息，將該信息與LRU信息相結(jié)合，采用了插入/推舉策略，盡量保留當(dāng)前工作集在Cache空間，消除了多核環(huán)境下Cache工作集大帶來的Cache抖動(dòng)現(xiàn)象，以及研究表明的0重復(fù)利用Cache塊占比相當(dāng)大帶來的Cache空間浪費(fèi)，更加有利于多核環(huán)境下的Cache命中率的提升。

圖4 4核下LRU, ALRU-F和BLRU-F效果對(duì)比圖

圖5 8核下LRU, ALRU-F和BLRU-F效果對(duì)比圖

圖6 16核LRU, ALRU-F和BLRU-F效果對(duì)比圖

6 結(jié)束語(yǔ)

本文綜合考慮Cache劃分，訪問頻率信息以及多核之間的干擾，提出了一個(gè)改進(jìn)的多核共享Cache替換算法。該算法結(jié)合當(dāng)前的研究熱點(diǎn)Cache劃分，將Cache訪問頻率信息作為替換塊選擇的重要參考，同時(shí)將LRU信息作為關(guān)鍵參考信息，采用Cache路插入推舉策略，最終選擇最合適的替換塊進(jìn)行替換。同時(shí)，算法還實(shí)現(xiàn)了塊粒度的動(dòng)態(tài)重分配。實(shí)驗(yàn)結(jié)果表明，這種改進(jìn)的Cache替換算法能夠很好地提高命中率，降低運(yùn)行時(shí)間。下一步工作將考慮兩個(gè)方面，一方面改進(jìn)Cache劃分策略，采取更有效的劃分方案，另一方面將當(dāng)前多核研究的另一個(gè)熱點(diǎn)，Cache路預(yù)測(cè)技術(shù)與當(dāng)前算法相結(jié)合，并進(jìn)行改進(jìn)，以獲得更好的效果。

[1] Hammond L, Nayfeh B A, and Olukotun K. A single-chip multiprocessor[J]., 1997, 30(9): 79-85.

[2] HuangZhi-bin, Zhu Ming-fa, and Xiao Li-min. Analysis of allocation deviation in multi-core shared cache pseudo-partition[C]. Proceedings of 2011 International Conference on Electronic Engineering, Communication and Management, Beijing, China, 2012:463-470.

[3] Mazen Kharbutli and Rami Sheikh. LACS: a locality-aware cost-sensitive cache replacement algorithm[J]., 2013, 6(3): 1-29.

[4] Zhang Xi and Li Chong-min. A cache replacement policy using adaptive insertion and re-reference prediction[C]. International Symposium on Computer Architecture and High Performance Computing, Petrópolis, Brazil, 2010: 95-102.

[5] Ding Shan and Li Yuan-yuan. LRU2-MRU collaborative cache replacement algorithm on multi-core system[C]. Computer Science and Automation Engineering(CASE2012), Zhangjiajie, China, 2012: 395-398.

[6] Huang Zhi-bin, Zhu Ming-fa, and Xiao Li-min. LvtPPP: live-time protected pseudopartitioning of multicore shared caches[J].2013, 24(8): 1622-1632.

[7] Sui Xiu-feng, Wu Jun-min, Chen Guo-liang,.. Augmenting cache partitioning with thread-aware insertion/promotion policies to manage shared caches[C]. Proceedings of the 7th ACM International Conference on Computing Frontiers, Bertinoro, Italy, 2010: 79-80.

[8] Kron J D, Prumo B, and Loh G H. Double-DIP: augmenting DIP with adaptive promotion policies to manage shared L2 caches[C]. Proceedings of the Workshop on Chip Multiprocessor Memory Systems and Interconnects, Beijing, China, 2008: 1-9.

[9] Kharbutli M and Solihin Y. Counter-based cache replacement algorithms[C]. IEEE International Conference on Computer Design, San Jose, USA, 2005: 61-68.

[10] John T and Ademola T. Dynamicly self-adjusting cache replacement algorithm[J]., 2013, 6(1): 25-34.

[11] Qureshi MK and Patt YN. Utility-based cache partitioning: alow-overhead, high-performance, runtime mechanism to partition shared caches[C]．Proceedings of the 39th Annual IEEE/ACM International Symposium on Micro Architecture, Washington DC, USA, 2006: 423-432．

[12] Aslot V,Domeika M J, Eigenmann R,.. SpecOMP: a new benchmark suite for measuring parallel computer performance[C]. WOMPAT’01 Proceedings of the International Workshop on OpenMP Applications and Tools: OpenMP Shared Memory Parallel Programming, London, UK, 2001: 1-10.

方 娟： 女，1973年生，副教授，研究方向?yàn)橛?jì)算機(jī)系統(tǒng)結(jié)構(gòu)、多核計(jì)算.

李成艷： 女，1988年生，碩士生，研究方向?yàn)槎嗪擞?jì)算.

王 帥： 男，1986年生，碩士生，研究方向?yàn)槎嗪擞?jì)算.

姚治成： 男，1989年生，碩士生，研究方向?yàn)槎嗪擞?jì)算.

A Frequency Based Cache Replacement Algorithm with Partition of CMPs

Fang Juan Li Cheng-yan Wang Shuai Yao Zhi-cheng

(,,100124,)

LRU has been widely used in single-core processor, while Chip Multi-Processors (CMP) employ a large Last-Level Cache (LLC) which is shared among the multiple cores. With the increasement of the LLC capacity and associativity, and the grows of working set of multicore’s applications, the performance gap between the LRU and the theoretical optimal replacement algorithms gets wider and wider. This paper proposes an Average partition LRU algorithm based on Frequency (ALRU-F). The algorithm has maintained the working set at Cache and drive out the ignore block. Also, a Cache line stealing strategy is proposed to realize a Block partition LRU replacement algorithm based on Frequency (BLRU-F). The result of experiments shows that comparing to the traditional LRU algorithm, the proposed ALRU-F algorithm reduces the miss rate by 26.59%, and improves the Instruction Per Clock (IPC) by 13.59 % with little change of power consumption. Comparing to the traditional LRU and BLRU-F algorithms, the proposed algorithm reduces the Cache miss rate by 33.72% and improves the IPC by 16.59%.

Chip Multi-Processors (CMP); Shared Cache; Partition; Replacement algorithm

TP393

A

1009-5896(2014)06-1229-06

10.3724/SP.J.1146.2013.01030

方娟 fangjuan@bjut.edu.cn

2013-07-16收到，2013-11-07改回

國(guó)家自然科學(xué)基金(61202076 )和北京市教委科技計(jì)劃面上項(xiàng)目(KM201210005022)資助課題