Journal of the Institute of Electronics and Information Engineers (전자공학회논문지)

The Institute of Electronics and Information Engineers (대한전자공학회)
권호 표지
DOI QR코드

DOI QR Code

Cache Replacement Policy Based on Dynamic Counter for High Performance Processor

고성능 프로세서를 위한 카운터 기반의 캐시 교체 알고리즘

  • Jung, Do Young (Department of Electrical Electronic Eng., Yonsei University) ;
  • Lee, Yong Surk (Department of Electrical Electronic Eng., Yonsei University)
  • 정도영 (연세대학교 전기전자공학부) ;
  • 이용석 (연세대학교 전기전자공학부)
  • Received : 2012.10.26
  • Published : 2013.04.25
Download PDF
⟨ Previous Next ⟩

Abstract

Replacement policy is one of the key factors determining the effectiveness of a cache. The LRU replacement policy has remained the standard for caches for many years. However, the traditional LRU has ineffective performance in zero-reuse line intensive workloads, although it performs well in high temporal locality workloads. To address this problem, We propose a new replacement policy; DCR(Dynamic Counter based Replacement) policy. A temporal locality of workload dynamically changes across time and DCR policy is based on the detection of these changing. DCR policy improves cache miss rate over a traditional LRU policy, by as much as 2.7% at maximum and 0.47% at average.

캐시 메모리의 성능에 큰 영향을 미치는 요소 중 하나인 캐시 교체 알고리즘 중에서 가장 최적의 성능을 가지는 알고리즘은 LRU알고리즘이다. LRU알고리즘은 데이터의 temporal locality특성이 강한 프로그램에서 좋은 성능을 보여주지만, 그렇지 않은 프로그램에서는 많은 캐시 미스를 발생시킨다. 본 논문에서는 LRU알고리즘의 이러한 단점을 개선하기 위한 새로운 카운터 기반 교체 알고리즘인 DCR(Dynamic Counter based Replacement) 알고리즘을 제안한다. 본 논문에서는 캐시에 저장된 이후로 교체되기 전까지 다시 사용되지 않는 데이터인 zero reuse line의 발생 추이를 관찰함으로써 프로그램의 temporal locality 특성이 시간에 따라 동적으로 변화함을 보였다. 그리고 이에 착안하여 제안하는 DCR 알고리즘은 주기적으로 zero reuse line의 수를 카운트하여 프로그램의 temporal locality 변화에 대응할 수 있도록 하였다. DCR 알고리즘은 기존의 LRU알고리즘과 비교하여 최대 2.7%, 평균 0.47%의 미스율 감소를 보였다.

Keywords

References

  1. Hennessy J. L, Patterson D., "Computer Architecture: A Quantitative Approach", Fourth Edition, Morgan Kaufmann Publishers, pp. 288-309, 2007.
  2. M. V. Wilkes, "The Memory Gap and the Future of High Performance Memories", SIGARCH Comput. Archit. News, 2001.
  3. M. D. Hill, A. J. Smith, "Evaluation associativity in CPU Caches", IEEE Trans. Comput., 38(12):1612-1630, 1989. https://doi.org/10.1109/12.40842
  4. H. Al-Zoubi, A. Milenkovic, M. Milenkovic, "Performance Evaluation of Cache Replacement Policies for the SPEC CPU2000 Benchmark Suite", ACM-SE 42: Proceedings of the 42nd annual southeast regional conference P267-272, New York, USA, 2004.
  5. J. T. Robinson, M. V. Devarakonda, "Data Cache Management Using Frequency-based Replacement", In Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, P.134-142, 1990.
  6. M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, J. Emer, "Adaptive Insertion Policies for High Performance Caching", ISCA 2007: Proceedings of the 34th annual international symposium on Computer Architecture, P.381-391, New York, NY, USA, 2007.
  7. Q. Wang, "WLRU CPU Cache Replacement Algorithm", Ph.D. Thesis, The University of Western Ontario, 2006.
  8. N. Duong, R. Cammarota, D. Zhao, T. Kim, and A. Veidenbaum, "SCORE: A Score-based Memory Cache Replacement Policy", JWAC 2010 : 1st JILP Worshop on Computer Architecture Compettions: Cache Replacement Championship, 2010.
  9. M. K. Qureshi, D. N. Lynch, O. Mutlu, and T. N. Patt, "A case for MLP-aware cache replacement", ISCA 2006: Proceedings of the 33th annual international symposium on Computer Architecture, 2007.
  10. S. Khan, Y. Tian, and D. A. Jimenez, "Sampling Dead Block Prediction for Last-Level Caches", Micro, 2010.
  11. www.simplescalar.com
  12. www.spec.org/cpu2000/