Optimizing Capacitance and Switching Activity to Reduce Dynamic Power - Computer Architecture Techniques for Power-Efficiency - page 104

data way is accessed. If the MRU way does not yield a hit, the remaining ways are also checked,
again, in two phases. First, the tags are checked for a hit and then only the correct data way
(if any) is accessed for the data. Alternatively, the second step can be combined with the first
step into one (Figure 4.27, right diagram). In this scheme, all tag ways are accessed in the first
step along with the predicted data way. In the case of a misprediction, the correct data way is
known from the tag comparison in the first step and it is accessed in the second (Figure 4.27,
right diagram).
4.9.4 Advanced Way-Prediction Mechanisms
The simplicity and success of the way prediction scheme gave rise to more sophisticated
prediction mechanisms. Two representative proposals are the selective direct-mapping and the
multi-MRU.
Selective direct-mapping : Powell et al. [ 183 ], combine selective direct-mapping (SDM)
[ 23 ] and way prediction in an effort to increase the overall way prediction accuracy. Selective
direct-mapping, initially proposed by Batson and Vijaykumar [ 23 ], was conceived as an en-
hancement on the PSA cache. The initial proposal featuring SDM, called Reactive-Associative
Cache , uses a set-associative organization for tags and a direct-mapped organization for data.
Cache lines are mapped in their direct-mapped positions and are only displaced to alterna-
tive set-associative positions in the case of conflicts. Cache access resembles a phased access
and takes one or two probes to find the data. The first probe, guided by a predictor, accesses
either the direct-mapped position or a predicted set-associative position. Tag match proceeds
in parallel. The second probe only takes place on a misprediction (the data are not found in
their direct-mapped position or the way-prediction was incorrect). At that point, the correct
position of the data is known from the tag comparison results.
SDM increases the chances of finding the desired data in the first probe. Why is that?
In a typical set-associative cache a line can end up anywhere in a set. This is due to the highly
dynamic nature of the associative replacement algorithms. Way prediction has the difficult task
of predicting the position of each cache line among all the equiprobable associative positions.
The problem, of course, worsens as associativity increases. Selective direct-mapping offers a way
out by separating conflicting from non-conflicting cache lines. 9 In essence, SDM pins down
non-conflicting cache lines to known positions (their corresponding direct-mapped positions)
so it is easy to “predict” where they are. In fact, a predictor in SDM only has to supply a prediction
on whether a cache line is conflicting or not. In the case it is conflicting, it is in a set-associative
9 This is achieved by using a conflict list that captures conflicts close in time. Cache lines enter the conflict list when
they are first evicted from the cache, from their direct-mapped positions. Further evictions while in the conflict list
give a cache line the “conflicting line” status and form that point onwards it is displaced in a set-associative position
rather than placed in its direct mapped position.