1) We will examine how replacement policies impact miss rate. Assume a following
ID: 3811116 • Letter: 1
Question
1)We will examine how replacement policies impact miss rate. Assume a following 2way set associative cache.
Consider the following block address sequence: 0, 1, 5, 2, 4, 8, 12, 16, 20, 24, 28, 0
0address will fill left side of set0.
1address will fill left side of set1.
5 address will fill right side of set1.
2 address will fill left side of set2.
a)Assuming an LRU (least recently used) replacement policy, how many hits does this address sequence exhibit?
b)Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit?
One-way set associative (direct mapped) Block Tag Data Two-way set associative Set Tag Data Tag Data Four-way set associative Sat Tag Data Tag Date Tag Data Tag Data Eight way set associative (fully associative) Tag Date Tag Date Tag Dat Tag Date Tag Dat B Tag Data Tag Data Tag DataExplanation / Answer
Solution:
I'll only be writing the order in which data will arrive to see whether it's hit or a miss.
So at first when the operation is required on some data it will be a miss (that means when the sets are empty). and the address which is accessed will be put into the set for future use, so that it can be found in the cache.
0, 1, 5, 2, 4, 8, 12, 16, 20, 24, 28, 0
When the memory start to access given address sequence in LRU manner in 2 way set associative way, then
so let's see which address will be a miss and which one is a hit, 0(Miss), 1(Miss), 5(Miss), 2(Miss), 4(Miss), 8(Miss), similarly we keep on doing like that and what will happen is 0 is the one which is least recently used and that will be replaced by any other element, so number of misses in LRU manner will be 12 and number of hits will be 0.
since all address sequence are different except 0 which will be replaced as soon as we ran out of cache memory.
MRU:
So in MRU the whole scenario will be same except one thing the sequence address will always be replaced by most recently used address, this way 0 will be there in the memory till the end, and on accessing last address sequence 0 it will be a hit, so in MRU number of misses= 11, and number of hits= 1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.