Question

For the given code snippets, predict the cache hit rate. The cache is 256KB, 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. Assume that the:
a. long variables total_sum and array arr are doublewords
b. 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?

Answer 1

The cache hit rate for Version v1, assuming a 256KB cache, direct-mapped, with 64-byte cache lines, is approximately 87.5%, since the array is accessed row by row, and each cache line would hold 8 elements, resulting in 7 hits and 1 miss per cache line.

Step-by-step explanation:

For a cache that is 256KB, direct-mapped, with 64-byte cache lines, the cache hit rate will greatly depend on how data is accessed. In Version v1 of the code, we iterate over the 2D array row by row, meaning the elements are accessed sequentially. Since a long variable is typically 8 bytes (doubleword), each cache line can hold 8 array elements (64 bytes / 8 bytes per doubleword).

In Version v1, we will get a cache hit for every element after the first element in a cache line is loaded (7 out of 8 times for each cache line, assuming a cold cache at the start). However, we will have a cache miss when loading the first element of every new cache line as we progress through the row. With a 256x256 array and knowing there are 4 cache lines per 256 elements (256 elements * 8 bytes/element divided by 64 bytes/cache line), we would miss once and then hit 7 times for each cache line:

Cache Hits = (256 / 4) * 7 * 256 = 458752

Total Memory Accesses = 256 * 256 = 65536

Cache Hit Rate = Cache Hits / Total Memory Accesses = 458752 / 65536 ≈ 7 / 1 ≈ 7.0

Using this information, we can predict the cache hit rate for Version v1 to be approximately 700% (hitting 7 times for each line). However, this is not possible as the hit rate cannot exceed 100%, indicating that a cache hit rate should always be expressed as a ratio between 0 and 1 or a percentage between 0 and 100%. The correct cache hit rate is 7/8, or 87.5%, because for each cache line after the first element causes a miss, the subsequent 7 elements would be hits.