Question

Consider the C program shown below int i int a [1024 1024] int x = 0; for (iso; i 1024, i++) { x = x + a[i] + a[1024 * i]; Suppose the code above is executed on a system with a direct mapped 16 KB data cache with block size 4. Assume that the address of matrix starts at o and I and x are in registers and initially the cache is empty. a) b) What is the miss rate of the cache? Suggest method to reduce the miss rate for the cache? Recalculate the miss rate based on your suggestion

Answer 1

Solution:

a is solved, please repost b.

Number of blocks in the cache = 16 KB/4 B = 4K

means we have 4*1024 = 4096 blocks in the cache

a)

Array size is 1024*1024 = 2^20

Initially, there will be a miss and when particular accessed element is not in the cache but after the access it will be placed in one of the 4096 blocks in the cache

the cache will start accessing elements 0, 1, 2, 3, .....1024

so these elements start to get stored in the cache along with a[1024 * i] will save the elements 1024, 2048, 4096, 8192, .... in the cache

at i = 0 one miss and one hit will be there

x + a[i] + a[1024* i]

as soon as data for a[0] is accessed for one the second one will get a hit

after that

from 1 to 1023 all cache misses

Total number of cache miss = 1023 + 1024 = 2047

Miss rate= 2047/4096

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)