Pseudo-LRU

Pseudo-LRU, or PLRU, is a family of cache replacement algorithms that improve on the Least Recently Used algorithm by replacing values using approximate measures of age rather than tracking the exact age of every cached value. It usually means two designs. Tree-PLRU keeps a one-bit direction flag at each node of a binary tree over the items; finding a victim follows the flags, and each access flips the flags along its path to point away from the item used. It has been used in the CPU cache of the Intel 486 and in many PowerPC processors, and as an approximation it can pick a slightly wrong victim. Bit-PLRU keeps one recently-used bit per cache line and resets the other bits when the last zero bit is set.