一种基于频率的多核共享Cache替换算法

摘要

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%.%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%。提出的两种算法在性能提升的同时，并没有明显地增加能耗。