Study of Different Cache Line Replacement Algorithms in Embedded Systems

Abstract

The increasing speed gap between processors and memories underlines the criticalness of cache memories. The strong area and power consumption constraints of general purpose embedded systems limit the size of cache memories. With the development of embedded systems provided with an operative system, these constraints are even stronger. The selection of an efficient replacement policy thus appears as critical. The Least Recently Used (LRU) strategy performs well on most memory patterns but this performance is obtained at the expense of the hardware requirements and of the power consumption. Consequently, new algorithms have been developed and this work is devoted to the evaluation of their performance. The implementation of a cache simulator allowed us to carry out a detailed investigation of the behaviour of the policies, which among others demonstrated the occurrence of Belady's anomaly for a pseudo-LRU replacement algorithm, PLRUm. The replacement strategies that emerged from this study were then integrated in the ARM11 MPCore processor and their performance results were compared with the cache simulator ones. Our results show that the MRU-based pseudo-LRU replacement policy (PLRUm) approximates the LRU algorithm very closely and can even outperform it with low hardware and power consumption requirements. Study of different cache line replacement algorithms in embedded systems ii Acknowledgements

Topics

    39 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)