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

方 娟 李成艷 王 帥 姚治成

?

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

方 娟*李成艷 王 帥 姚治成

(北京工業大學計算機學院 北京 100124)

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

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

1 引言

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

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

針對LRU不適應多核環境的問題，學者們提出了很多改進策略，主要分為3個部分：路粒度的Cache劃分[6,7]，動態插入推舉策略[8]，以及改進的替換算法[9,10]。其中大部分研究集中體現在以下3個環節：信息的收集，策略的選取以及策略的實施。信息收集給出提高性能的關鍵突破點，策略的選取通過收集的信息給出提高性能方法，最后給出實施方案，通過實驗驗證策略的有效性。

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

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

2.1 算法評估模型

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

2.2 Cache劃分策略

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

2.3 插入推舉策略

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

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

2.4 基于訪問頻率的策略

文獻[11]提出，訪問頻率也是Cache訪問的重要參考信息，因此將Cache訪問頻率信息考慮在內，通過一個計數器來記錄每個Cache塊的訪問頻率信息，Cache塊每次被訪問相應的計數器進行自增操作。針對每一組維護個候選塊，在進行Cache替換時，將從個候選塊中進行選擇。

2.5 ALRU-F替換算法

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

圖1 插入策略對比

(1)初始化

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

(2)Cache替換

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

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

(b)將要存取的數據塊插入到Cache組中優先級為的存儲單元中，更新的訪問頻率信息，執行步驟(4)；

(3) 提升優先級

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

(b)將命中的Cache存儲單元的優先級提升為最近訪問的列的優先級；

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

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

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

圖2 BLFU-F算法訪問存儲過程流程圖

當出現Cache缺失時，若該核的Cache列未命中，則判斷核core是否竊取了其它核的列；如果核core竊取了核core的列，根據路竊取信息表確定被竊取的核core的存儲單元對應的組號集合；若屬于，搜索組中核core對應的存儲單元；判斷是否命中；若命中，存取Cache單元，繼續步驟(4)；若不屬于并且未命中，執行步驟(2)；若核core未竊取其它核的列，執行步驟(2)；

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

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

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

4 實驗結果及分析

4.1 實驗環境

實驗使用的系統模擬器為Virtutech Simics，它是一個靈活的全系統模擬器，可以模擬多種目標平臺的體系結構。GEMS(General Execution-driven Multi-processor Simulator)是Virtutech Simics的一組模塊，它使Virtutech Simics能更詳細地模擬多處理器系統。實驗選取了4核，8核，16核，并分別選取了8路，16路，32路，64路進行了實驗。表1是實驗環境配置。

表1 實驗環境配置

4.2 實驗結果

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

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

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

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

本文提出的BLRU-F改進了劃分策略，在列劃分的基礎上，根據多核訪存需求變化以塊為單位進行重分配，并且在Cache替換時通過逐出的方式回收Cache塊資源。這種基于列劃分的塊粒度的動態重分配，既節省了開銷又達到了細粒度的動態劃分。

5 LLC共享時的算法效率分析

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

圖4 4核下LRU, ALRU-F和BLRU-F效果對比圖

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

圖6 16核LRU, ALRU-F和BLRU-F效果對比圖

6 結束語

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

[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年生，副教授，研究方向為計算機系統結構、多核計算.

李成艷： 女，1988年生，碩士生，研究方向為多核計算.

王 帥： 男，1986年生，碩士生，研究方向為多核計算.

姚治成： 男，1989年生，碩士生，研究方向為多核計算.

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改回

國家自然科學基金(61202076 )和北京市教委科技計劃面上項目(KM201210005022)資助課題