1. Pseudo-LRU and LRU
Cache replacement strategies are used to determine which cache items should be replaced when the cache space is full. Pseudo-LRU (Pseudo-Least Recently Used) and LRU (Least Recently Used) are both common cache replacement strategies, and they have the following differences:
Principle:
- LRU: The LRU strategy determines the usage frequency of cache items based on the time of recent access. When the cache space is full, it selects the cache item that has not been accessed for the longest time for replacement.
- Pseudo-LRU: Pseudo-LRU, also known as approximate LRU, uses a binary tree or similar data structure to maintain the access history of cache items. Each node represents a cache item, and the leaf nodes of the tree represent the state of the cache items (used or unused). By comparing the states of the leaf nodes, the Pseudo-LRU strategy selects the unused cache items for replacement.
Implementation Complexity:
- LRU: The LRU algorithm is relatively simple and does not require maintaining additional data structures; it only needs one data structure (like a doubly linked list) to record the access order.
- Pseudo-LRU: The implementation of Pseudo-LRU is relatively complex, as it requires maintaining an additional data structure (like a binary tree) to track the access status of cache items.
Accuracy:
- LRU: The LRU strategy accurately tracks the access time of each cache item and selects the cache item that has not been accessed for the longest time for replacement.
- Pseudo-LRU: The Pseudo-LRU strategy is an approximate algorithm that estimates the access time of cache items by maintaining a binary tree, so it may make less accurate replacement decisions in some cases.
Memory Usage:
- LRU: The LRU strategy only requires one additional data structure to record the access order, so it has relatively low memory usage.
-
Pseudo-LRU: The Pseudo-LRU strategy requires maintaining a binary tree or similar data structure, resulting in relatively high memory usage. Overall, LRU is a classic cache replacement strategy that is simple and effective, but may not be precise enough in certain specific scenarios. Pseudo-LRU is an approximate algorithm that provides more accurate replacement decisions by maintaining additional data structures, but it correspondingly increases complexity and memory usage. The choice of which replacement strategy to use depends on the specific application scenario and requirements.
2. Cache Replacement Strategy in Arm Architecture – A78 as an Example
3. Dynamic Biased Replacement Policy
The Dynamic Biased Replacement Policy (动态偏置替换策略) is an advanced cache replacement strategy that dynamically adjusts the replacement priority of various cache items based on access patterns.
Traditional cache replacement strategies (such as LRU, FIFO, Random, etc.) do not consider the access frequency or importance of different cache items when making replacement decisions. However, access patterns may lead to certain cache items being accessed frequently while others are rarely accessed. This introduces the concept of the dynamic biased replacement strategy.
The dynamic biased replacement strategy gives some cache items higher replacement priority based on their access patterns, allowing these important cache items to be retained more frequently. Thus, frequently accessed cache items have a higher protection against replacement compared to less important cache items, reducing the probability of them being replaced.
There are many ways to implement the dynamic biased replacement strategy, one common method is to assign an access counter or weight to each cache item and make replacement decisions based on these counters or weights. Cache items with high access counts or weights have lower priority during replacement, thus improving the retention probability of these cache items.
The dynamic biased replacement strategy can adaptively adjust according to actual access patterns (in simple terms, this is AI intelligent replacement), to accommodate different application scenarios and changes in access patterns. It can help improve cache hit rates and performance, and in some cases reduce the performance overhead caused by replacements. However, implementing and adjusting the dynamic biased replacement strategy requires consideration of monitoring access patterns and computational overhead, ensuring appropriate trade-offs and performance gains.
4. Summary
In Armv8/Armv9 architectures, the replacement strategy for L1-I and L1-D is Pseudo-LRU, while L2 uses Dynamic Biased Replacement Policy (AI Intelligent Replacement).