Consider the following two loops, written in C:

Loop A

sum = 0;

for (i = 0; i < 256; i++)

for (j = 0; j < 16; j++){

sum += A[i][j];

}

Loop B

sum = 0;

for (j = 0; j < 16; j++)

for (i = 0; i < 256; i++){

sum += A[i][j];

}

Here, A is a matrix of 256 rows and 16 columns, where each element of the array is a 32-bit integer (i.e., int A[256][16]; ). The first element of A is stored at memory address 0. Recall that in C, arrays are stored in row-major order. This means that the consecutive elements of a row reside next to each other in memory, as shown in the following memory layout:

Memory address: 0, 4, 60, 64, 4*(16*255+15)

Array elements: (A[0][0]) (A[0][1]) () (A[0][15] A[1][0]) () (A[255][15])

Here, A[i][j] resides in memory location 0 + [4*(16*i + j)]. In this question, we assume that a machine word is 4 bytes, a memory block holds 16 bytes and the memory is byte-addressable. We also assume the data caches are initially empty, and only accesses to A lead to memory accesses (as all other variables are stored in registers) 5.1 A compulsory cache miss happens the first time the CPU reads any bytes in a memory block from the main memory. Should this happens, the entire memory block will be brought into the cache.

1.How many compulsory misses in the data cache will occur when running Loop A? Give your answer as a base 10 number (and only write down the number).

2 . Consider a direct-mapped cache that holds 256 bytes of data. What is the total number of data cache misses (including compulsory misses) when running Loop A? Give your answer as a base 10 number (and only write down the number).

3. Consider the same 256-byte direct-mapped cache as question 5.2. What is the total number of data cache misses (including compulsory misses) when running Loop B? Give your answer as a base 10 number (and only write down the number).

4. What is the minimum number of cache lines required for the data cache if Loop A is to run without any cache misses other than compulsory misses? Give your answer as a base 10 number (and only write down the number).

5. What is the minimum number of cache lines required for the data cache if Loop B is to run without any cache misses other than compulsory misses? Give your answer as a base 10 number (and only write down the number).

6. Consider now a fully-associative cache with 256 lines. The cache uses a first-in/firstout (FIFO) replacement policy. How many misses (including compulsory misses) will occur when running Loop B? Give your answer as a base 10 number (and only write down the number).