Given a 2-way Set Associative cache with 4 lines using LRU replacement within ea
ID: 2082612 • Letter: G
Question
Given a 2-way Set Associative cache with 4 lines using LRU replacement within each set. The word size is one byte, there is one word per block, and the main memory capacity is 16 bytes. Suppose the cache is initially empty and then the following addresses are accessed in the order listed: {3, 4, 3, 7, 7, 12, 4, 8, 3, 12, 7, 9}. How many bits are in the tag field? (.e. the tag itself not including any counter bits) After execution of all of the above references, what are the final contents of the cache? State your answer as a set of memory addresses whose data resides in cache, e.g. "{3, 4, 8, 12}". For instance, if memory[3], memory [4], memory[8], and memory[12] resided in cache then the answer is stated as "{3, 4, 8, 12}". What is the hit rate? Express your answer as a percent.Explanation / Answer
2.1) Since the main memory has a capacity of 16 bytes and each word is one byte long it has 16 words. We need 4 bits to address any one of the 16 words (24 = 16). Therefore the total number of address bits is 4. Now the address field is divided into 3 sub-fields known as tag, set and offset. As the block contains only one word which itself is only one byte, the offset bits are 0 because 20 = 1. And since the cache is 2-way set associative with 4 lines the number of sets is = number of lines/ number of ways = 4/2 = 2. To represent any one of the two sets you would need only one bit. So number of tag bits are given by:
total number of address bits - (offset bits + set bits) = 4 - 0 - 1 = 3 bits
2.2) LRU replacement strategy essentially replaces the least recently used word in the cache. Also the cache has 2 sets of 2 ways each. So any of the 16 words from main memory will be stored in set 0 or set 1 in the cache depending on the LSB of the address which is the SET bit as we saw in the previous section. So addresses 1,3,5,7,9,11,13,15 will be stored in set 1 and others in set 0. To find the final contents we will have to place/ replace each of the above memory contents in cache as follows:
3. As the cache is empty this will be a miss and the word at address 3 is stored in set 1
4. As the cache is empty for set 1 this will be a miss and the word at address 4 is stored in set 0
3. This will be a hit as the number is already present in the cache
7. As there are 2 ways in set 1, the word at address 7 will be stored in the 2nd way of set 1
7. This will be a hit as the number is already present in the cache
12. This number belongs to set 0 and will be stored in the 2nd way
4. This will be a hit as the number is already present
8. Now the cache is not empty and one of 12 or 4 will have to be replaced with 8 in set 0. Since we are using LRU strategy and 4 has been accessed in the previous step we will replace 12 and place 8
3. This will be a hit as the number is already present
12. This will be a miss as 12 had been replaced previously 8 and now 4 being least recently used it will get replaced by 12
7. This will be a hit as the number is already present
9. Since 7 was accessed most recently 3 will be replaced by 9
So the final contents of the memory will be {9,12,7,8}
2.3) The hit rate is calculated as percentage of memory accesses which are satisfied by cache. So in above (5/12)*100 will give you the hit rate which is 41.66 %
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.