Αξιολόγηση και ανάπτυξη νέων πολιτικών αντικατάστασης κρυφής μνήμης: η πολιτική Histogram-based LRU

Abstract

Στα σύγχρονα υπολογιστικά συστήματα με όλο αυξανόμενες απαιτήσεις για αποδοτικότητα και ταχύτητα, η αποδοτική ανάκτηση δεδομένων αποτελεί κρίσιμο παράγοντα. Η κρυφή μνήμη, ούσα περιορισμένης χωρητικότητας, καθιστά απαραίτητη τη σωστή επιλογή και διαχείριση των δεδομένων που θα παραμείνουν σε αυτήν. Η επιλογή αυτή πραγματοποιείται μέσω πολιτικών αντικατάστασης, με τον αλγόριθμο LRU (Least Recently Used) να αποτελεί έναν από τους πιο διαδεδομένους. Στόχος της παρούσης εργασίας είναι η ανάπτυξη μίας νέας πολιτικής αντικατάστασης κρυφής μνήμης Histogram-based LRU, με σκοπό την ορθότερη αξιολόγηση της χρησιμότητας των δεδομένων, βασισμένη στη χρονική εγγύτητα αλλά και στη συχνότητα προσπέλασης των δεδομένων, μετριάζοντας τους περιορισμούς που συνδέονται με την κλασική LRU. Αρχικά αποτελέσματα δείχνουν ότι μπορούμε να επιτύχουμε έως και 52.3% λιγότερα cache misses, άρα και να μειώσουμε το χρόνου απόκρισης του συστήματος συγκριτικά με την LRU.

In modern computing systems, where demands for efficiency and speed continue to rise, optimizing data retrieval is a critical challenge. Given the limited capacity of cache memory, it is essential to carefully select and manage the data that remain in the cache. This selection is governed by replacement policies, with the Least Recently Used (LRU) algorithm being one of the most widely adopted approaches.This study introduces the Histogram-based LRU, an enhanced variant of the LRU algorithm designed to improve data usefulness evaluation by incorporating both temporal locality and access frequency. By addressing key limitations of the traditional LRU, our approach aims to enhance cache performance. Preliminary results indicate that the proposed method can reduce cache misses by up to 52.3%, leading to an overall decrease in response time compared to the conventional LRU strategy.