Optimal mapping in direct mapped cache environments

In this paper the authors 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, the authors break the general positioning problem into two, the collision minimization and the grouping problems and show optimal algorithms for both problems. Using these algorithms they derive an optimal algorithm for the general positioning problem. Since the optimal positioning is of very special structure the authors consider other, less restricted, positionings. They 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. The authors find an optimal assignment for the special case of the pair assignment. In addition they 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. The authors 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.