캐시 효율성 향상을 위한 적응적 셋-분할 교체정책
Adaptive Set-Division Replacement Policy for Increasing Cache Efficiency
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최신 프로세서들은 오프-칩 메모리 latency를 완화하기 위해 온-칩 캐시를 갖는다. LRU 교체정책은 셋에 있는 캐시 블록들을 LRU 스택으로 나타낸다. 이 정책은 LRU 블록을 교체 대상자로 선택한다. 대부분의 경우에 잘 수행되나 일부 메모리 집중 워크로드에 대해 주어진 캐시 크기와 연관에 대해 충분한 액세스 히스토리를 제공하지 못한다. 또한 어떤 워크로드들에서는 대부분의 라인이 유용하게 사용되지 못하고 캐시 공간을 낭비한다. 긴 액세스 히스토리를 저장한다면 캐시 적중에 기여할 수 있고 따라서 캐시 성능을 향상시킬 수 있다. 본 논문에서는 효과적인 캐시 관리를 위해 적응적 셋-분할 교체정책(Adaptive Set-division Replacement Policy : ASRP)을 제안한다. ASRP 정책은 마지막-수준 캐시의 셋을 여러 서브셋으로 분할하고 교체가 발생할 때 한 서브셋만 활성화되며, LRU 정책을 사용하는 현재 활성 서브셋으로 교체 영역이 제한된다. 어떤 서브셋이 활성화될 때, 캐시 미스가 카운트되며 미스 카운트가 임계값을 초과하면 다음 서브셋이 활성화된다. 따라서 임계값은 마지막-수준 캐시의 액세스 히스토리를 간접적으로 결정할 수 있다. 워크로드에 적합한 액세스 히스토리 길이는 응용마다 다를 수 있고, 또한 임의 응용의 실행시간 중에도 변화할 수 있다. 여러 워크로드와 한 워크로드의 여러 실행-시간 단계에 대해 임계값을 동적으로 결정하는 간단한 방법을 제안한다. 실험결과 제안한 ASRP는 베이스라인 1 MB 16-way L3 캐시의 평균 MPKI를 4.6% 감소시켰다.
Abstract
Modern processors have large on-chip caches to mitigate off-chip memory latency. The Least Recently Used(LRU) replacement policy represents the cache blocks in a set as LRU stack. This policy picks the LRU block as the replacement candidate. In most condition, it can accomplish the work well, but for some memory-intensive workload it can not provide a long enough access history for a given cache size and associativity. Also in some workload, the majority of lines go through the cache space without making any sense. Cache performance can be improved if a long range of access history can be held so that some period of records can contribute to cache hits. In this paper, we propose an Adaptive Set-division Replacement Policy(ASRP) for effective cache management. In ASRP policy, the set of the last-level cache is divided into several subsets, only one subset is activated when replacement happens and the replacement area is limited to this subset using LRU policy. The cache misses are counted when a certain subset is activated. When the miss-count exceeds a threshold, the next subset is activated. So the threshold can indirectly decide the range of access history through the last-level cache. We use a sample method to dynamically determine the threshold for different workloads and different run-time phases of a certain workload. The experiment results show that ASRP reduces the average MPKI of the baseline 1MB 16-way L3 cache by 4.6%.
참고문헌 (13)
- M. K. Qureshi, "Adaptive insertion policies for high-performance caching", ISCA'07, pp.381~391 (2007)
- M. K. Qureshi, "A case for MLP-aware cache replacement", ISCA'06, pp.167~178 (2006)
- M. Kharbutli, "Counter-based cache replacement and bypassing algorithms", IEEE Transactions On Computers, 57(4), pp.433~447 (2008)
- H. Liu, "Cache bursts: A new approach for eliminating dead blocks and increasing cache efficiency", MICRO'08, pp.222~233 (2008)
- S. M. Khan, "Decoupled dynamic cache segmentation", HPCA’12, pp.1~12 (2012)
- M. Zahran, "Cache replacement policy revisited", WDDD(Workshop on Duplicating, Deconstructing, and Debunking) (2007)
- M. Zahran, "Adaptive block placement policy for cache hierarchies", SMART'09(Statistical and Machine learning approaches to ARchitectures and compilaTion) (2009)
- E. Perelman, "Using simpoint for accurate and efficient simulation", SIGMETRICS'03, 31(1), pp.318~319 (2003)
- J. Jeong, "Optimal replacements in caches with two miss costs", SPAA’99(Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures) (1999)
- D. A. Jiménez, "Insertion and promotion for tree-based pseudo LRU last-level caches", MICRO'13, pp.284~296 (2013)
- "SimPoint home page"[URL]
- "Pin Homepage"[URL]
- M. Qureshi, "Set-dueling-controlled adaptive insertion for high performance caching", IEEE Micro, 28(1), pp.91~98 (2008)