Consider a machine with a byte addressable main memory of 216 bytes. Assume…
2007
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. A 50x50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. 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 accesses.
Consider the data given in above question. Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time?
- A.
line 4 to line 11
- B.
line 4 to line 12
- C.
line 0 to line 7
- D.
line 0 to line 8
Attempted by 117 students.
Show answer & explanation
Correct answer: A
Answer: line 4 to line 11.
Reasoning and method to verify:
Compute block numbers from addresses: blockNumber = floor(address / blockSize).
Map each block to a cache line: cacheLine = blockNumber mod numberOfLines.
Apply these steps to every array access in the second traversal. The resulting cacheLine indices form the set of cache lines that will be used and thus replaced; in this case those indices are 4 through 11.
Why the other ranges are incorrect:
Ranges that start at line 0 are incorrect because the accessed block numbers map to higher cache line indices (starting at line 4 here).
Ranges that extend to line 12 are incorrect because the last accessed block maps to line 11; no access maps to line 12 during the second traversal.
Summary: Using the block-number and modulo mapping steps above on the addresses from the question produces cache line indices 4 through 11, so those are the lines replaced on the second pass.