Last Level Cache에서 캐시 실패율을 줄이기 위한 그룹 기반 교체 알고리즘
Group-Based Replacement Algorithm to Reduce Cache Miss in Last Level Cache
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
마이크로프로세서에 비해 상대적으로 느린 메모리의 속도를 극복하고, 시스템의 성능을 향상시키기 위하여 캐시가도입되어 사용되고 있다. 이러한 캐시의 성능을 더욱 향상시키기 위하여 많은 노력들이 이루어지고 있으며 그러한노력 중 하나로 최적화된 교체 알고리즘을 찾기 위한 연구들이 이루어지고 있다. 하지만 이러한 연구의 대부분은상위 레벨 캐시에 집중되어 있다. 용량이 상대적으로 큰 최하위 레벨 캐시의 경우 상위 캐시에서와는 다른 특성들을 가질 수 있다. 그렇기 때문에 상위 레벨 캐시와 똑같은 교체 알고리즘을 적용할 경우 최적의 성능을 보이지 못하는 경우가 많다. 본 논문에서는 이러한 LLC (Last Level Cache)의 특성에 초점을 맞추어 그에 적합한 그룹 기반 캐시 교체 알고리즘을 제안한다. 본 논문에서 제안하는 알고리즘에서는, 큰 배열에 속한 데이터가 다시 사용될가능성이 높은 점을 감안하여, 데이터 그룹을 기반으로 교체될 캐시 라인을 선택한다. 본 논문에서는 제안하는 그룹 기반 교체 알고리즘을 LLC에 적용하여 실험해보았으며, 이때의 캐시 실패율이 LRU 알고리즘과 비교하여 8.5%낮게 나타났다. 이때, 그룹을 정의하는 방법에 따라 성능에 차이를 보일 수 있으며, 이에 대한 연구는 추후연구로남겨둔다.
Abstract
Caches were proposed to overcome the slow access speed of the memories compared to the microprocessors,and improve the performance of the system. In order to maximize the performance of the cache, many studies have been done. Among them, many of the researches focused on finding the optimal cache replacement algorithm. However, most of the studies were mainly focusing on the high level caches. The last level cache with relatively larger capacity, may have some unique properties different from the higher level caches. Therefore, using the same replacement algorithm that high level caches use, does not always result in best performance. In this paper, we propose a group based cache replacement algorithm that focuses on the properties of the LLC. In our proposed algorithm, the victim cache is selected based on data group, assuming that array data are more likely to be reused. We evaluated our proposed group based replacement algorithm on the LLC against the LRU algorithm. Cache miss rate of our proposed algorithm was 8.5% lower compared to the LRU algorithm. The result may vary depending on the methods for determining groups. We leave this as future work.
참고문헌 (14)
- Soares, "Reducing the Harmful Effects of Last-Level Cache Polluters with an OS-Level, Software-Only Pullute Buffer", Internatinoal Symposium on Microarchitecture (2008)
- T. R. Puzak, "Analysis of Cache Replacement-Algorithms", Ph, pp.1985
- W.A. Wong, "Modified LRU Policies for Improving Second-Level Cache Behavior", International Symposium on High -Performance Architecture (2008)
- J. Alghazo, "Sf-lru Cache Replacement Algorithm", Records of the International Workshop on Memory Technology, Design and Testing (2004)
- N. Megiddo, "ARC: A Self-tuning, Low Overhead Replacement Cache", Proceedings of the Conference on File and Storage Technologies, pp.115~130 (2003)
- R. Subramanian, "Adaptive Caches: Effective Shaping of Cache Behavior to Workloads", Proceedings of the Annual IEEE, 2004, 385~396
- "File, Cache Miss Rate"[URL]
- "Advanced Computer Architecture"[URL]
- A. S. Tanenbaum, "Modern Operating Systems", second edition, 218~ (2001)
- S. Jiang, "CLOCK-Pro: An Effective Improvement of the CLOCK Replacement", Proceedings of USENIX Annual Technical Conference (2005)
- S. Bansal, "CAR: Clock with Adaptive Replacement", Proceedings of USENIX Conference on File and Storage Technologies (2004)
- A. Jaleel, "CMP$im: A Pin-Based On-The-Fly Multi-Core Cache Simulator", Modeling, Benchmarking and Simulation, ~ (2008)
- A. Phansalkar, "Analysis of Redundancy and Application Balance in the SPEC CPU2006 Benchmark Suite", ACM SIGARCH Computer Architecture News, 35(2) (2007)
- "Description of Simulation Infra Structure"[URL]