PRR: A low-overhead cache replacement algorithm for embedded processors

In embedded systems power consumption and area tightly constrain the cache capacity and management logic. Many good cache replacement policies have been proposed in the past, but none approach the performance of the least recently used (LRU) algorithm without incurring high overheads. In fact, many embedded designers consider even pseudo-LRU too complex for their embedded systems processors. In this paper, we propose a new level 1 (L1) data cache replacement algorithm, Protected Round-Robin (PRR) that is simple enough to be incorporated into embedded processors while providing miss rates that are very similar to the miss rates of LRU. Our experiments showed that on average the miss rates of PRR are only 0.22% higher than the miss rates of LRU on a 32KB, 4-way L1 data cache with 32 byte long cache lines. PRR has miss rates that are on average 4.72% and 4.66% lower than random and round-robin replacement algorithms, respectively.