OPTIMAL MAPPING IN DIRECT MAPPED CACHE ENVIRONMENTS

In this paper we study positioning strategies for improving the perfor mance of a memory system with a direct mapped cache. A positioning tec hnique determines for every program item, (instruction or data), its a ddress in main memory. Assuming the Independent Reference Model, we br eak the general positioning problem into two, the collision minimizati on and the grouping problems and show optimal algorithms for both prob lems. Using these algorithms we derive an optimal algorithm for the ge neral positioning problem. Since the optimal positioning is of very sp ecial structure we consider other, less restricted, positionings. We s how 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 assig nment for the special case of the pair assignment. In addition we look at the expected performance gain of two frequently suggested cache fe atures. The cache bypass feature supports the access of items in memor y 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 determin ed randomly, does not improve the expected hit ratio.