Computer Organization And Architecture MCQ - Memory Hierarchy

31 A CPU has a 32 kB direct mapped cache with 128-byte block size. Suppose A is a two dimensional array of size 512 x 512 with elements that occupy 8-bytes each. Consider the following two C code segments, Pl 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 M₁ and that for P2 be M₂.

The value of the ratio M₁/M₂ is

When A [0] [0] is accessed, block from A [0] [0] to A [0] [15] is brought into the cache but it is of no use as the next element required to access will be A [1] [0].
Thus there will not be a single hit and all 512.512 = 262144 accesses will be misses.
∴ M1 / M2 = 16384/262144 = 1/16

32 Consider a system with 2 level cache. Access times of Level 1 cache, Level 2 cache and main memory are 1 ns, 10 ns, and 500 ns, respectively. The hit rates of Level 1 and Level 2 caches are 0.8 and 0.9, respectively. What is the average access time of the system ignoring the search time within the cache?

First, the system will look in cache 1. If it is not found in cache 1, then cache 2 and then further in main memory (if not in cache 2 also).
The average access t i me would take into consideration success in cache 1, failure in cache 1 but success in cache 2, failure in both the caches and success in main memory.
Average access time
= [H₁ * T₁] + [(1 – H₁) * H2* T2]+ [(1 – H₁)(1 – H2) * Hm * Tm]
where,
H₁ = Hit rate of level 1 cache = 0.8
T₁ = Access time for level 1 cache = 1 ns
H2 = Hit rate of level 2 cache = 0.9
T2 = Access time for level 2 cache = 10 ns
Hm = Hit rate of Main Memory = 1
Tm = Access time for Main Memory = 500 ns
So, Average Access Time
= (0.8 * 1) + (0.2 * 0.9 * 10) + (0.2 * 0.1 * 1 * 500)
= 0.8 + 1.8 + 10
= 12.6 ns

33 Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is 8, 12, 0, 12, 8

34 A cache line is 64 bytes. The main memory has latency 32ns and bandwidth 1 GB/s. The time required to fetch the entire cache line from the main memory is

For 1 GBps bandwidth  it takes 1 sec to load 109 bytes on line
so, for 64 bytes it will take 64 * 1 /109 = 64 ns main memory latency given is 32
so, total time required to place cache line is 64 + 32 = 96 ns

35 A CPU has a cache with block size 64 bytes. The main memory has k banks, each bank being c bytes wide. Consecutive c-byte chunks are mapped on consecutive banks with warp-around. All the k banks can be assessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes k/2 ns. The latency of one bank access is 80 ns. If c = 2 and k = 24, then latency of retrieving a cache block starting at address zero from main memory is

The main memory consists of 24 banks, each of 2 bytes. Since parallel accesses t o all banks are possible, only two parallel accesses of all banks are needed to traverse the whole data.
For one parallel access,
Total time = Decoding Time + Latency Time
= 24/2 + 80
= 92ns
Hence, for 2 such accesses,
time = 2 * 92
= 184 ns