MESI Protocol Invalid cache line is attempted to be stored?

Question

I am implementing a sample MESI simulator having two levels of cache (write back). I have added MESI status bits to both levels of cache. As it is a write back cache, the cache line is updated to L2 only when it is flushed. My doubts are

1. what should be the behavior when a cache line with INVALID state is flushed from L1 cache. Will it just ignore the transaction? It seems that is the only possibility..but it doesn't seem right.

2. Consider processor1(P1) modifying a cacheline shared by processor2(P2). Then that cache line in P2 will get status INVALID. If P2 has to update the same cache line in future and sees the state is INVALID, it should read the updated value from??what if it is still in modified state in P1(not yet written back to L2/Main memory)?

3. Consider a similar situation that P1 has a cache line in MODIFIED state, P2 has the same line in INVALID state. When P3 tries to retrieve the same line, it broadcasts a request to all L1 caches. According to the theory,if P3 cant get the cache line from any other L1 caches, it sends request to L2/main memory. In this case where will P3 get the requested cache line from? From P1 or from the L2/main memory? Or will P1 update to the main memory first and then send the cache line to P3?

4. I am using LRU for flushing the cache(write back). When flushing a cache if it is INVALID what should be the behavior? It just ignores the line?

Answer 1

INVALID means "not in the cache," so there is nothing to flush. When you mark a cache block as INVALID it means that the data and the tag are not relevant.

Similarly, for your second question. The line is not in P2's cache, so it should treat the line the same way it treats any other cache miss: (if it's a snoopy coherence mechanism then it should broadcast a message to all the other caches. If it's a directory based coherence mechanism then it should send a request to the directory.)

Answer 2

1. A cacheline that is invalid will not be affected by a flush.
2. The sequence goes:
   • Line A is in state S (shared) in P1 and P2
   • P1 sets its state to E (exclusive) and sends out a StUp (store upgrade) to some central directory (CD)
   • CD sends a SnpI (snoop invalidate) to all other agents (in this case, P2) telling them to set their copy of Line A to I (invalid).
   • P2 sends an Ack (acknowledge) to the CD. After receiving all Acks from all agents, the CD sends an AckE (acknowledge you are exclusive) to P1.
   • P1 is free to commit any write it does to Line A. But it doesn't (Line A remains E).
   • P2 now wants to write Line A, it sees that Line A is I in its own cache. So P2 sends a RdE (read exclusive) to the CD.
   • CD gets the RdE and looks up its directory and sees that P1 has Line A in state E. CD sends a SnpI (snoop invalidate) to P1.
   • P1 receives the SnpI -- but it hasn't written any data to Line A -- so it sends a AckI (acknowledge I've invalidated and I have no data to give you) to CD.
   • CD sees the AckI from P1 and knows there is no data from P1. It reads Line A from memory and sends a FillE (fill data with exclusive permission) to P2.
   • P2 gets the FillE and has the latest updated data. It can then write to Line A.
3. Similar to #2, the sequence goes:
   • Line A is in state S (shared) in P1 and P2
   • P1 sets its state to E (exclusive) and sends out a StUp (store upgrade) to some central directory (CD)
   • CD sends a snoop to all other agents (in this case, P2) telling them to set their copy of Line A to I (invalid).
   • P2 sends an ack (acknowledge) to the CD. After receiving all acks from every agent, the CD sends an AckE (acknowledge you are exclusive) to P1.
   • P1 is free to commit any write it does to Line A. It sets its local copy state to M (modified) and writes some data to it.
   • P2 now wants to write Line A, it sees that Line A is I in its own cache. So P2 sends a RdE (read exclusive) to the CD.
   • CD gets the RdE and looks up its directory and sees that P1 has Line A in state E. CD sends a SnpI (snoop invalidate) to P1.
   • P1 receives the SnpI and sees that Line A is M in its own cache. It sends a Wb (writeback) to CD.
   • CD sees the Wb from P1, which has data. It writes the data from P1 to both memory (optional) and sends a FillE to P2.
   • P2 gets the FillE and has the latest updated data. It can then write to Line A.
     4. In this case:
   • P1 does not have Line A. It wants to read/write Line A. It will look up the LRU to find space. It sees that it has space that is invalid, so it sets that entry in its cache to Line A and sets the cache state to either S (for a read) or E (for a write). It does not need to flush anything as the replaced cache entry was invalid.
   • P1 sends a RdS (read shared) or RdE (read exclusive) to the CD to make sure everyone else knows it has the data for Line A.
   • The CD replies with a FillS (fill data with shared permission) or FillE (fill data with exclusive permission).
   • P1 uses data in Line A for a Load. Or it is free to commit data to Line A for a Store.