Study, Assessment And Optimisation Of Last Level Cache Replacement Policies In Cmp Systems

Abstract

The constantly increasing demand for more efficient computing systems motivated the hardware manufacturers to make innovative changes in existing technology, in order toachieve faster transmission, processing and storing of data. The transition from single-processing to multi-processing systems was one of the main changes, where many designing issues were resolved by adopting the principles of single-processing systems. The way multi-processing systems operate is yet to be fully understood and does not resemble that of single-processing systems, thus opening the path of research for new optimal design changes. Among the fields that favour research is memory hierarchy, where optimal replacement policy -Least Recently Used (LRU)- for the Last Level Cache (LLC) was transferred unchanged from single-processing to multi-processing systems. Researches have shown that LRU is not the best LLC replacement policy for multiprocessing systems, whereas several competing policies have been proposed, which perform better than LRU.The major subject of this diploma thesis is the study, implementation, evaluation and optimization of last level cache replacement algorithms for multiprocessing systems. Specifically a comparison is made between several implemented replacement policies -for instance: ABFCP, TADIP, TADRRIP, PIPP, UCP- with respect to LRU. Moreover an alternative for one of these policies (ABFCP) is proposed, which shows an improvement at a degree comparable to the best performing ones, as well as combining considerably reduced hardware overhead.