A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a…
2006
A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional array of size 512×512 with elements that occupy 8-bytes each. Consider the following two C code segments, P1 and P2. P1:
for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x += A[i][j];
}
}
P2:
for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x += A[j][i];
}
}
P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2 . The value of the ratio M1/M2 is:
- A.
0
- B.
1/16
- C.
1/8
- D.
16
Attempted by 146 students.
Show answer & explanation
Correct answer: B
Key facts:
Cache size = 32 KB, block size = 128 B ⇒ number of cache lines = 32 KB / 128 B = 256.
Array element size = 8 B ⇒ elements per block = 128 B / 8 B = 16 elements per block.
Each row has 512 elements ⇒ blocks per row = 512 / 16 = 32 blocks (i.e., 4 KB per row).
Misses for P1 (row-major traversal):
Inner loop scans contiguous elements in a row. Each block provides 16 consecutive elements, so each block causes one miss when first accessed and then 15 hits.
Misses per row = 32. Number of rows = 512 ⇒ M1 = 512 * 32 = 16,384 misses.
Misses for P2 (column-major traversal):
Successive accesses A[j][i] move one row at a time. Row size in bytes = 512 * 8 B = 4,096 B, so the stride between successive elements is 4,096 B, which is much larger than the block size (128 B).
Therefore each access in the inner loop touches a different block and causes a miss. Misses per column = 512. Number of columns = 512 ⇒ M2 = 512 * 512 = 262,144 misses.
Compute the ratio:
M1 = 16,384 and M2 = 262,144 ⇒ M1/M2 = 16,384 / 262,144 = 1/16.
Final answer: 1/16