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.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.