Slides-Cap8-Part2-Cache Coherence Problems in SMP Systems

76 Questions

What occurs when a processor writes in a shared block in the write invalidate protocol?

The other processor's cache block is invalidated

What happens when a processor tries to access an invalid block in the write invalidate protocol?

There is a cache miss, and the data comes from the 'dirty' cache block and also updates the memory

Why do writing in non-shared blocks not cause problems in the write invalidate protocol?

Because it does not affect other processor's cache blocks

What is the main difference between the write invalidate protocol and the write update protocol?

The write update protocol updates all cached copies, while the write invalidate protocol invalidates them

What is a disadvantage of the write update protocol?

It consumes considerably more bandwidth

In terms of efficiency, why do most recent multiprocessors opt to implement the write invalidate protocol?

Because it is more efficient than the write update protocol

What is an advantage of the write invalidate protocol?

Multiple writing of the same word without intervening readings require multiple broadcasts, but just one initial block invalidation

What happens when P1 writes the memory position X on its cache and P2 reads the Mem[X]?

Cache coherence problem occurs

What is the primary goal of cache coherence in a system?

To ensure the use of the most current data

What is the relationship between memory system coherence and consistency?

Coherence and consistency are complementary

In the SMP problem, which if statement will be taken?

It needs to be handled by the programmer

What is the primary concern in SMP systems?

All of the above

What is the consequence of not handling cache coherence and consistency in SMP systems?

All of the above

What is the guarantee for a read by processor P to location X following a write by P to X, with no writes of X by another processor between the write/read by P?

The value written by P is always returned

What happens when a read by processor P1 to location X follows a write by processor P2 to X, with no other writes to X between the two accesses?

The value written by P2 is always returned if the accesses are sufficiently separated in time

What is the guarantee for writes to the same location by any two processors?

The writes are seen in the same order by all processors

What is the purpose of status bits associated with a cache block in basic schemes for enforcing coherence?

To keep track of the status of any sharing of a data block

What is the main difference between snooping and directory-based cache coherence protocols?

Snooping keeps the sharing status of a block in every cache, while directory-based keeps it in one location

What is the purpose of a directory in a directory-based cache coherence protocol?

To keep track of the state of every block that may be cached

What is the main advantage of snooping cache coherence protocols?

It is simpler to implement than directory-based protocols

What is the main disadvantage of directory-based cache coherence protocols?

It is more complex to implement than snooping protocols

What is the primary function of a directory in a directory-based protocol?

To keep track of the state of every block that may be cached

What is an advantage of distributing the directory along with the memory?

It allows different coherence requests to go to different directories

What information does the directory keep track of?

The state of every block that may be cached

How do the state diagrams in a directory-based protocol compare to those in a snooping-based protocol?

They are the same

What is the primary difference between a directory-based protocol and a snooping-based protocol?

The communication mechanism used for coherence requests

What is the function of the field with an associated bit for each system processor for each memory block?

To track the processors that have each memory block

What type of system does a directory-based protocol typically implement cache coherence in?

DSM systems

What is the main difference between write update and write invalidate protocols in terms of cache blocks?

Write update acts on individual words, while write invalidate acts on cache blocks.

What is the advantage of the write update protocol in terms of delay between writing and reading?

The delay between writing and reading is smaller in the write update protocol.

What is the key to implementing the write invalidate protocol?

Getting access to the memory bus.

What is the effect of the need to get access to the bus in the write invalidate protocol?

It forces the serialization of the writes.

What is the characteristic of a write through cache?

All written data are always sent to the memory.

What happens when a block is dirty in a write back cache?

The block is sent in response to the read request and the memory read/fetch operation is aborted.

What is the initial state of a cache block in a simple protocol with three states?

Invalid

What happens to the state of a cache block in the first write operation in a simple protocol with three states?

It becomes modified/exclusive.

What is the primary goal of cache coherence in a system, and how does it relate to memory system coherence and consistency?

The primary goal of cache coherence is to ensure that the most current data is used. Cache coherence and memory system coherence are complementary, with coherence ensuring the use of the most current data and consistency synchronizing read/write between processors.

What problem arises when P1 writes to a memory position X on its cache and P2 reads the Mem[X], and how can it be handled?

A cache coherence problem arises, and it needs to be handled by the programmer, i.e., synchronization.

What is the consequence of not handling cache coherence and consistency in SMP systems?

If not handled, it can lead to inconsistencies and errors in the system.

What is the primary concern in SMP systems, and how is it related to cache coherence?

The primary concern is synchronization, which is closely related to cache coherence, as it ensures that all processors see the most recent data.

How do cache coherence and processor consistency relate to each other?

Cache coherence ensures that the most current data is used, and processor consistency ensures that read/write operations are synchronized between processors.

What is the guarantee for a read by processor P to location X following a write by P to X, with no writes of X by another processor between the write/read by P?

The guarantee is that the read will return the value written by P.

What happens when a read by processor P1 to location X follows a write by processor P2 to X, with no other writes to X between the two accesses?

The read will return the value written by P2.

What is the guarantee for writes to the same location by any two processors?

The guarantee is that the writes will be seen in the order they were issued.

What is the fundamental principle that ensures a read by processor P to location X, following a write by P to X, with no writes of X by another processor between the write/read by P, always returns the value written by P?

Processor consistency

What is the condition under which a read by processor P1 to location X following a write by processor P2 to X returns the written value?

If the write and read are sufficiently separated in time and no other writes to X occur between the two accesses

What is the significance of serializing writes to the same location?

Ensures that all processors see the writes in the same order

What is the primary function of status bits associated with a cache block in basic schemes for enforcing coherence?

Keep track of the status of any sharing of a data block

What is the key difference between snooping and directory-based cache coherence protocols?

Snooping tracks sharing status of a block in every cache, while directory-based protocols keep the sharing status in one location (directory)

What is the primary advantage of directory-based cache coherence protocols?

Scalability and reduced traffic on the memory bus

What is the primary disadvantage of snooping cache coherence protocols?

Increased traffic on the memory bus due to snooping

What is the main advantage of the write invalidate protocol over the write update protocol?

Improved cache coherence and reduced latency

What is the primary goal of a directory-based cache coherence protocol in a distributed shared memory system?

To keep track of the state of every block that may be cached, including information about which caches have copies of the block, whether it is dirty, and the block status.

How do directory-based protocols implement cache coherence in multicomputers?

Through message passing between nodes, rather than snooping on the bus.

What information does the directory keep track of in a directory-based cache coherence protocol?

The state of every block that may be cached, including which caches have copies of the block, whether it is dirty, and the block status.

What is the primary difference between a directory-based protocol and a snooping-based protocol?

A directory-based protocol uses message passing between nodes, while a snooping-based protocol uses a bus to snoop on cache accesses.

What is the function of the field with an associated bit for each system processor for each memory block in a directory-based protocol?

To keep track of which processors have copies of each memory block.

What is the main advantage of using a directory-based protocol in a distributed shared memory system?

It allows for scalable and flexible cache coherence management in systems with many processors.

How do the state diagrams in a directory-based protocol compare to those in a snooping-based protocol?

They are the same, with states representing the cache line status and transitions representing the actions taken in response to cache accesses.

What is the primary advantage of distributing the directory along with the memory in a directory-based protocol?

It allows different coherence requests to go to different directories, reducing contention and improving system performance.

What is the primary concern in cache coherence protocols, and how does it relate to the memory bus in SMP systems?

The primary concern is preventing data inconsistency. In SMP systems, the memory bus can be a bottleneck, and cache coherence protocols must ensure that data is consistent across all processors, even when multiple processors are accessing the same data through the shared memory bus.

How do write invalidate protocols handle cache coherence, and what is the key to implementing this protocol?

Write invalidate protocols handle cache coherence by invalidating cache blocks on other processors when a write operation is performed. The key to implementing this protocol is to get access to the memory bus to invalidate a block, and the other processors snoop on the bus to check if they have that block in their caches.

What is the difference between write through and write back caches, and how do they handle dirty blocks?

Write through caches always send written data to memory, while write back caches only send dirty blocks to memory. If a block is dirty in a write back cache, it sends the dirty block in response to a read request and aborts the memory read/fetch operation.

What is the purpose of status bits associated with a cache block in basic schemes for enforcing coherence, and how do they relate to the three states in a simple protocol?

The purpose of status bits is to enforce coherence by tracking the state of a cache block. The three states in a simple protocol are invalid, shared, and modified/exclusive, which indicate the state of the cache block and ensure coherence across all processors.

How do write update and write invalidate protocols differ in terms of cache blocks, and what is the advantage of each protocol?

Write update protocols act on individual words, while write invalidate protocols act on cache blocks. The advantage of write update protocols is that they reduce the delay between writing and reading, while the advantage of write invalidate protocols is that they generate less traffic on the memory bus.

What is the primary goal of cache coherence in SMP systems, and how does it relate to the concept of consistency?

The primary goal of cache coherence is to ensure that data is consistent across all processors in an SMP system. Cache coherence is closely related to the concept of consistency, which ensures that data is consistent across all processors and memory.

What is the effect of the need to get access to the bus in the write invalidate protocol, and how does it relate to the concept of serialization?

The need to get access to the bus in the write invalidate protocol forces the serialization of writes, which ensures that writes are executed in a sequential manner to maintain cache coherence.

What is the main difference between snooping and directory-based cache coherence protocols, and how do they relate to the concept of cache coherence?

Snooping protocols rely on processors snooping on the bus to maintain cache coherence, while directory-based protocols use a directory to track cache coherence. The main difference is that snooping protocols are more scalable and typically used in smaller systems, while directory-based protocols are more complex and typically used in larger systems.

What is the primary advantage of using the write invalidate protocol over the write update protocol in terms of bandwidth consumption?

It consumes less bandwidth as only one initial block invalidation is required, whereas multiple broadcasts are required in the write update protocol

How does the write update protocol differ from the write invalidate protocol in terms of updating cached copies of a data item?

The write update protocol updates all cached copies of a data item when it is written, whereas the write invalidate protocol invalidates the other block copies in the other processor's cache

What is the primary goal of implementing cache coherence protocols in a system?

To ensure that multiple processors in a shared-memory system have a consistent view of shared data

How do write-back caches differ from write-through caches in terms of updating memory?

Write-back caches update memory only when a dirty block is replaced, whereas write-through caches update memory immediately on each write

What is the main disadvantage of the write update protocol in terms of system performance?

It consumes considerably more bandwidth due to the need to broadcast all writes to shared cache lines

What is the primary advantage of using a write invalidate protocol in a system with multiple processors?

It reduces the number of broadcasts required for multiple writes to the same word, making it more efficient

How does the write invalidate protocol ensure cache coherence in a system with multiple processors?

It ensures cache coherence by invalidating the other block copies in the other processor's cache when a processor writes in a shared block

What is the primary concern in systems with multiple processors and shared memory?

Maintaining cache coherence and consistency to ensure that all processors have a consistent view of shared data

Study Notes

Cache Coherence

A cache coherence problem occurs when multiple processors in a shared-memory multiprocessor (SMP) system access shared data, and the system returns a stale value instead of the most recent one.
A system is coherent if it returns the last value written to a data item.

SMP Problems

Consistency problems arise when multiple processors access shared data, leading to synchronization issues.
Inconsistencies can occur when processors read and write data to shared memory, leading to unexpected results.

Coherence

A memory system is coherent if:
- A read by a processor to a location following a write by the same processor to that location returns the value written by the processor.
- A read by a processor to a location following a write by another processor to that location returns the written value, if the write and read are sufficiently separated in time and no other writes to the location occur between those accesses.
- Writes to the same location are serialized, i.e., two writes to the same location by any two processors are seen in the same order by all processors.

Basic Schemes for Enforcing Coherence

Keep track of the status of any sharing of a data block.
Cache block status is kept by using status bits associated with that block.

Hardware-based Solution for Multiprocessors

Cache coherence protocols, such as snooping and directory-based protocols, are used to maintain cache coherence.

Snooping Coherence Protocols

Each cache has a copy of the memory data block and the share status of the block.
Caches share the memory bus and snoop on the memory traffic to check if they have copies of the "in-transit" block.
Protocols include write invalidate and write update protocols.

Write Invalidate Protocol

Writing in a shared block invalidates the other block copies in the other processor's cache.
When trying to access an invalid block, there is a cache miss, and the data comes from the "dirty" cache block and also updates the memory (write-back case).
Writing in non-shared blocks does not cause problems.

Write Update Protocol

Updates all cached copies of a data item when that item is written.
Must broadcast all writes to shared cache lines, which consumes more bandwidth.
Therefore, most recent multiprocessors have opted to implement a write invalidate protocol.

Brief Protocols Comparison

Write invalidate protocol:
- Multiple writings of the same word without intervening readings require multiple broadcasts, but just one initial block invalidation.
- It tends to generate less traffic in the memory bus.
Write update protocol:
- The delay between writing a word on one processor and reading the value written on another processor is smaller.
- The written data is updated immediately in the reader's cache.

Write Invalidate Implementation

Block invalidation:
- Key to implementation is to get access to the memory bus.
- Use it to invalidate a block, i.e., the processor sends the block address through the bus.
- The other processors are snooping on the bus and watching if they have that block in their caches.
Serialized writing:
- The need to get access to the bus, as an exclusive resource, forces the serialization of the writes.

Directory-based Protocol

Alternative to a snooping-based coherence protocol.
A directory keeps the state of every block that may be cached.
Information in the directory includes which caches have copies of the block, whether it is dirty, and block status.
Solution – distribute the directory along with the memory.
Each directory is responsible for tracking caches that share the memory addresses of the memory portion in the node.

Multicomputers

There is no cache coherence problem in multicomputers based on message passing, as each processor node has its own private memory and communicates with other nodes through message passing.