Okay, so
how often can we expect to guess correctly in a way prediction cache?
We can get an idea for this by looking at the smaller direct mapped cache.
Basically, let's say we have a two way set associative cache.
Each set of this cache has two ways, two lines in it.
And by doing way prediction, we are effectively using one of these at first.
And only if we don't find it there, we look at the other one.
So effectively, a way prediction cache
first tries to access what looks like a smaller direct mapped cache.
Then it will try the entire set associative cache.
So we can get a pretty good estimate for the hit rate and hit latency and so
on of a way prediction cache, if we look at the direct mapped cache and
the set associative cache.
So let's look at the basic 32 kilobyte, 8-way set associative cache.
Let's look at its hit rate, hit latency, miss penalty, and the over AMAT.
And we will also look at a 32 kilobyte,
8-way set-associative cache with way prediction.
The hit rate of this cache, let's say its around 90%.
The hit latency might be 2 cycle because it's highly associative.
The miss penalty will be 20 cycles, for example.
And the overall AMAT would then be 2 for the hit latency,
plus 10% of the time we have the miss penalty.
And we get 4 here.
Now we already said that way prediction
behaves like accessing only one of the ways in the cache.
With way prediction in a 8-way associative cache,
we are really guessing which of the 8 places is going to have the block.
So you effectively, with way prediction, our first attempt will
be to a 4 kilobyte direct mapped subset of this cache.
If we look at the normal 4 kilobyte direct mapped cache,
that's going to have, for example, a 70% hit rate,
but the 1 cycle hit latency, because it's faster.
And the miss penalty will be the same.
If we now try to get the AMAT for this basic direct mapped cache,
we will have 1 + 0.3, the miss rate,
times 20, and this is going to be 1 plus 6 so it gives us 7.
So obviously we are better off with a 8 way set associative cache.
However, we are paying an extra cycle each time we access it for
the hit latency in order to get the low missed penalties here.
With the way prediction cache, what we're getting is 70% of the time
we're going to find what we're looking for in the 4 kilobyte subset that we
are checking first and we will have a 1 cycle latency for that.
In the remaining 20%, we're going to check the rest of the cache so
our overall hit rate will be 90%.
What we don't find here,
we will still find here if it's in the 32 kilobyte cache.
So we get a 90% hit rate overall.
Our hit latency is now 1 or 2.
And our miss penalty is 20, so how do we compute the AMAT?
Well, what we now have is that 70% of the time,
we find what we are looking for in one cycle.
The other 30% of the time, whether we have a hit or
a miss in the 8-way cache, we have to check it.
So the other 30% of the time we're checking all of the ways for
which we pay a 2 cycle latency, and then 10% of the time we don't find what
we are looking for in all of the ways, so we have to pay the miss penalty.
So now we have what looks like our hit time.
70% of the time, it's 1.
30% of the time, we have to use a 2, so
we end up having a 1.3 cycle on average hit time.
And a miss penalty of the 8-way set associative cache
which is still going to be 2.
And this is how we improve things, we now get an AMAT of 3.3.
Because what we effectively got was the misses of an 8-way
set associative cache, but the hit time that is much closer to
a direct mapped cache then it is to an 8-way set associative cache.