Computer System Architecture - Memory Hierarchy
A CPU has a 32 KB direct mapped cache with 28-byte block size. Suppose A is a two dimensional tray 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 [i] [j];
}
}
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
- Option : C
- Explanation : [P2] runs the loops in a way that access elements of A in r ow major order and [P2] accesses elements in column major order.
No of cache blocks = Cache Size/Block Size
= 32KB / 128 Byte = 256
No. of array elements in Each Block
= Block Size/Element Size
= 128 Byte / 8 Byte = 16
Total Misses for [P1] = ArraySize * (No. of array elements in Each Block) / (No of cache blocks) = 512 * 512 * 16/256
= 16384
A CPU has a 32 KB direct mapped cache with 28-byte block size. Suppose A is a two dimensional tray 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 [i] [j];
}
}
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
37. The value of the ratio M1 /M2 is
- Option : B
- Explanation : Total Misses for [P1] = ArraySize * (No. of array elements in Each Block) / (No of cache blocks)
= 512 * 512 * 16 / 256 = 16384
Total Misses for [P2] = Total Number of elements in array (For every element, there would be a miss)
= 512 * 512 = 262144.
Ration M1/M2 = 16384 / 262144 = 1/16.
Consider a machine with a byte addressable main memory of 216 bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100 H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two access.
38. How many data cache misses will occur in total?
- Option : C
- Explanation : Size of main memory = 216 bytes
Size of cache = 32 * 64 Bytes = 211 Bytes
Size of array = 2500 Bytes
Array is stored in main memory but cache will be empty
Size of cache = 2048 Bytes
So number of page faults = 2500 – 2048
= 452
Complete array will be access twice
So for second access no. of total page faults
= 452 * 2
= 904
So total page faults = 452 + 904
= 1356
So data cache misses will be 56
Consider a machine with a byte addressable main memory of 216 bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100 H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two access.
- Option : B
- Explanation : Since the cache has 2c blocks and there are 2 blocks per set, the cache thus has c sets. So, block k of the main memory would map to block (k mod c) of the cache.
