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
- A.
0%
- B.
25%
- C.
50%
- D.
75%
Attempted by 114 students.
Show answer & explanation
Correct answer: C
Answer: 50%.
Key idea: A single cache line brings multiple consecutive elements into the cache. If the loop initializes elements sequentially and the cache is cold at the start, the first access to each cache line misses and the subsequent access to the other element(s) in that line hits.
Assume there are N elements stored contiguously and one cache line holds two consecutive elements.
Total memory accesses during initialization = N (one access per element).
Number of distinct cache lines touched = N / 2 (each line covers two elements).
Misses = one miss per cache line = N / 2. Hits = total accesses − misses = N − N/2 = N/2.
Hit ratio = hits / total accesses = (N/2) / N = 1/2 = 50%.
Assumptions: sequential access order, cold cache at start, and a cache line that holds two elements. If the cache line size or access pattern changes, the ratio will change accordingly.