Pseudo-LRU
Encyclopedia
Pseudo-LRU usually refers two cache replacement algorithms: tree-PLRU and bit-PLRU.
Tree-PLRU, is an efficient algorithm
to find 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 Power Architecture
(formerly 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 find a pseudo-LRU element" or "go right to find 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.
Bit-PLRU stores one status bit for each cache line. We call these
bits MRU-bits. Every access to a line sets its MRU-bit to 1, indicating that the
line was recently used. Whenever the last remaining 0 bit of a sets status bits is
set to 1, all other bits are reset to 0. At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
Tree-PLRU, is an efficient algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to find 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
CPU cache
A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
of the Intel 486 and in many processors in the Power Architecture
Power Architecture
Power Architecture is a broad term to describe similar RISC instruction sets for microprocessors developed and manufactured by such companies as IBM, Freescale, AMCC, Tundra and P.A. Semi...
(formerly PowerPC
PowerPC
PowerPC is a RISC architecture created by the 1991 Apple–IBM–Motorola alliance, known as AIM...
) family, such as Freescale's PowerPC G4
PowerPC G4
PowerPC G4 is a designation used by Apple Computer to describe a fourth generation of 32-bit PowerPC microprocessors. Apple has applied this name to various processor models from Freescale, a former part of Motorola....
used by Apple Computer
Apple Computer
Apple Inc. is an American multinational corporation that designs and markets consumer electronics, computer software, and personal computers. The company's best-known hardware products include the Macintosh line of computers, the iPod, the iPhone and the iPad...
.
The algorithm works as follows: consider a binary search tree
Binary search tree
In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
for the items in question. Each node of the tree has a one-bit flag denoting "go left to find a pseudo-LRU element" or "go right to find 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.
Bit-PLRU stores one status bit for each cache line. We call these
bits MRU-bits. Every access to a line sets its MRU-bit to 1, indicating that the
line was recently used. Whenever the last remaining 0 bit of a sets status bits is
set to 1, all other bits are reset to 0. At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.