Random-LRU: A Replacement Policy for Chip Multiprocessors - VLSI Design and Test - page 207

proposals implemented their replacement policy for the entire set. In our pro-
posal we have not implemented LRU policy for the entire set. We use random
replacement policy, which has no additional hardware requirement, for some
number of ways (min 50%) and LRU for the remaining ways in a set. Note that,
any local replacement policy is implemented for each set separately and so is
true in our case also.

3 Random-LRU

During the block eviction phase, a cache line from RP is randomly selected
as the victim block (say V 1 ) and replaces it with the newly arrived block. But
instead of removing the victim block ( V 1 ) completely from the cache it is moved
to LP and inserted into the MRU position. To move the victim block ( V 1 )into
LP ,ablockfrom LP may need to be evicted. In such a situation the LP will
select its own LRU block as victim block and replace it with the block V 1 .Here
the LRU block means the oldest block in LP . For example, in case of a 8-way set
associative cache if we consider 4 ways for RP then the replacement algorithm
applies only on the remaining 4 ways. When a block in LP accessed again, it
is moved into RP and another random block from RP is moved into LP .In
this way we always maintain the initial allocated size of both RP and LP .
Moving the randomly selected victim block from RP to LP gives a high priority
block another chance to remain in the cache. Also choosing a random block from
RP partially solves the two major issues of LRU based policies (as discussed in
Section 1).
Though the LP section can use any replacement algorithm in this work we
only consider LRU as the replacement algorithm. The hardware cost of true LRU
is relatively high but using LRU only for a subset of ways, we can able to reduce
a huge amount of hardware cost. For the remaining discussion in this section we
consider that the cache is N -way set-associative and out of N ways, LP n ways
are for LP .Let RP n (= N − LP n )waysarefor RP .

3.1 Logical Block Movement and LRU Implementation

As we mentioned earlier, in case of random-LRU the blocks may need to be
moved between LP and RP within the same set. Such kind of physical movement
of blocks can be done in the background without affecting the performance of
the cache. But it consumes some additional energy. As our main intention is to
reduce the energy and hardware complexity we use a concept of logical block
movement. In this technique each way in a set has a bit ( isLP ) to indicate
whether the way belongs to LP or not. For any cache line if isLP bit is set to
1 then the block belongs to LP and otherwise belongs to RP . Initially for each
set the isLP bit of LP n ways are set as 1 and RP n ways as 0. The ways are
randomly distributed over the two sections and they may not be contiguous.
Whenever we want to move a block from RP to LP , we just set its isLP bit
as 1. Similarly whenever we want to move a block from LP to RP we reset its