Can you show the state transition for snoop-based scheme using MSI protocol?

The snoop based scheme is common used in both UMA and NUMA architectures, due to its flexibility and ease of scalability. In this post, we will discuss the state transition for snoop based scheme in both UMA and NUMA architectures. The protocol we are using is MSI protocol, i.e., a cache block can be in modified, shared or invalid state.

The Snoop-based MSI Protocol State Transition in UMA Architecture

A request of a cache block can be from processors, and it can be read or write, hit or miss. The requested cache block state can be in modified, shared or invalid state. The table below shows local cache controller actions upon a request from processor.

Request Source	Request	Local Cache Block State	Next Local Cache Block State	Actions of the System
Processor	Read hit	Shared	Shared	Read data from local cache
		Modified	Modified	Read data from local cache
	Read miss	Shared	Shared	Place a read miss on system bus, and evict the cache block
		Modified	Shared	Place a read miss on system bus, and write back the cache block to main memory
		Invalid	Shared	Place a read miss on system bus
	Write hit	Shared	Modified	Place an invalidate on system bus
		Modified	Modified	Write data in local cache
	Write miss	Shared	Modified	Place a write miss on system bus, and evict the cache block
		Modified	Modified	Place a write miss on system bus, and write back the cache block to main memory
		Invalid	Modified	Place a write miss on system bus

From the above table, certain requests from processors will involve actions of system bus. These actions including placing read miss, write miss and invalidate on system bus. The table below summarizes system bus behavior under these circumstances.

Request Source	Request	Block State of Remote Caches	Next Block State of Remote Caches	Actions of the System
System bus	Read miss	Shared	Shared	Allow shared cache or main memory to supply the data
		Modified	Shared	Place the cache block on system bus to supply the data, and write back the cache block to main memory
	Invalidate	Shared	Invalid	Invalidate the cache block
	Write miss	Shared	Invalid	Invalidate the cache block
		Modified	Invalid	Place the cache block on system bus to supply the data, and write back the cache block to main memory

The Snoop-based MSI Protocol State Transition in NUMA Architecture

As discussed in previous post, NUMA architecture usually combines the snooping with directories associated with distributed memories. Cache controller needs to send request to corresponding main memory, and the directory associated with that main memory decides whether to supply data directly, or to fetch data from remote caches.

The table below shows local cache controller behavior upon a request from processor.

Request Source	Request	Local Cache Block State	Next Local Cache Block State	Actions of the System
Processor	Read hit	Shared	Shared	Read data from local cache
		Modified	Modified
	Read miss	Shared	Shared	Send a read request to home directory, and evict the cache block
		Modified	Shared	Send a read request to home directory, and write back the cache block to main memory
		Invalid	Shared	Send a read request to home directory
	Write hit	Shared	Modified	Send an invalidate to home directory
		Modified	Modified	Write data in local cache
	Write miss	Shared	Modified	Send a write request to home directory, and evict the cache block
		Modified	Modified	Send a write request to home directory, and write back the cache block to main memory
		Invalid	Modified	Send a write request to home directory

From above table, certain requests from processors will involve actions of home directories. These requests include read request, write request and invalidate from processors. The table below summarizes home directory behavior under different circumstances.

Request Source	Request	Destination	Actions of the System
Home directory	Invalidate	Remote cache	Invalid shared copies in all remote caches
	Fetch	Remote cache	If the remote cache holds a modified copy, ask the remote cache to write back the cache block, and change the remote cache state to shared
	Fetch / Invalidate	Remote cache	If the remote cache holds a modified copy, ask the remote cache to write back the cache block, and change the remote cache state to invalid
	Data response	Local cache	return the cache block from home directory

“Fetch” usually happens when there is a read miss in local cache, and the modified copy is in remote cache.  Home directory sends “Fetch” to remote cache, and will expects a “Data write-back” from remote cache.

“Fetch / invalidate” usually happens when there is a write miss in local cache, and the modified copy exists in remote cache. Home directory sends “Fetch” to remote cache, and will expects a “Data write-back” from remote cache.

The data returned to local cache in “Data response” is either from remote cache or from main memory. If no remote cache holds a modified copy, then data value is returned from home memory, otherwise it is returned from remote cache.

The table below shows the remote cache behavior upon receiving “Fetch” or “Fetch / Invalidate” from home directory. Note, “Data write-back” may also happen due to cache eviction and a cache block replacement.

Request Source	Request	Destination	Actions of the System
Remote cache	Data write-back	Home directory	Write back the data to home directory

Conclusion

Understanding the cache coherent protocol and cache state transition are absolutely required in interview questions. It is also highly recommended to read J. Hennessy and D. Patterson’s book, Computer Architecture, Chapter 5 for more details. In this post, we used MSI protocol as an example. MSI protocol established the baseline for cache coherent protocol, and it can be extended to other variants, which we will discuss in next post.