Download The Cache Visualisation Tool

architecture
direct-mapped
2-way SA
4-way SA
8-way SA
Cache Size
1 KB 4 KB 16 KB 64 KB
0.690
0.710
0.798
0.798
0.321
0.293
0.236
0.253
0.220
0.206
0.207
0.211
0.208
0.206
0.206
0.206
Figure 5.7: Miss ratios with respect to cache size and set associativity.
part of the conict misses should be extracted. The opposite became true; increasing the set associativity
for a 1KB cache can also increase the miss-ratio! The bigger caches conrm this view; increasing the set
associativity will not always decrease the miss-ratio. How can we explain this phenomenon? Let us create
one very simple example where direct-mapped cache causes less misses than a 2-way set-associative cache:
Suppose we have three data-items of 4 bytes each and a cachesize of 8 bytes and two cachelines. Call
these three data items A, B and C with addresses 0, 4 and 8 respectively. We have the following reference
pattern ABCABCABC.... In a direct-mapped cache data-item A and C will show cross-interference in the
rst cacheline, but data-item B in the second cacheline will be reused every time it is referenced. Now we
have a 2-way set-associative cache and a LRU-replacement policy. As you will see with this same reference
pattern, there will not be any reuse at all! This could be improved by changing the replacement policy to
Most Recently Used, which performs in this case much better, but still the performance evaluation can be
better for direct-mapped cache.
In this section we will demonstrate the basic usage of the tool for testing hardware architectures. We
will use a simple program; a nested loop with four arrays in the innerloop.
ArrayA 0 1,100
ArrayB 420 1,100
ArrayC 940 1,100
ArrayD 613 1,100;1,100
DO I = 1,100,1
DO J = 1,100,1
S1 : R ArrayB 1*J
S2 : R ArrayA 1*J
S3 : R ArrayC 1*J
S4 : W ArrayA 1*I
S5 : W ArrayD 1*J,1*I
ENDDO
ENDDO
Figure 5.8: Loaded test program
In order to illustrate this example in the tool, we will need to understand the reference patterns to the
arrays. There will 10,000 iterations causing 50,000 references; each element of array B and C is referenced
100 times, the 10,000 elements of array D will be referenced only once and every element of array A is
referenced 200 times (see gure 5.9). Notice that when one array-element ts into one cacheline, there can
not be any spatial locality in this DO-loop. Though, there is a lot of spatial locality when we increase the
cacheline size as we will see in section 5.8.2. Array A, B and C might exploit some temporal locality, when
data is not ushed after 100 iterations.
To illustrate the dierence between set associative caches and a direct-mapped cache it is important to
see what the address-range is of a cache; The addresses in a 1 KB direct-mapped cache, range between 0 and
1024 bytes. The addresses in a 1 KB 2-way S.A.-cache range between 0 and 512 bytes, but can be placed in
two equivalent sets.
78