Optimal mapping in direct mapped cache environments

Abstract

In this paper we study positioning strategies for improving the performance of a memory system with a direct mapped cache. A positioning technique determines for every program item, (instruction or data), its address in main memory. Assuming the Independent Reference Model, we break the general positioning problem into two, the collision minimization and the grouping problems and show optimal algorithms for both problems. Using these algorithms we derive an optimal algorithm for the general positioning problem. Since the optimal positioning is of very special structure we consider other, less restricted, positionings. We show that the quality of a class of natural assignments that distribute the items almost arbitrarily is good as long as the optimal hit ratio is sufficiently large. Another possible requirement is that the items should be distributed as evenly as possible. We find an optimal assignment for the special case of the pair assignment. In addition we look at the expected performance gain of two frequently suggested cache features. The cache bypass feature supports the access of items in memory without loading the item into the cache. We show an assignment with best possible hit ratio. Also it is shown that a cache which employs a random assignment policy, i.e., the assignment of an item is determined randomly, does not improve the expected hit ratio. © 1994 The Mathematical Programming Society, Inc.