Mark Brehob and Stephen K. Wagner and Eric Torng and Richard J. Enbody
June, 2000
When examining a new cache structure or replacement policy, it is often helpful to use the optimal policy as a baseline. In this paper we prove that it is NP-hard to find the optimal schedule for any but the simplest of caching schemes. We prove this by a reduction from 3-Occ-Max-2SAT, a known NP-hard problem. We also show that there is no polynomial time algorithm which is guaranteed to find a ``good'' approximation to this problem unless $P=NP$. Our results apply to cache structures that include a victim cache or an assist cache, as well as skew caches and nearly all ``multi-lateral'' caches. This result also applies to the optimal scheduling of multi-level cache structures.
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format.