Consider a machine with a 2-way set associative data cache of size 64 Kbytes…
2008
Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes. A program to be run on this machine begins as follows:
double ARR[1024][1024];
int i, j;
/* Initialize array ARR to 0.0 */
for (i = 0; i < 1024; i++)
for (j = 0; j < 1024; j++)
ARR[i][j] = 0.0;The size of double is 8 bytes. Array ARR is located in memory starting at the beginning of virtual page 0XFF000 and stored in row-major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR.
The cache hit ratio for this initialization loop is
Answer: C. 50% — Concept: In a linear scan of an array of fixed-size elements, one cache block holds k = (block size) / (element size) consecutive elements. With an initially…
- A.
0%
- B.
25%
- C.
50%
- D.
75%
Attempted by 215 students.
Show answer & explanation
Correct answer: C
Concept: In a linear scan of an array of fixed-size elements, one cache block holds k = (block size) / (element size) consecutive elements. With an initially empty cache, no prefetching, and the usual write-allocate policy, the first access that touches a block misses and loads the whole block, and the remaining k − 1 accesses to that same block hit.
So for a sequential traversal the hit ratio is (k − 1) / k. It depends only on how many elements fit in one block — associativity and total cache size matter only if a block were evicted before all of its elements were used.
Application
Elements per block: k = 16 bytes / 8 bytes = 2 consecutive double values sit in one cache block.
Access order: ARR is stored in row-major order and j is the inner-loop index, so the program writes ARR[i][0], ARR[i][1], ARR[i][2], … in increasing address order — one pure linear scan over 1024 × 1024 = 1,048,576 doubles.
Alignment: ARR starts at the beginning of virtual page 0xFF000. A page boundary (4 Kbytes) is a multiple of 16 bytes, so the first element is block-aligned and each block holds exactly one pair ARR[i][2t], ARR[i][2t+1].
Blocks touched: 1,048,576 / 2 = 524,288 distinct blocks. Within each pair the first write misses and loads the block; the second write finds its data already there.
Totals: hits = 524,288, misses = 524,288, references = 1,048,576.
Hit ratio = 524,288 / 1,048,576 = 1/2 = 50%.
Cross-check: Substituting k = 2 into (k − 1) / k gives (2 − 1) / 2 = 50%, which matches the count. Capacity is not the limiting factor either: the cache holds 64 Kbytes / 16 bytes = 4096 blocks in 4096 / 2 = 2048 sets, whereas the loop needs only the current block live at any instant, and consecutive blocks fall in different sets, so a block is never evicted between its two accesses.
Why the other values do not arise
0% is the ratio under a no-write-allocate policy, where a store that misses writes straight through and never installs the block. The stem does not name the write-miss policy, and the standard convention taken for this item is write-allocate, under which the second write of each pair does find its block already loaded.
25% would mean one hit in every four references, which needs three of every four elements to be absent — not possible when a block already supplies the very next element.
75% would mean three hits in every four references, which needs k = 4, i.e. 32-byte blocks holding four doubles, not the 16-byte blocks given.
Result: One miss followed by one hit for every pair of consecutive doubles gives a hit ratio of 50% for this initialization loop.