The cache is an important component of the memory system of workstations and mainframe computers, and its performance often a critical factor in the overall performance of the system. The advent of RISC processors and VLSI technology have driven down processor cycle times and made frequent references to main memory unacceptable.
The higher miss rate of direct-mapped caches is mitigated by their smaller hit access times. A set-associative cache of the same total size always displays a higher hit access time because an associative search of a set is required during each reference, followed by a multiplexing of the appropriate data word to the processor. Although direct-mapped caches offer the best cost-performance in workstations, the large number of interference misses that occur in direct-mapped caches are still a major problem. These interference misses can be largely eliminated by implementing control logic which makes better use of cache area. The challenge is determining a simple, area-efficient cache control algorithm to reduce the number of iterference misses and to boost the performance without increasing the degree of associativity. This has led several researchers to suggest ways to achieve miss rates similar to two-way set-associative caches with fast access times by using modified direct-mapped caches that use a serialized or sequential search to compare tags in set-associative caches.
Two such proposed caches are the CA cache and the PSA cache. The CA cache resolves conflicts by allowing alternate hashing functions, which results in significantly better use of cache area and access times very similar to two-way set associative caches. But, the CA cache requires that entire cache blocks be exchanged because the special cache allocation and re-allocation policies. Instead PSA cache uses a dynamic probe ordering with the ``most recently used'' (MRU) information based on [5]. The PSA cache uses a steering bit table (SBT) to guide data access and a prediction index to select a particular steering bit.