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 50 × 50 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.
How many data cache misses will occur in total?
- A.
40
- B.
50
- C.
56
- D.
59
Attempted by 81 students.
Show answer & explanation
Correct answer: C
Key data: 16-bit address space (2^16 bytes); cache: 32 lines × 64 bytes; block offset = 6 bits, index = 5 bits.
Array size = 50 × 50 = 2500 bytes → number of 64-byte blocks = ceil(2500 / 64) = 40 blocks.
Starting address 1100H = 4352 decimal. Block number of start = 4352 / 64 = 68 (so the array occupies blocks 68 through 107).
Cache is direct-mapped with 32 lines, so a block maps to cache line = block number mod 32. For blocks 68..107, note that blocks 68..75 map to the same indices as blocks 100..107 (they form 8 conflicting pairs).
First traversal: each of the 40 blocks is loaded once the first time it is accessed → 40 misses (compulsory misses for these blocks).
Cache state after first traversal: the later blocks in each conflicting pair (blocks 100..107) occupy those 8 lines, so the earlier blocks 68..75 have been evicted.
Second traversal (same order): for each of the 8 conflicting pairs, when the earlier block (e.g., block 68) is accessed it misses and reloads, evicting its later partner (e.g., block 100); when the traversal later reaches that partner, it also misses. Thus each conflicting pair causes 2 misses in the second traversal, giving 8 × 2 = 16 misses. Blocks that do not have a conflicting partner remain in cache and hit.
Total misses = first traversal misses (40) + second traversal misses (16) = 56.
Answer: 56 cache misses in total.