Ques: Consider a memory of 32 blocks (labeled 0 through 31) and a cache of 8 blo

Question

Ques: Consider a memory of 32 blocks (labeled 0 through 31) and a cache of 8 blocks (labeled 0 through 7). In the questions below, list only correct results:

a. Under direct mapping, which blocks of memory contend for block 2 of the cache?

b. Under 4-way set associativity, to which blocks of cache may element 31 of memory go?

c. In the following sequence of memory block references from the CPU, beginning from an empty cache, on which reference must the cache layout for a direct mapped and a 4-way set associative cache first differ?

d. Suppose a direct-mapped cache is equipped with a single-block victim cache. Out of the following sequence of memory block references from the CPU (R denotes read (or load) and W denotes write (or store)), on which references is the block retrieved from the victim cache? If no block is ever thus retrieved, so state. Show your reasoning.

Explanation / Answer

a.Using the rule x mod 8 for memory address x, we get {2, 10, 18, 26} contending
for location 2 in the cache.

b. With 4-way set associativity, there are just two sets in 8 cache blocks, which we
will call 0 (containing blocks 0, 1, 2, and 3) and 1 (containing 4, 5, 6, and 7).
The mapping of memory to these sets is x mod 2; i.e., even memory blocks go to set
0 and odd memory blocks go to set 1. Memory element 31 may therefore go to
{4, 5, 6, 7}.

c. For the direct mapped cache, the cache blocks used for each memory block are
shown in the third row of the table below
order of reference 1 2 3 4 5 6 7 8
block referenced 0 15 18 5 1 13 15 26
Cache block 0 7 2 5 1 5 7 2

For the 4-way set associative cache, there is some choice as to where the blocks
end up, and we do not explicitly have any policy in place to prefer one location
over another or any history with which to apply the policy. Therefore, we can
imitate the direct-mapped location until it becomes impossible, as shown below
on cycle 5:

order of reference 1 2 3 4 5 6 7 8
block referenced 0 15 18 5 1 13 15 26
Cache block 0 7 2 5 x

It is required to map an odd-numbered memory block to one of {4, 5, 6, 7}, as
shown in part (b).

d. In this example, nothing interesting happens beyond compulsory misses until
reference 6, before which we have the following occupancy of the cache with
memory blocks :

Cache block 0 1 2 3 4 5 6 7 V
Memory block 0 1 18 5 15

On reference 6, memory block 13 takes the place of memory block 5 in cache
block 5 (conflict miss), so memory block 5 goes to the victim cache:

Cache block 0 1 2 3 4 5 6 7 V
Memory block 0 1 18 13 15 5

The 7th reference, to memory block 15, hits in cache. On reference 8, memory
block 26 is mapped to cache block 2, displacing memory block 18 to the victim
cache and overwriting memory block 5:

Cache block 0 1 2 3 4 5 6 7 V
Memory block 0 1 26 13 15 18

Cycle 9 is a routine compulsory miss. On reference 10, memory block 18 is
retrieved on the read miss from the victim cache, changing places with 26:

Cache block 0 1 2 3 4 5 6 7 V
Memory block 0 1 18 13 15 26

On reference 11, when memory block 5 is desired, it must come from memory,
putting 13 into the victim cache:

Cache block 0 1 2 3 4 5 6 7 V
Memory block 0 1 18 5 15 13

Finally, on reference 12, memory block 13 is written into cache block 5. This
does not reuse the old value of memory block 13 in the victim cache, though it
does interchange 5 and 13 in cache block 5 and the victim cache upon
completion.

To summarize, only reference 10 retrieves a victim cache block.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.