Pseudo-LRU Tree Implementation

An approximation of LRU (pseudo-LRU) can be achieved if only the most recently and the least recently blocks need to be tracked. The recency of the intermediate blocks are unimportant. One such approach, uses a binary tree to keep track of the most recent and the least recent blocks.

Binary Node

A binary tree with $n$ leaves will have $n-1$ internal nodes. Thus $n$ blocks in a set will require $n-1$ bits to approximate LRU. Each node (and corresponding bit) encodes the information about which child node is $Recent$ and which child node is $Old$ . Let $1$ represent that the left side has been referenced more recently than the right side, and $0$ vice-versa.

Consider a $4$ block (line) cache implemented as a $3$ node tree.

State $00x$

Here, the first bit $0$ divides the $4$ blocks into two sets of $2$ blocks. Since this bit is a $0$ , this means that the first two blocks are $Old$ when compared to the last two blocks. The second bit is also a $0$ . This means that within the first two blocks, the first block is $Old$ when compared to the second block. Notice that the third bit is inconsequential in determining the Least Recently Used block. Within the last two blocks any block can be $Old$ or $Recent$ . This bit is marked as an $x$ . Thus, for both configurations $000$ and $001$ , the first block is the Least Recently used.

State $01x$

Here, the first bit $0$ divides the $4$ blocks into two sets of $2$ blocks. Since this bit is a $0$ , this means that the first two blocks are $Old$ when compared to the last two blocks. The second bit is a $1$ . This means that within the first two blocks, the second block is $Old$ when compared to the first block. Notice that the third bit is inconsequential in determining the Least Recently Used block. Within the last two blocks any block can be $Old$ or $Recent$ . This bit is marked as an $x$ . Thus, for both configurations $010$ and $011$ , the second block is the Least Recently used.

State $1x0$

Here, the first bit $1$ divides the $4$ blocks into two sets of $2$ blocks. Since this bit is a $1$ , this means that the last two blocks are $Old$ when compared to the first two blocks. The third bit is a $0$ . This means that within the last two blocks, the first block is $Old$ when compared to the second block. Notice that the first bit is inconsequential in determining the Least Recently Used block. Within the first two blocks any block can be $Old$ or $Recent$ . This bit is marked as an $x$ . Thus, for both configurations $100$ and $110$ , the third block is the Least Recently used.

State $1x1$

Here, the first bit $1$ divides the $4$ blocks into two sets of $2$ blocks. Since this bit is a $1$ , this means that the last two blocks are $Old$ when compared to the first two blocks. The third bit is a $1$ . This means that within the last two blocks, the second block is $Old$ when compared to the first block. Notice that the first bit is inconsequential in determining the Least Recently Used block. Within the first two blocks any block can be $Old$ or $Recent$ . This bit is marked as an $x$ . Thus, for both configurations $101$ and $111$ , the last block is the Least Recently used.

When a cache block is referenced through a hit or a block replacement, the branch of the tree from the root to this leaf cache block gets populated with $Recent$ . This does affects the recency of other nodes along this branch, hence the approximation.

Block 0

When the first block is referenced, the edges from the root to this block get populated with $Recent$ . The complementary edges get populated with $Old$ . This process sets the first two bits to $1$ . Notice that this process does not affect the third bit. It remains unchanged. This is marked as a $-$ . Thus, when the first block is referenced, the state changes to $11-$ .

Block 1

When the second block is referenced, the edges from the root to this block get populated with $Recent$ . The complementary edges get populated with $Old$ . This process sets the first bit to $1$ and the second bit to $0$ . Notice that this process does not affect the third bit. It remains unchanged. This is marked as a $-$ . Thus, when the second block is referenced, the state changes to $10-$ .

Block 2

When the third block is referenced, the edges from the root to this block get populated with $Recent$ . The complementary edges get populated with $Old$ . This process sets the first bit to $0$ and the third bit to $1$ . Notice that this process does not affect the second bit. It remains unchanged. This is marked as a $-$ . Thus, when the third block is referenced, the state changes to $0-1$ .

Block 3

When the last block is referenced, the edges from the root to this block get populated with $Recent$ . The complementary edges get populated with $Old$ . This process sets the first and third bit to $0$ . Notice that this process does not affect the second bit. It remains unchanged. This is marked as a $-$ . Thus, when the last block is referenced, the state changes to $0-0$ .

The Beard Sage