A Frequency Based Cache Replacement Algorithm with Partition of CMPs

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 multicores 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%.