MESI protocol in cache conherence

Question

I have a question on MESI protocol.

(1)Consider the following code fragment that runs on a uniprocessor system that Implements the MESI cache coherence protocol:

I1: load $s1, [A] I2: load $s2, [B] I3: add $s1, $s2, $s3 I4: store $s3, [C] I5: sub $s3, 1, $s4 I6: store $s3, [A]

Assume write-thru cache policy. If memory block A, B, and C are loaded (if needed) onto two different cache blocks (initially empty) on a single processor, complete the following table to identify the cache state of the blocks containing A, B, C, after each instruction executes.

My answer to that is:

Step/State                A                   B               C
I1                        E                   I               I
I2                        E                   E               I
I3                        E                   E               I
I4                        I                   I               E
I5                        I                   I               E
I6                        E                   I               I

(2) In the following RTL

I1: R1 <-[6] 
I2: R2 <-[4] 
I3: R3 <- R1 + R2 
I4: [6]<- R3 
I5: R4 <- R4 - 1 
I6: [4]<- R4

Assume write-thru cache policy. If memory block 4 and 6 are loaded onto two different cache blocks (initially empty) on a single processor

My answer is

Step/state            Block 4                Block 6
Initial                 I                      I
I1                      I                      E
I2                      E                      E
I3                      E                      E
I4                      I                      E(write miss, AOW)
I5                      I                      E
I6                      E(write miss, AOW)     I

Is my answer correct please? Thank you very much in advance.

Tayyar R Tayyar R · Accepted Answer · 2014-07-25T16:52:08

The answer to 1st question depends on your write policy and whether you have more than one cache level in your hierarchy. Are you using write-allocate or No-write-allocate? And is it fair to assume that you have L2 that is write-back?

If you are assuming NO-write-allocate, the store (I4) will write around the cache and not request the line at all, so it will remain Invalid.

If you are assuming write-allocate policy, then the cache line C will be requested in M state (at least in one of the cache levels, and definitely in the LLC). So the answer here would depend on the number of caches you have as well as the write-policy.

But I4 should not invalidate A or B, so they both stay in Exclusive Mode. The only way they would be invalidated is if another processor were to write to them or you have a conflict. It is unclear to me how your memory locations A,B, and C are mapped to cache lines. If they are one to one and there is no conflict in the cache, then A and B will stay in Exclusive Mode, if there is conflict you would need to decide based on the replacement policy.

The answer to 2nd question also depends on the number of caches and whether your LLC is write-back. When I4 is writing to Block 6, it is already in the cache, which means it will modify both this cache and the lower level cache, which will be marked as M (assuming the lower level cache is write-back). At the same time Block 4 is NOT invalidated.

Exactly the same thing happens when I6 writes to Block 4. The block will be written to in this cache and also in the lower level cache. The lower level cache will be marked as M (again, assuming the lower level cache is write-back)

If you clarify all of those assumptions, I could sketch you the correct (in my opinion) diagram.

Hope this helps!

MESI protocol in cache conherence

1 Answers