Tree-PLRU is an efficient
algorithm to select an item that most likely has not been accessed very recently, given a set of items and a sequence of access events to the items. This technique is used in the
CPU cache of the
Intel 486 and in many processors in the
PowerPC family, such as
Freescale's PowerPC G4 used by
Apple Computer. The algorithm works as follows: consider a
binary search tree for the items in question. Each node of the tree has a one-bit flag denoting "go left to insert a pseudo-LRU element" or "go right to insert a pseudo-LRU element". To find a pseudo-LRU element, traverse the tree according to the values of the flags. To update the tree with an access to an item N, traverse the tree to find N and, during the traversal, set the node flags to denote the direction that is opposite to the direction taken. This algorithm can be sub-optimal since it is an approximation. For example, in the above diagram with A, C, B, D cache lines, if the access pattern was: C, B, D, A, on an eviction, B would be chosen instead of C. This is because both A and C are in the same half and accessing A directs the algorithm to the other half that does not contain cache line C. ==Bit-PLRU==