Hardware Implementation of Stack-Based Replacement Algorithms
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
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:55175", author = "Hassan Ghasemzadeh and Sepideh Mazrouee and Hassan Goldani Moghaddam and Hamid Shojaei and Mohammad Reza Kakoee", title = "Hardware Implementation of Stack-Based Replacement Algorithms", 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.", volume = "2", number = "4", pages = "1121-5", }
