hpca/sample-final/samplefinal2/problem4

Problem 4. 25 Points - Cache Coherence

A shared-memory bus-based multiprocessor has two processors. Each processor has a

small direct-mapped L1 cache, with only two 8-byte blocks in each cache. All addresses

in this problem are 12-bit physical addresses, and all caches are physically indexed and

tagged. The MESI coherence protocol is used in this multiprocessor. The initial state for

the two caches is with tags of 0 and in “I” state.

A) [3 points] What is the shortest sequence of accesses that will, starting with the

initial state, result in the following cache state:

Screen Shot 2014-04-29 at 9.56.26 AM.png

Note: The minimum number of accesses is fewer than five. Space for five is

provided just in case you need it. Similar extra space is provided in B), C), etc.

B) [4 points] What is the shortest sequence of accesses that will, starting with the

initial state, result in the following cache state:

Screen Shot 2014-04-29 at 10.04.20 AM.png

Sequence of accesses:

Screen Shot 2014-04-29 at 10.05.32 AM.png

C) [4 points] What is the shortest sequence of accesses that will, starting with the

initial state, result in the following cache state:

Screen Shot 2014-04-29 at 9.59.36 AM.png

D) [4 points] What is the shortest sequence of accesses that will, starting with the

initial state, result in the following cache state:

Screen Shot 2014-04-29 at 10.08.35 AM.png

Sequence of accesses:

Screen Shot 2014-04-29 at 10.09.44 AM.png

E) [5 points] The following state cannot happen:

Screen Shot 2014-04-29 at 10.11.14 AM.png

Explain why:

F) [5 points] The following state cannot happen:

Screen Shot 2014-04-29 at 10.13.03 AM.png

Explain why: