Practice problems, do not submit for the lab report
RET ; --------------------------------------------------------------
Download 0.89 Mb.
|
- Navigate this page:
- 2-way set-associative cache, with 4 sets
| RET
; -------------------------------------------------------------- END Hint: The program does still not work correctly for n=3 (or higher). Pay close attention to the multiplication instruction – when returning from the recursive calls: AL does not have the correct value, (n-1)! BL does not have the correct value, n. How to fix these problems? (Each has its own fix.) Notes for solution: 2] If a cache set is full and a new block must be brought from MM into that set, the set-associative (or fully associative) replacement algorithm must choose the block to be evicted based on a replacement policy. LRU (Least Recently Used) is the best policy, however it requires in general several bits of memory to keep track of each block’s usage. The LRU bit (i.e. just 1 bit) is the simplest approximation of the LRU algorithm. For a 2-way set associative cache, the one LRU bit is actually sufficient to implement the LRU policy exactly. Scenario: 2-way set-associative cache, with 4 sets (of 2 blocks each). The size of the block (therefore the # of bits in the offset) is not known, nor is the size of the MM (therefore the # of bits in the tag). We know, however, that log2(4) = 2, so the set field is 2 bits wide: The block numbers shown here are meant to include the tag and set bits, so the set number is simply the number modulo 4, or, in binary, the least significant 2 bits, as shown above. When there is a hit (or when the block is first brought in the cache): its LRU bit is reset (made 0) the LRU bit of the other block (if present) is set (made 1). We can think that 0 means “new”, and 1 means “old”. If both blocks in a set are available, the smaller one (on the “left”) is used first. The cache has 4 sets, and it is initially empty. The CPU is requesting the following sequence of 8 blocks: 13, 1, 2, 1, 2, 42, 43, 17. Show in the sequence of cache diagrams (handout) how the state of the cache evolves. Download 0.89 Mb. Share with your friends:
|