Hardware Implementation of Stack-Based Replacement Algorithms

Authors: Hassan Ghasemzadeh, Sepideh Mazrouee, Hassan Goldani Moghaddam, Hamid Shojaei, Mohammad Reza Kakoee

Abstract:

Block replacement algorithms to increase hit ratio have been extensively used in cache memory management. Among basic replacement schemes, LRU and FIFO have been shown to be effective replacement algorithms in terms of hit rates. In this paper, we introduce a flexible stack-based circuit which can be employed in hardware implementation of both LRU and FIFO policies. We propose a simple and efficient architecture such that stack-based replacement algorithms can be implemented without the drawbacks of the traditional architectures. The stack is modular and hence, a set of stack rows can be cascaded depending on the number of blocks in each cache set. Our circuit can be implemented in conjunction with the cache controller and static/dynamic memories to form a cache system. Experimental results exhibit that our proposed circuit provides an average value of 26% improvement in storage bits and its maximum operating frequency is increased by a factor of two

Keywords: Cache Memory, Replacement Algorithms, LeastRecently Used Algorithm, First In First Out Algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062248

References:

[1] J. Handy, The Cache Memory Book, Academic Press, San Diego, pp. 47-67, 1993.
[2] H. Ghasemzadeh, S. Mazrouee and M. R. Kakoee, Modified Pseudo LRU Replacement Algorithm, 13th Annual IEEE International Conference and Workshop on the Engineering of Computer Based Systems (ECBS), pp. 368-376, March 27-30 2006.
[3] R. Pendse, Pipeline LRU Block Replacement Algorithm, Proc. 43rd Midwest Symp. On Circuits and Systems, Lansing MI, Aug. 8-11, 2002.
[4] J. Jeong and M. Dubios, Cost-Sensitive Cache Replacement Algorithms, 9th International Symposium on High-Performance Computer Architecture (HPCA-9'03), 2002.
[5] S. Jiang, X. Zhang, Making LRU Friendly to Weak Locality Workloads : A Novel Replacement Algorithm to Improve Buffer Cache Performance, IEEE Transactions on Computers, Vol. 54, No. 8, Aug. 2005.
[6] R. Pendse, Pipeline LRU Block Replacement Algorithm, Proc. 43rd Midwest Symp. On Circuits and Systems, Lansing MI, Aug. 8-11, 2002.
[7] D. Lee, et. Al., LRFU : a spectrum of policies that subsumes the least recently used and least frequently used policies, IEEE Transaction on Computers, vol. 50, no. 12, pp. 1352-1361, 2001.
[8] A.W. Wayne and J.L. Baer, Modified LRU Policies for Improving Second-Level Behavior, proceeding 6th International Symposium on High-Performance Computer Architecture, pp. 49-60, 2000.
[9] Yoon, J., Min, S.L., and Cho, Y., Buffer cache management: predicting the future from the past, International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'02), pp. 92-97, 2002.
[10] H. Ghasemzadeh and S. O. Fatemi, Pseudo-FIFO Architecture of LRU Replacement Algorithm, Proc. 9th IEEE International Multi Topic Conference (INMIC), December 23-25, 2005.
[11] D. Lamet and J.F. Frenzel, Defect-Tolerant Cache Memory Design, IEEE Transactions on Computers, April 1993.
[12] B. Beridegard, B. Nilsson and L. Philipson, VLSI Implementation of A Virtual Memory Paging Algorithm, VLSI: Algorithms and Architectures, Elsevier Science Publishers B.V., pp. 167-174, 1985.
[13] W. Luk and G. Brown, A Systolic LRU Processor and Its Top-Down Development, Science of Computer Programming, Vol. 15, pp. 217-233, 1990.
[14] O. Fatemi, F. Idris and S. Panchanathan, FPGA Implementation of the LRU Algorithm for Video Compression, IEEE 1994 International Conference on Acoustics, Speech, and Signal Processing, pp. 337-344, June 1994.
[15] K.A. Hurd, A 600MHZ 64b PA-RISC Microprocessor, ISSCC Digest of Technical Papers, pp 94-95, February 2000.
[16] K. Maruyama, mLRU Replacement Algorithm in terms of the Reference Matrix, IBM Technical Disclosur Bulletin, pp. 3101-3103, March 1975.
[17] J.M. Rabaey, Digital Integrated Circuits, A Design Perspective, Prentice- Hall Electronics and VLSI Series, pp. 332-381, 1996.
[18] Weste N.H.E. and Eshraghian K., Principles of CMOS VLSI Design, A System Perspective, Second Edition, Addison-Wesely Publishers Company, pp. 513-620, 1994.