1. The following code is written in C, where elements within the same row are stored contiguously. Assume each word is a 32-bit integer.
for (I=0; I<8; I++) for (J=0; J<8000; J++) A[I][J]=B[I][0]+A[J][I];
(1) Which variable references exhibit temporal locality?
(2) Which variable references exhibit spatial locality?
2. Below is a list of 32-bit memory address references, given as word addresses:
0x03, 0xB4, 0x2B, 0x02, 0xBF, 0x58, 0xBE, 0x0E, 0xB5, 0x2C, 0xBA, 0xFD
(1) For each of these references, identify the tag and the cache index given a direct-mapped cache with 8 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty. (
(2) For each of these references, identify the tag and the cache index given a direct-mapped cache with two-word blocks and a total size of 4 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.
(3) You are asked to optimize a cache design for the given references. There are three direct-mapped cache designs possible, all with a total of 8 words of data: C1 has 1-word blocks, C2 has 2-word blocks, and C3 has 4-word blocks. In terms of miss rate, which cache design is the best? If the miss stall time is 35 cycles, and C1 has an access time of 2 cycles, C2 takes 3 cycles, and C3 takes 5 cycles, which is the best cache design?
3. For a direct-mapped cache design with a 32-bit byte address, the following bits of the address are used to access the cache.
Tag
Index
Offset
31–10
9–5
4–0
(1) What is the cache block size (in words)?
(2) How many blocks does the cache have?
(3) What is the ratio between total bits required for such a cache implementation over the data storage bits?
Beginning from power on, the following byte addresses for cache references are recorded.
Address
0x00
0x04
0x10
0x84
0xE8
0xA0
0x400
0x1E
0x8C
0xC1C
0xB4
0x884
(4) For each reference, list
a) its tag, index, and offset
b whether it is a hit or a miss, and
c) How many blocks were replaced (if any)?
(5) What is the hit ratio?
(6) Show the final state of the cache, with each valid line represented as <index, tag, data>.
