Finite State Machine

AKA coherence controller.

Coherence Protocols

Specifing Protocols

• State: For example, Not readable or writable (N), Read-only (RO), Read-write (RW). These is the state of the cache.
• Events: For example, Load, Store, Incoming Coherence request to optain read-write state.
• Transitions: Actions

States

Implemented ststes shoudl consider:

• Validity: Has the up-to-date value. Can read, but can write if it is also exclusive.
• Dirtiness: Write to up-to-date, but not yet push to lower memory.
• Exclusivity: No other private cache has a copy of the block.
• Ownership: Owner is responsible for responding to coherence reqeust for that block.

MOESI/MSI

• Modified: Valid, exclusive, owned, and maybe dirty. Can read and write.
• Owned: Valid, and owned, and maybe dirty. Read-only. Other core also have read-only copy but not owners.
• Exclusive: Valid, exclusive, and clean. Read-only.
• Shared: Valid and clean. Read-only.
• Invalid: Invalid.

Transiten States

States that is inbetween two states. ie., $IV^D$ (in Invalid going to Valid, waiting for DataResq).

Transactions

*Some protocols do not require a coherence transaction to evict a Shared block and/or an Exclusive block (i.e., the PutS and/or PutE are “silent”).

*A cache controller may choose to ignore a prefetch request from the core.

Major Protocal Design Options

Directory vs. Snooping

• Directory protocol: A directory is used to track the state of each block. Cache controller send request to the home of that block.
• Snooping protocol: A shared bus is used to broadcast the state of each block. Assume requests arrive in totol order.

Invalidate vs. Update

• Invalidate protocol: Write will invalidate the block, so other core cannot read.
• Update protocol: Write update all copies of the block.

Snooping Protocol

Usually using a bus to broadcast the requests, but not necessarily has to use a bus.

SIMPLE SNOOPING SYSTEM MODEL: ATOMIC REQUESTS, ATOMIC TRANSACTIONS

Simple snooping for cache controller, labeled “(A)” denotes that this transition is impossible because transactions are atomic on bus:

• Atomic request: Issue request ensures that another core’s request will not ordered ahead of its, when this cache controller seeks to upgrade permission (I->S, S->M, or I->M). Thus, controller transition immediately to state $IS^D$, $IM^D$, or $SM^D$.
• Atomic transaction: No subsequent requests from a block will occur until the current transaction completes. Resquest always comes with reponse in pair.

BASELINE SNOOPING SYSTEM MODEL: NON-ATOMIC REQUESTS, ATOMIC TRANSACTIONS

MESI

• Rely on atomic transactions.
• Use E instead of S: when GetS occurs when no other cache has access to the block.
• Upgrade from E to M is silent. No transactions needed. Elinimate half of the transactions.

Note: in the figure when it says, “mem in I”, it means in the lower level memory (ie,. LLC or DRAM), that cache block is in I which states that no private cache has a copy of that block. It does not mean the cache in the private cache is in I state.

MOSI

• Rely on atomic transactions.
• Eliminate extra data to update LLC when a cache receives a GetS request in the M/E state.
• Using dirty bit, eliminate unnecessary write to LLC (if block is written again before write back to LLC).
• Owner is used to reduce the access latency. Without owner, even a core’s private has a copy in S, it cannot forward the copy to other because no one know who is the owner. Only the defined owner can forward the copy.

Non-atomic bus

• Send request without waiting for previous response.
• Pipelined bus: response in same order as request.
• Split transaction bus: response in random order depending on latency.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Atomic bus:
Address Bus:  Request 1 ----------- Request 2 ------------ Request 3
Data Bus:               Response 1 ----------- Response 2 ----------- Response 3

Pipelined (non-atomic) bus:
Address Bus:  Request 1 Request 2 Request 3
Data Bus:               Response 1 Response 2  Response 3

Split transaction (non-atomic) bus:
Address Bus:  Request 1 Request 2 Request 3
Data Bus:               Response 2 Response 3  Response 1

• non-atomic system model:
  • can use FIFO queue to buffer messages.

Directory Protocol

• Directory: a global view of the coherence state of each block.
• Forwarding, the directory controller can forward the request to the owner of the block.

A directory entry can be like (N: number of nodes):

Avoiding Deadlocks

• Deadlock: Event A causes event B and both require resource allocation. Deadlock can occur when the resources are both not available until one of the event completes. For example, GetS can causes Fwd-GetS which uses the same resources.

1
2
3
4
5
6
7
8

    Full
    | Queue | ------> C1 ----->
       ^                       |
       |                       |
       |                       |
       |                       |
       -----C2<--------------| Queue |
                                Full

To avoid deadlock, we can use different netwroks for different calss of messages. This avoid dependence between different messages. ie,. response and request.

Detailed Protocal Specification

MSI Directory Protocol - directory controller

References

Sorin, D. J., Hill, M. D., Wood, D. A., & Nagarajan, V. (2020). A primer on memory consistency and cache coherence (2nd ed., pp. 91-191). Springer Nature. https://doi.org/10.1007/978-3-031-01764-3