A more desirable cache design would reduce the interference miss rate to the same extent as a set-associative cache, but at the same time, it would maintain the critical hit access path of the direct-mapped cache. The hash-rehash cache (HR) [3] answers this problem but has a serious drawback, which is addressed by CA cache. The CA cahe and the HR cache use two distinct hashing functions, which is realised as a simple bit selection and bit flipping for simplicity, speed, ease of design and implementation and also immediate hash computation. This also provides two identically distributed hash and rehash functions. The index obtained by the hashing function is performed with bit selection and denoted by b[a], where a is the address of the data. And the rehash function is obtained by bit flipping and denoted by f[a]. If b[a] indexes to valid data, a first-time hit occurs; if it misses, f[a] is then used to access the cache. If a second-time hit occurs, the data is retrieved. The data in the two cache lines are then swapped so that the next access will likely result in a first-time hit. However, if the second access also misses, then the data is retrieved from main memory, placed in the cache line indexed by f[a], and swapped with the data in the first location.
Usually, the high-order bit of the index field is used for the hashing and rehashing functions. As bit flipping is used as the rehashing (or second hashing function), the tag fields of two addresses may be identical, even though they vary in the high-order bit. To avoid this, the higher-order bit of the index field is added to the tag. This scheme is assumed to be in place whenever bit flipping is used.
While, the HR cache functions simply as above, it has a serious drawback. A rehash is attempted after every first-time miss, which can replace potentially useful data in the rehashed location, even when the primary location had a potentially inactive block. This effect where inactive data may be swapped out, when useful data is clobbered, is called secondary thrashing by Agarwal et al. [2].
In the CA cache, the key to implementing column associativity effectively is inhibiting a rehash access if the location reached by the first-time access itself contains a rehashed data block. Every cache set contains an extra bit which indicates whether the set is a rehashed location, that is, whether the data in this set is indexed by f[a]. When a cache set must be replaced, a rehashed location is always chosen--immediately if possible. If the first time access is a miss, then the rehashed-location bit of that set is checked. If it has been set to one, then no rehash access will be attempted, and the data retrieved from memory is placed in that location. Then the rehash bit is reset to zero to indicate that the data in this set is to be indexed by b[a] in the future. On the other hand, if the rehash bit is already a zero, then upon a first-time miss the rehash access will continue. It is to be noted that if the second-time miss occurs, then the set whose data will be replaced is again a rehashed location, as desired. At start-up, all of the empty cache locations should have their rehash bits set to one.
The CA cache does not use the LRU replacement policy, but with the rehash bit has a high hit first-time hit rate. Calder et al. in their Predictive Sequential Associative cache (PSA) [1] show the failure of the CA cache, on a particular scheme of accesses, and argue that the LRU-replacement policy is the best to minimize misses. They put forward the PSA cache, which follows the LRU-replacement policy as in the MRU cache [4]. The MRU cache needs the MRU-information in advance to access the most recently used block directly. The PSA cache predicts the index a few cycles earlier using different mechanisms and reads the MRU-information.