| This dissertation studies the caching problem in a restricted cache where each memory item can be placed in only a restricted subset of cache locations. Examples of restricted caches in practice include victim caches, assist caches, and skew caches. Restricted caches differ fundamentally from traditional set-associative caches because the exact location that an item is placed in the cache is important. This fact greatly complicates the scheduling problems for restricted caches.; We first consider the off-line restricted cache scheduling problem. This problem is closely related to restricted interval scheduling. We show that any interesting version of restricted interval scheduling is NP-complete and also APX-complete, meaning that is hard to approximate.; We then study the on-line restricted cache scheduling problem. We focus on companion caches, the simplest restricted cache. Companion caches include victim caches and assist caches as special cases. We show that the commonly studied Least Recently Used (LRU) algorithm is not competitive unless cache reorganization is allowed while the performance of the First In First Out (FIFO) algorithm is competitive but not optimal. We present two near optimal algorithms for this problem as well as lower bound arguments. We also extend these results to more complicated restricted caches, such as the skew cache.; Finally we present a model to measure the flexibility of cache designs as a means to compare different cache designs independent of scheduling algorithms and input sequences. The model is based on the concept of working sets, and the probability that working sets of different sizes will fit into a given cache. |
