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.
2 Comments