Direction: A CPU has a 32 kbyte direct mapped cache with 128-byte block size. Suppose A is a two-dimensional array of size 512 × 512 with elements that occupy 8-byte 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
-
- zero
- 2048
- 16384
- 262144
- zero
Correct Option: C
Given loop P1 accesses array A row wise & P2 access column wise.
M1 = ? Cache Capacity = 215 B.
1 element = 23 B
Total elements 512 × 512
Total data = 512 × 512 × 8 B = 221 B
Block size = 128 B
1 block can have = 128/8 = 16 elements
So total blocks require =( 512 × 512 )/16 = 1638 blocks
Since the memory is initially empty so all blocks are required at least once.
So, M1 = 16384
Hence (c) is correct answer.
