-
Notifications
You must be signed in to change notification settings - Fork 81
Description
Problem Description:
The libCacheSim library aims to be a comprehensive cache simulation tool for research. While an interface for LRU-K exists at libCacheSim/cache/eviction/cpp/LRU_K.cpp, the implementation is missing. This limits the library's ability to simulate and benchmark against this foundational algorithm, which is crucial for understanding advanced cache policies like 2Q and ARC.
Solution:
Implement the complete and functional LRU-K eviction algorithm in LRU_K.cpp, ensuring it correctly tracks and evicts based on the K-th last access time.
Feature Category:
- New cache algorithm implementation
Use Case:
Enables researchers to:
- Directly compare new algorithms against LRU-K.
- Study the impact of the 'K' parameter on cache performance.
- Understand the evolution of modern cache algorithms from LRU-K's principles.
- Reproduce academic results.
Alternatives Considered:
Currently, users must implement LRU-K externally. An internal implementation enhances libCacheSim's completeness and utility for research, providing direct K-parameter tuning not fully covered by 2Q.
Implementation Considerations:
- Efficiently store and retrieve K-th last access timestamps (e.g., using
std::unordered_mapwithstd::listorstd::setfor history). - Ensure
Kis configurable. - Handle pages with fewer than K accesses.
- Integrate with existing
EvictionPolicyinterface.
Additional Context:
LRU-K (O'Neil, O'Neil, Weikum, 1993) is a seminal algorithm that introduced history-based eviction to address scan resistance. Its inclusion is vital for a research-oriented simulation library.