Abstract
Cache memory plays an important role in the in-memory computation in memory-intensive applications. Hierarchical cache design is used to increase the capacity of cache to handle large working set. The last level cache (LLC) does not strictly follow the temporal locality of program, so it becomes challenging to identify the blocks that will not be reused (dead block). In this paper, we have performed a detail survey on different techniques to detect the dead blocks early in the cache memory and improve the hit rate of cache replacement algorithm. Belady’s optimal solution detects the dead block by analyzing the future of blocks, which is completely un-realistic. Many researches have been done to detect dead block practically by observing the previous access pattern. Many algorithms are proposed to improve the performance of traditional replacement policies by considering different additional information. Most of the algorithm aims to reduce the miss count by retaining the blocks that will be reused before eviction (live blocks). Recent study observes that the cost of all the cache miss are not uniform in nature. So, some researchers have distinguished between high-cost block and low-cost block. The overall cost can be reduced by retaining the high-cost block in memory, with little higher miss count. It is observed that by managing cache miss un-coordinately among the different levels of cache memory, it is not possible to obtain maximum utilization of memory. Many adaptive algorithms have been proposed to maintain balance between the over-utilized blocks and underutilized blocks by the displacement of blocks. In this survey, we have categorized the practically implemented techniques into different classes based on their basic principle of cache replacement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Wulf, W.A., McKee, S.A.: Hitting the memory wall: implications of the obvious. Comput. Archit. News 23, 20–24 (1995)
Lai, A.-C., Fide, C., Falsafi, B.: Dead-block prediction & dead-block correlating prefetchers. ACMSIGARCH Comput. Archit. News 29(2), 144–154 (2001)
Liu, H., Ferdman, M., Huh, J., Burger, D.: Cache bursts: a new approach for eliminating deadblocks and increasing cache efficiency. In: 41st IEEE/ACM International Symposium on Micro-architecture, 2008, pp. 222–233
Das, P.: Role of cache replacement policies in high performance computing systems: a survey. Commun. Comput. Inform. Sci. 400–410 (2019)
Belady, L.: A study of replacement algorithms for a virtual-storage computer. IBM Syst.J. (1966)
Das, S., Polavarapu, N., Halwe, P.D., Kapoor, H.K.: Random-LRU: a re-placement policy for chip multiprocessors. İn: Proceedings of the International Symposium on VLSI Design and Test (VDAT) (July 2013)
Roy, B., Das, P.: SplitWays: an efficient replacement policy for larger sized cache memory. Int. J. Eng. Adv. Technol. (IJEAT), 9(1), 4230–4234 (October 2019)
Jain, A., Lin, C.: Back to the future: leveraging Belady’s algorithm for improved cache replacement. ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA), Seoul, pp. 78–89 (2016)
Qureshi, M.K., Jaleel, A., Patt, Y.N., Steely, S.C., Emer, J.: Adaptive insertion policies for high performance caching. In: International Symposium on Computer Architecture (ISCA), pp. 381–391 (2007)
Do, C.T., Choi, H.-J., Kim, J.M., Kim, C.H.: A new cache replacement algorithm for last-level caches by exploiting tag-distance correlation of cache lines. Microprocess. Microsyst. 39(4–5), 286–295 (2015)
Chaudhuri, M.: Pseudo-LIFO: the foundation of a new family of replacement policies for last-level caches. In: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 42). ACM, New York, NY, USA, 2009, pp. 401–412
Rodríguez-Rodríguez, R., Castro, F., Chaver, D., Pinuel, L., Tirado, F.: Reducing Writes in Phase-Change Memory Environments by Using Efficient Cache Replacement Policies, pp. 93–96. Design, Automation & Test in Europe Conference & Exhibition (DATE), Grenoble, France (2013)
Albericio, J., Ibáñez, P., Viñals, V., Llabería, J.M.: Exploiting reuse locality on inclusive shared last-level caches. ACM Trans. Archit. Code Optim. 9(4), 19 (January 2013). Article 38
Lee, D., Choi, J., Kim, J., Noh, S., Min, S., Cho, Y., Kim, C.: LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Trans. Comput. 50(12) (2001)
Denning, P.J.: Thrashing: its causes and prevention. In: Proceedings of the December 9–11, 1968 Fall Joint Computer Conference Part I, pp. 915–922 (1968)
Jain, A., Lin, C.: Rethinking Belady’s Algorithm to Accommodate Prefetching, pp. 110–123. ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), Los Angeles, CA (2018)
Kharbutli, M., Solihin, Y.: Counter-based cache replacement and bypassing algorithms. IEEE Trans. Comput. (2008)
Vakil-Ghahani, A., Mahdizadeh-Shahri, S., Lotfi-Namin, M., Bakhshalipour, M. Lotfi-Kamran, P., Sarbazi-Azad , H.: Cache Replacement Policy Based on Expected Hit Count. IEEE Computer Architecture Letters 17(1), 64–67 (2018)
Liu, H., Ferdman, M., Huh, J., Burger, D.: Cache bursts: A new approach for eliminating dead blocks and increasing cache efficiency. 41st IEEE/ACM International Symposium on Microarchitecture, Lake Como, 2008, pp. 222–233
Qureshi, M., Lynch, D., Mutlu, O., Patt, Y.: A case for MLP-aware cache replacement. In: Proceedings of 33rd Annual International Symposium Computer Architecture, pp. 167–178 (2006)
Kharbutli, M., Sheikh, R.: LACS: a locality-aware cost-sensitive cache replacement algorithm. IEEE Trans. Comput. 63(8), 1975–1987 (2014)
Sheikh, R., Kharbutli, M.: Improving cache performance by combining cost-sensitivity and locality principles in cache replacement algorithms. In: IEEE International Conference on Computer Design, Amsterdam, pp. 76–83 (2010)
Jeong, J., Dubois, M.: Cost-sensitive cache replacement algorithms. In: Proceedings of 9th Interational Symposium High-Perform. Computer Architecture, pp. 327–337 (2003)
Jeong, J., Dubois, M.: Cache replacement algorithms with nonuniform miss costs. IEEE Trans. Comput. 55(4), 353–365 (2006)
Jeong, J., Stenstrom, P., Dubois, M.: Simple penalty-sensitive cache replacement policies. J. Instruct.-Level Parallel 10 (2008)
Srinivasan, S., Dz-Ching Ju, R., Lebeck, A., Wilkerson, C.: Locality vs. criticality. In: Proceedings of 28th Annual International Symposium Computer Architecture, pp. 132–143 (2001)
Ma, T., Qu, J., Shen, W., Tian, Y., Al-Dhelaan, A., Al-Rodhaan, M.: Weighted greedy dual size frequency based caching replacement algorithm. In IEEE Access, vol. 6, pp. 7214–7223 (2018)
Chen, D., Jin, H., Liao, X., Liu, H., Guo, R., Liu, D.: MALRU: Miss-penalty aware LRU-based cache replacement for hybrid memory systems. Design, Automation & Test in Europe Conference & Exhibition (DATE), Lausanne, pp. 1086–1091 (2017)
Tian, G., Liebelt, M.: An effectiveness-based adaptive cache replacement policy. Microprocess. Microsyst. 38(1), 98–111 (2014)
Qureshi, M.K., Jaleel, A., Patt, Y.N., Steely, S.C., Emer, J.: Adaptive insertion policies for high performance caching. In: Proceedings of the 34th Annual International Symposium on Computer Architecture, San Diego, California, USA (2007), 09–13 June 2007
Manivannan, M., Pericás, M., Papaefstathiou, V., Stenström, P.: Global dead-block management for task-parallel programs. ACM Trans. Archit. Code Optim. 15(3), 25 (2018), Article 33
Tada, J., Sato, M., Egawa, R.: An adaptive demotion policy for high-associativity caches. In: Proceedings of the 8th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies (HEART 2017). ACM, New York, NY, USA (2017), Article 4, 6
Reishi Kumaar, T., Sharma, A., Bhaskar, M.: Reference table based cache design using LRU replacement algorithm for Last Level Cache. In: IEEE Region 10 Conference (TENCON), Singapore, pp. 2219–2223 (2016)
Rolán, D., Fraguela, B.B., Doallo, R.: Adaptive line placement with the set balancing cache. In: 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), New York, NY, 2009, pp. 529–540
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Das, P., Roy, B.R. (2021). A Categorical Study on Cache Replacement Policies for Hierarchical Cache Memory. In: Mandal, J., Mukhopadhyay, S., Roy, A. (eds) Applications of Internet of Things. Lecture Notes in Networks and Systems, vol 137. Springer, Singapore. https://doi.org/10.1007/978-981-15-6198-6_19
Download citation
DOI: https://doi.org/10.1007/978-981-15-6198-6_19
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-6197-9
Online ISBN: 978-981-15-6198-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)