Please show work so that I may follow steps The following C program is run on a
ID: 666813 • Letter: P
Question
Please show work so that I may follow steps
The following C program is run on a machine with a data chache that has four-word blocks and the data capacity of the data cache is 256 bytes. Assume that only references to the array incur memory accesses and the cache is empty at the very beginning.
int i, c, array[256];
c = 0;
for (i=0; i<256; i++)
{
c = c + array[i];
}
i) How many cache lines are there if the cache is direct mapped?
ii) How many sets are there if the cache is two-way associative? Which address bits are used for indexing the set in a 32-bit address? (Please present the result in Addr[x:y] format)
iii) If a direct mapped cache is used, what is the expected miss rate after program execution?
iv) If a two-way associative cache is used, what is the expected miss rate after program execution?
v) If a four-way associative cache is used, what is the expected miss rate after execution the program.
Explanation / Answer
Solution:
The number of bits in the index field = 6
6 no.of cache lines are needed if the cache is direct mapped.
iii)Assume that array[0] . . . array[3] is in block 0. Then, block 1 has array[4] . . . [7] and block 2 has array[8] . . . [11] and so on until block 63 has [252] . . . [255]. Thus if we look at array[0] and array[256], we are looking at the same cache block. One access will cause the other to miss, so there will be a 100% miss rate.
iv) If the cache is two-way set associative, even if two accesses are in the same cache set, they can coexist, so the miss rate will be 0.
v) If the cache is four-way set associative, even if 4 accesses are in the same cache set, they can coexist, so the miss rate will be 0.