Optimal replacements in caches with two miss costs
Jaeheon Jeong, Michel Dubois · 1999
Cache replacement policies such as FIFO (First-In/First-Out), LRU (Least Recently Used) and OPT (OPTimum) were conceived in the context of uniprocessor systems in which the cost of all cache misses was uniform.With the advent of multiprocessor systems, this uniform cost assumption has lost its validity.In this paper we revisit the problem of designing optimum cache replacement algorithms for CC-NUMA multiprocessors.In CC-NUMAs the cost of a miss mapping to a remote memory is higher in terms of latency, bandwidth, or power consumption than the cost of a miss mapping to the local memory.In general we call the class of replacement algorithms to minimize a non-uniform miss cost function "cost-sensitive replacement algorithms".We evaluate a cost-sensitive optimal replacement algorithm (CSOPT) using a trace-driven simulator and we compare it to OPT, the optimal algorithm assuming uniform miss cost in a CC-NUMA multiprocessor where misses have two different static costs.In this context, CSOPT has more misses than OPT because it may trade off several "cheap" misses for one "expensive" miss, but its overall cost is lower.We run all the SPLASH-2 benchmarks for several configurations of CC-NUMAs andfor cost ratios of up to 32, and observe that CSOPT can improve the cost function by 20% over OPT.This is quite an improvement considering that the benchmarks are finely tuned to run efhciently on CC-NUMA systems.