Question

For the given code snippets, predict the cache hit rate. The cache is 4KB, direct mapped, and has 64-byte cache lines. There are two implementations for the for loops (v1 and v2) which are executed separately in isolation on the same machine. Assume that the:

long variables total_sum and array arr are doublewords

the cache is empty before the loops start executing.

// Version v1

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

for (int j=0; j<256; j++) {

total_sum += arr[i][j];

}

}

// Version v2

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

for (int j=0; j<256; j++) {

total_sum += arr[j][i];

}

}

What is the cache hit rate in Version v1?

What is the cache hit rate in Version v2?

Answer 1

The cache hit rate in Version v1 is determined by how many cache lines are accessed and how many of them result in a cache hit. Similarly, the cache hit rate in Version v2 is also determined by the number of cache lines accessed and how many of them result in a cache hit.

Step-by-step explanation:

The cache hit rate in Version v1 can be calculated by determining how many cache lines are accessed and how many of them result in a cache hit. In this version, the inner loop accesses the elements of the 2D array in a row-major order, which means that each cache line contains consecutive elements in the same row. Since the cache is direct mapped, each cache line can only hold one element, and if another element from the same row is accessed while the cache line is already occupied, it will result in a cache miss. Therefore, in this version, there will be a cache hit for every 256 accesses to the rows.

The cache hit rate in Version v2 can be calculated in a similar way. However, in this version, the inner loop accesses the elements in a column-major order, which means that consecutive elements in the same column will be placed in the same cache line. Since the cache is direct mapped, each cache line can only hold one element, and if another element from the same column is accessed while the cache line is already occupied, it will result in a cache miss. Therefore, in this version, there will be a cache hit for every 256 accesses to the columns.