Abstract
As the number of cores and associativity of the last level cache (LLC) on a Chip Multi-processor increases, the role of replacement policies becomes more vital. Though, pure least recently used (LRU) policy has some issues it has been generally believed that some versions of LRU policy performs better than the other policies. Therefore, a lot of work has been proposed to improve the performance of LRU-based policies. However, it has been shown that the true LRU imposes additional complexity and area overheads when implemented on high associative LLCs. Most of the LRU based works are more motivated towards the performance improvement than the reduction of area and hardware overhead of true LRU scheme. In this paper we proposed an LRU based cache replacement policy especially for the LLC to improve the performance of LRU as well as to reduce the area and hardware cost of pure LRU by more than a half. We use a combination of random and LRU replacement policy for each cache set. Instead of using LRU policy for the entire set we use it only for some number of ways within the set. Experiments conducted on a full-system simulator shows 36% and 11% improvements over miss rate and CPI respectively.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balasubramonian, R., Jouppi, N.P., Muralimanohar, N.: Multi-Core Cache Hierarchies. Morgan & Claypool Publishers (2011)
Belady, L.: A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5(2), 78–101 (1966)
Wong, W., Baer, J.L.: Modified lru policies for improving second-level cache behavior. In: Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, HPCA-6, pp. 49–60 (2000)
Kharbutli, M., Solihin, Y.: Counter-based cache replacement and bypassing algorithms. IEEE Trans. Comput. 57(4), 433–447 (2008)
Qureshi, M.K., Jaleel, A., Patt, Y.N., Steely, S.C., Emer, J.: Adaptive insertion policies for high performance caching. SIGARCH Comput. Archit. News 35(2), 381–391 (2007)
Jain, A., Shrivastava, A., Chakrabarti, C.: La-lru: A latency-aware replacement policy for variation tolerant caches. In: 2011 24th International Conference on VLSI Design (VLSI Design), pp. 298–303 (2011)
Qureshi, M.K., Lynch, D.N., Mutlu, O., Patt, Y.N.: A case for mlp-aware cache replacement. SIGARCH Comput. Archit. News 34(2), 167–178 (2006)
Belady, L.: A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal (1966)
Wong, W., Baer, J.L.: Modified lru policies for improving second-level cache behavior. In: Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, HPCA-6, pp. 49–60 (2000)
Zahran, M.: Cache replacement policy revisited. In: The Annual Workshop on Duplicating, Deconstructing, and Debunking (WDDD) Held in Conjunction with the International Symposium on Computer Architecture (ISCA) (June 2007)
Fricker, C., Robert, P., Roberts, J.: A versatile and accurate approximation for lru cache performance. In: 2012 24th International Teletraffic Congress (ITC 24), pp. 1–8 (2012)
Morales, K., Lee, B.K.: Fixed segmented lru cache replacement scheme with selective caching. In: 2012 IEEE 31st International Performance Computing and Communications Conference (IPCCC), pp. 199–200 (2012)
Juan, F., Chengyan, L.: An improved multi-core shared cache replacement algorithm. In: 2012 11th International Symposium on Distributed Computing and Applications to Business, Engineering Science (DCABES), pp. 13–17 (2012)
Martin, M.M.K., Sorin, D.J., Beckmann, B.M., Marty, M.R., Xu, M., Alameldeen, A.R., Moore, K.E., Hill, M.D., Wood, D.A.: Multifacet’s general execution-driven multiprocessor simulator (gems) toolset. SIGARCH Comput. Archit. News 33(4), 92–99 (2005)
Agarwal, N., Krishna, T., Peh, L.S., Jha, N.: Garnet: A detailed on-chip network model inside a full-system simulator. In: IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2009, pp. 33–42 (April 2009)
Bienia, C.: Benchmarking Modern Multiprocessors. PhD thesis, Princeton University (January 2011)
Alameldeen, A., Martin, M., Mauer, C., Moore, K., Xu, M., Hill, M., Wood, D., Sorin, D.: Simulating a $2m commercial server on a $2k pc. Computer 36(2), 50–57 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, S., Polavarapu, N., Halwe, P.D., Kapoor, H.K. (2013). Random-LRU: A Replacement Policy for Chip Multiprocessors. In: Gaur, M.S., Zwolinski, M., Laxmi, V., Boolchandani, D., Sing, V., Sing, A.D. (eds) VLSI Design and Test. Communications in Computer and Information Science, vol 382. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-42024-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-42024-5_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-42023-8
Online ISBN: 978-3-642-42024-5
eBook Packages: Computer ScienceComputer Science (R0)