Part 1. Memory analysis Question 1 (15 pt). You are given designs of 3 caches fo
ID: 3702249 • Letter: P
Question
Part 1. Memory analysis
Question 1 (15 pt). You are given designs of 3 caches for a 16-bit address machine:
D1:
Direct-mapped cache.
Each cache line is 1 byte.
10-bit index, 6-bit tag.
1 cycle hit time.
D2:
2-way set associative cache.
Each cache line is 1 word (4 bytes).
7-bit index, 7-bit tag.
2 cycle hit time.
D3:
fully associative cache with 256 cache lines.
Each cache line is 1 word.
14-bit tag.
5 cycle hit time.
Answer the following set of questions:
a) What is the size of each cache?
b) How much space does each cache need to store tags?
c) Which cache design has the most conflict misses? Which has the least?
d) The following information is given to you: hit rate for the 3 caches is 50%, 70% and 90%
but did not tell you which hit rate corresponds to which cache, which cache would you guess
corresponded to which hit rate? Why?
e) Assuming the miss time for each is 20 cycles, what is the average service time for each?
(Service Time = (hit rate)*(hit time) + (miss rate)*(miss time)).
Explanation / Answer
a) What is the size of each cache?
Direct mapped cache= 2^index * size of cache line= 2^10 * 1B lines = 1KB.
2-way set associative cache= 2^index * size of cache line * 2 ways=2^7 * 4 words *2ways= 128 4B lines * 2 ways = 1KB
Fully associative cache= number of cache lines* size of each line= 256 * 4B lines = 1KB
b) How much space does each cache need to store tags?
Direct mapped cache= 1024 * 6-bit tags = 6Kb
2-way set associative cache= 256 * 7-bit tags = 1792 bits
Fully associative cache= 256 * 14-bit tags = 3584 bits
c) Which cache design has the most conflict misses? Which has the least?
Direct mapped cache has likely the most conflict misses, because it is direct mapped. Fully associative cache has the least since it is fully associative so it can never have conflict misses.
d) The following information is given to you: hit rate for the 3 caches is 50%, 70% and 90% but did not tell you which hit rate corresponds to which cache, which cache would you guess corresponded to which hit rate? Why?
Since the size of all three caches is same size and as we said in the previous answer that direct mapped cache has more conflict misses and fully associative has the least so direct mapped will have 50%, 2-way set associative 70%, and Fully associative will have 90% hit rate.
e) Assuming the miss time for each is 20 cycles, what is the average service time for each? (Service Time = (hit rate)*(hit time) + (miss rate)*(miss time)
We are given hit rates and miss rates. Also miss time=2o cycles for each cache and hit time= 1, 2, 5 for direct mapped, 2-way set associative and fully associative cache respectively.
Direct mapped= 0.5*1 + 0.5*20 = 10.5 cycles
2-way set associative= 0.7*2 + 0.3*20 = 7.4 cycles
Fully associative cache= 0.9*5 + 0.1*20 = 6.5 cycles.