재사용성 예측 시스템에 기반한 동적 캐시 메모리 관리 기법 = A Reuse Predictor for Dynamic Cache Insertion

국문 초록 (Abstract)

프로세서가 갖는 제한된 자원을 효과적으로 사용하여 고성능을 얻기 위해서는 캐시 메모리의 효율적인 관리가 필수적인 요소이다. 가장 널리 사용되고 있는 Least Recently Used(LRU) 정책은, 캐시메모리에 올려진 후 대체될 때까지 재사용이 되지 않는 라인, 즉 Dead Line 문제를 고려하지 않고, 사용된 시점에 기반하여 가장 오래 전에 사용된 라인을 대체라인으로 선정한다. 비록, LRU 정책이 많은 경우에 효과적으로 동작하지만, 메모리 집약적인 프로그램을 수행 시에는 성능이 현저히 떨어진다는 것이 많은 연구에서 밝혀졌다. 본 논문에서는 이 문제를 해결하기 위한 새로운 캐시 관리 정책, Predictor for Cache Insertion(PCI) 정책을 제안하고 있다. 대체되는 다수의 라인이 극히 적은 재사용 빈도를 보임에 착안하여, PCI는 과거의 기록을 토대로, 각 라인의 재사용성, 즉 Cache Utilization Factor(CUF)를 예측하여, 새로운 라인이 캐시에 올려질 위치를 동적으로 결정한다. 실험 결과, PCI는 메모리 공간에 대한 추가 부담을 최소화하면서, LRU 대비 2차 캐시 미스율이 CINT2000과 CFP2000에 대해 각각 최대 8.49%, 23.71%까지 향상됨을 확인하였다.

다국어 초록 (Multilingual Abstract)

Efficient cache replacement plays an increasingly crucial role to achieve high performance and mitigate limited resource constraints in modern processor designs. Traditional Least Recently Used (LRU) policy is widely used and focuses only on how to find a victim candidate to be evicted without taking a dead line, a cache line that is not reused until being evicted, into consideration. Although the LRU performs well in many situations, its performance severely degrades for some memory-intensive workloads which have too large a working set to fit into a limited cache. This paper presents a new cache replacement policy, Predictor for Cache Insertion (PCI), to mitigate the performance degradation due to the dead line problem. Based on the biased distribution of reusability measure of the evicted cache lines, the proposed PCI architecture fully exploits a predictor to speculate how frequently each cache line is likely to be reused by learning the past behavior of each cache line at run-time. The PCI policy then decides the position of a newly inserted cache line dynamically based on its speculated future reusability, evaluated by Cache Utilization Factor (CUF). Experimental results show that the proposed PCI scheme reduces the L2 cache miss rate up to 8.49% and 23.71% with CINT2000 and CFP2000 workloads respectively compared to a traditional LRU scheme, with a minimal impact on the storage overhead.

목차 (Table of Contents)

• 요약
• Abstract
• 1. Introduction
• 2. Background and Motivation
• 3. Predictor For Cache Insertion
• 4. Evaluation
• 5. Related Work
• 6. Conclusion
• References

참고문헌 (Reference)

• 1 M. K. Qureshi, "case for MLP-aware cache replacement" 167-177, 2006
• 2 T. Austin, "SimpleScalar: An infrastructure for computer system modeling" 35 : 59-67, 2002
• 3 A. C. Lai, "Selective, accurate, and timely self-invalidation using last-touch prediction" 2000
• 4 J. L. Henning, "SPEC CPU2000: Measuring CPU performance in the new millennium" 33 : 28-35, 2000
• 5 I. Burcea, "Predictor virtualization" 43 : 157-167, 2008
• 6 I. Burcea, "Phantom-BTB:A Virtualized Branch Target Buffer Design" 14 : 313-323, 2009
• 7 Y. J. Xie, "PIPP: Promotion/Insertion Pseudo- Partitioning of Multi-Core Shared Caches" 174-183, 2009
• 8 L. X. Xiang, "Less Reused Filter: Improving L2 Cache Performance via Filtering Less Reused Lines" 2009
• 9 M. Takagi, "Inter-reference gap distribution replacement: an improved replacement algorithm for set-associative caches" 30-, 2004
• 10 J. Abella, "IATAC: a smart predictor to turn-off L2 cache lines" 2 : 55-77, 2005
• 11 J. D. Kron, "Double-DIP: Augmenting DIP with Adaptive Promotion Policies to Manage Shared L2 Cache" 2008
• 12 A. C. Lai, "Dead-Block Prediction & Dead- Block Correlating Prefetchers" 144-154, 2001
• 13 H. Dybdahl, "An LRU-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches" 35 : 45-52, 2007
• 14 A. Jaleel, "Adaptive Insertion Policies for Managing Shared Caches" 2008
• 15 M. K. Qureshi, "Adaptive Insertion Policies for High Performance Caching" 2007