Menu
The logic behind Pseudo LRU is to use less bits and to speed up the replacement of the block. The logic is given as "let 1 represent that the left side has been referenced more recently than the right side, and 0 vice-versa" But I am unable to understand the implementation given in the following diagram:
Details are given at : http://courses.cse.tamu.edu/ejkim/614/CSCE614-2011c-HW4-tutorial.pptx
251
Pseudo-LRU or PLRU is a family of cache algorithms which improve on the performance of the Least Recently Used (LRU) algorithm by replacing values using approximate measures of age rather than maintaining the exact age of every value in the cache.
We need one bit per set to identify which of these blocks is the LRU block. Note that if block 0 is the LRU block, then block 1 is the MRU (most recently used) block, and vice versa.
LRU is a cache eviction algorithm called least recently used cache. Look at this resource. LFU is a cache eviction algorithm called least frequently used cache. It requires three data structures. One is a hash table that is used to cache the key/values so that given a key we can retrieve the cache entry at O(1).
LRU and 2-random are pretty close, with LRU edging out 2-random for the smaller caches and 2-random edging out LRU for the larger caches. As we might expect, LRU does worse than 2-random when the miss rates are high, and better when the miss rates are low.
I'm also studying about Pseudo-LRU. Here is my understand. Hope it's helpful.
"Hit CL1": there's a referent to CL1, and hit LRU state (B0 and B1) are changed to inform CL1 is recently referred.
"Hit CL0": there's a referent to CL0, and hit LRU state (B1) is updated to inform that CL0 is recently used (than CL1)
"Miss; CL2 replace" There's a miss, and LRU is requested for replacement index. As current state, CL2 is chose. LRU state (B0 and B2) are updated to inform CL2 is recently used. (it's also cause next replacement will be CL1)
79
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
