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 M1 is:
- A.
0
- B.
2048
- C.
16384
- D.
262144
Attempted by 156 students.
Show answer & explanation
Correct answer: C
Answer: 16384
Reasoning:
Cache size and block calculations:
The cache holds 32 KB = 32768 bytes. With 128-byte blocks, the cache has 32768 / 128 = 256 cache lines.
Array layout and block occupancy:
Each array element is 8 bytes, so each 128-byte block contains 128 / 8 = 16 consecutive elements.
Each row has 512 elements ⇒ row size = 512 × 8 = 4096 bytes ⇒ row uses 4096 / 128 = 32 blocks.
Miss behavior for P1 (row-major traversal):
The inner loop scans elements consecutively along a row, so the first access to each 128-byte block is a miss and the next 15 accesses to elements in that block are hits. Thus there is one cache miss per block when traversing a row.
Misses per row = 32 blocks ⇒ misses per row = 32.
Total rows = 512 ⇒ total misses = 512 × 32 = 16384.
Note on conflicts:
Even though the cache is direct-mapped and blocks from different rows can map to the same cache lines (mapping repeats every 8 rows), this does not increase misses for this traversal because each block in a row is only needed once while scanning that row. Therefore the compulsory misses counted above determine the total.