# 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 leaves will have internal nodes. Thus blocks in a set will require bits to approximate LRU. Each node (and corresponding bit) encodes the information about which child node is and which child node is . Let represent that the left side has been referenced more recently than the right side, and vice-versa.

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

## State

Here, the first bit divides the blocks into two sets of blocks. Since this bit is a , this means that the first two blocks are when compared to the last two blocks. The second bit is also a . This means that within the first two blocks, the first block is 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 or . This bit is marked as an . Thus, for both configurations and , the first block is the Least Recently used.

## State

Here, the first bit divides the blocks into two sets of blocks. Since this bit is a , this means that the first two blocks are when compared to the last two blocks. The second bit is a . This means that within the first two blocks, the second block is 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 or . This bit is marked as an . Thus, for both configurations and , the second block is the Least Recently used.

## State

Here, the first bit divides the blocks into two sets of blocks. Since this bit is a , this means that the last two blocks are when compared to the first two blocks. The third bit is a . This means that within the last two blocks, the first block is 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 or . This bit is marked as an . Thus, for both configurations and , the third block is the Least Recently used.

## State

Here, the first bit divides the blocks into two sets of blocks. Since this bit is a , this means that the last two blocks are when compared to the first two blocks. The third bit is a . This means that within the last two blocks, the second block is 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 or . This bit is marked as an . Thus, for both configurations and , 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 . 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 . The complementary edges get populated with . This process sets the first two bits to . 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 .

## Block 1

When the second block is referenced, the edges from the root to this block get populated with . The complementary edges get populated with . This process sets the first bit to and the second bit to . 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 .

## Block 2

When the third block is referenced, the edges from the root to this block get populated with . The complementary edges get populated with . This process sets the first bit to and the third bit to . 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 .

## Block 3

When the last block is referenced, the edges from the root to this block get populated with . The complementary edges get populated with . This process sets the first and third bit to . 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 .