Suppose that you have a 4-way associative cache. In one of the sets of the cache,...

 

Transcribed Image Text:

Suppose that you have a 4-way associative cache. In one of the sets of the cache, there is a stream of accesses to the following block addresses. Determine whether each of the access would result in a cache hit, a cache miss, or a cache miss and replacement. Show what block is replaced for each of the following replacement policies: LRU, OPT, FIFO, Pseudo-LRU, and Inverse MRU. Inverse MRU keeps track of which line is the most recently used within each set. On replacement, replace the block from the line that is bitwise inverse of the MRU (e.g., if the MRU is in line "10", then select block in line "01" for replacement). For the first few accesses, fill the cache starting from way/line 00, 01, 10, and then 11. For each cell, use the following notation: "H" for hit, "M" for miss, "MR-x" for miss and replace block x. For the Pseudo-LRU replacement, assume initially that the tree has 'O' in all nodes. For the OPT replacement, if future information is no longer available for one or more blocks, break the tie by choosing to replace block that is alphabetically earlier (e.g. replace A before B, etc.) Accessed Block Address A B C D A E G H F F D IC D E G H E LRU Pseudo-LRU FIFO Inverse MRU OPT Suppose that you have a 4-way associative cache. In one of the sets of the cache, there is a stream of accesses to the following block addresses. Determine whether each of the access would result in a cache hit, a cache miss, or a cache miss and replacement. Show what block is replaced for each of the following replacement policies: LRU, OPT, FIFO, Pseudo-LRU, and Inverse MRU. Inverse MRU keeps track of which line is the most recently used within each set. On replacement, replace the block from the line that is bitwise inverse of the MRU (e.g., if the MRU is in line "10", then select block in line "01" for replacement). For the first few accesses, fill the cache starting from way/line 00, 01, 10, and then 11. For each cell, use the following notation: "H" for hit, "M" for miss, "MR-x" for miss and replace block x. For the Pseudo-LRU replacement, assume initially that the tree has 'O' in all nodes. For the OPT replacement, if future information is no longer available for one or more blocks, break the tie by choosing to replace block that is alphabetically earlier (e.g. replace A before B, etc.) Accessed Block Address A B C D A E G H F F D IC D E G H E LRU Pseudo-LRU FIFO Inverse MRU OPT

Answer rating: 100% (QA)

ANSWER To solve this problem we need to keep track of the contents of the cach... View the full answer