A cache has the following (unrealistic) configuration: • 2-way associative, using an LRU replacement policy • 8 sets • 4 bytes per line yielding a total capacity of 64 bytes. The cache is initially all lines invalid. An array of characters (one byte each) is located at address 0, such that the index of each character in the array is exactly the address of that character. Indicies in the array are accessed in the order given below. Select the appropriate choices from the dropdowns to give the index of the first element in each line of the cache after all of the accesses are complete. In order to help you get started, we've done the first 8 accesses for you, and to help you verify your work, some of the answers are provided for you; if your answers don't match the provided answers, you made an error in your calculations. Addresses are accessed through the cache in the following order: 92, 13, 118, 9, 31, 62, 15, 107, 6, 23, 15, 9, 15, 58, 36, 29, 114, 45, 73, 63, 100, 67, 4, 76, 4, 53, 93, 112, 96, 51, 103, 60 Working through the first 8 accesses: • Initially, all lines in the cache are marked invalid • Address 92 misses (it is not already in the cache). It is added to set 7 • Address 13 misses. It is added to set 3 (the line begins with address 12) • 118 misses. It is added to set 5 • 9 misses. It is added to set 2 • 31 misses. It is added to set 7 • 62 misses. It is added to set 7. Set 7 had no invalid lines, so it knocks out the least recently used line • 15 hits in set 3. Set 3 still has an invalid line in the set, so it is not necessary to update LRU bookkeeping • 107 misses. It is added to set 2 After these operations, the cache has the following state: • Both lines in set 0 are invalid • Both lines in set 1 are invalid • Set 2 contains lines beginning at addresses 8 and 104. The line beginning at 8 is least recently used • Set 3 has one invalid line. The other line begins at 12 • Both lines in set 4 are invalid • Set 5 has one invalid line. The other line begins at 116 • Both lines in set 6 are invalid • Set 7 contains lines beginning at addresses 28 and 60. The line beginning at 28 is least recently used Complete the state of the cache after the remaining 24 accesses: • Set 0: The lines begin with indices [Select] • Set 1: One of the lines begins with index 100, the other [Select] く • Set 2: The lines begin with indices (Select] • Set 3: The lines begin with indices [ Select] Set 4: The lines begin with indices [Select] • Set 5: The lines begin with indices [Select] < • Set 6: One of the lines begins with index [Select] , the other invalid • Set 7: The lines begin with indices
