Consider the code fragment shown below: int M[16]; for(int i=1; i<=2; i++) for(i
ID: 673011 • Letter: C
Question
Consider the code fragment shown below:
int M[16];
for(int i=1; i<=2; i++)
for(int j=1; j<16; j=j+3)
x = M[j] + 1;
Assume the following:
Memory is arranged in bytes, with one word = 4 bytes.
Array M[] starts at memory address 0, i.e., M[0] is at address 0, M[1] at address 4, etc.
The program is run on a machine with a direct-mapped cache that has 2 word (8 byte) blocks, and holds 32 total bytes (4 blocks) of data.
References to i, j and x don’t touch the cache (e.g., these variables use fixed registers allocated to them); we only care about array M[].
Assume the cache starts empty.
What is the miss rate in this cache for this code?
Explanation / Answer
As the cache is of 32 bytes(4 blocks), it can accomodate 8 array variables at a time, as each varaible is of size 4 bytes.
As per the loop,
for(int i=1; i<=2; i++)
for(int j=1; j<16; j=j+3)
x = M[j] + 1;
The order in which it accesses the variables is:
i = 1: j = 1, 4, 7, 10,13.
i = 2: j = 1, 4, 7, 10, 13.
Therefore, the order in which the processor accesses the variables and its hit/miss possibility is:
M[1] - Miss, and will be placed into the cache.
M[4] - Miss, and will be placed into the cache.
M[7] - Miss, and will be placed into the cache.
M[10] - Miss, and will be placed into the cache.
M[13] - Miss, and will be placed into the cache.
Again, retrieving the same variable for the second time(when i = 2), leads to a hit for all the 5 variables, as they are placed in the cache when they are accessed for the first time.
So, the number of misses are 5, where as the number of hits are also 5.
Therefore the miss rate for this code is: 50% (0.5)