CSC/ECE 506 Fall 2007/wiki3 2 aY3w
SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.
A Brief Overview of the SSCI Protocol
The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on the possible race conditions in the final section.
As previously states, in the SSCI protocol the memory directory is in one of three states. They are:
- UNOWNED - the block is unowned by any cache.
- SHARED - the block is owned by multiple caches. Main memory is up to date.
- EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.
A Brief Overview of the SCI Protocol
Memory Directory States
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
- HOME - no remote cache contains a copy of the block.
- FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.
- GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.
Cache States
Additionally, each cache has a state, either stable or pending. Stable states have two parts:
- Where the cache entry is located in the sharing list for that block
- ONLY - singleton list
- HEAD - head of sharing list of more than one node
- MID - not head or tail of sharing list of more than one node
- TAIL - tail of sharing list of more than one node
- State of the cached block
- DIRTY - modified and writable
- CLEAN - unmodified and writable, same contents as memory
- FRESH - data is readable and writable, but memory must be informed before memory is written
- COPY - unmodified and readable
- many others
These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.
List Operations
SCI defines three primitive list operations for shared lists:
- List construction - adding a new node to the head of the sharing list
- Rollout - removing a node from the sharing list
- Invalidation - invalidate all other sharers. Can only be performed by the head node.
Why Additional States are Needed
The principle difference between SCI and SSCI is that SCI provides mechanisms for resolving race conditions and preserving serialization.
Example 1
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line.
In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0.
Consider what might happen if two processors both read miss concurrently. Suppose that P1 and P2 simultaneously send read request to the home node, and the home node processes the request from P1 first. Now, after the home node has updated its state to "EM" and its head pointer to 1, but before P1 has received the ReplyD, the home node processes the request from P2. The home node will set its state to S, update its head pointer to 2 and send a ReplyID(H->P2) telling P2 that P1 has the data.
Due to network latency, it's possible that P2 will receive the ReplyID and send a WB+Int+UpdPtr(P2->P1), and that P1 will receive that message before it even received the data from the home node! So, because P1's read is not atomic, we have a race condition.
Now let's consider the same scenario in SCI.
P1 and P2 both read miss. Both set aside space for the line to be read in, set the state of that line to a "pending" state, and issue the read request to the home node. When the home node receives the request from P1, the memory directory will be in state HOME (since the block is not cached anywhere). It will set its state to FRESH, set its head pointer to 1, and reply with the data.
Now P2's request is processed by the home node. Since the home node is in state FRESH, its data is up to date. It sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).
P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list. So, P2 remains in a pending state and sends a request to P1 to become the new head of the list. Recall that in our scenario, due to network latency, P1 still hasn't received the initial response from the home directory; P1 is still in a pending state. Under the SCI protocol, if a processor is in a pending state when it receives a list operation request (such as becoming the new head of the list), it will extend the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state. When P1 completes its operation and becomes the "true" head of the list, it can then pass the "true head" status on to P2. In this way, read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity).
Links
http://www.scizzl.com/WhatIsSCI.html
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf