3.2.

CACHE COHERENCE AND SYNCHRONIZATION

MECHANISMS
Cache coherence protocols for coping with the multicache inconsistency problem are
considered below.
• Snoopy protocols are designed for bus-connected systems.
• Directory—based protocols apply to network-connected systems.

3.2.1 Cache Coherence problem

• Cache and main memory may contain inconsistent copies of the same object.
Multiple caches may possess different copies of the same memory block because
multiple processors operate independently and asynchronously.
• Cache coherence schemes prevent this problem by maintaining a uniform state
for each cached block of data.

Qn:What are the causes of cache inconsistency? Explain the mechanisms

used for handling cache inconsistencies?
Qn:Explain any three sources of cache data inconsistency and discuss the
possible protocols to overcome the cache data inconsistency problem?

• Cache inconsistency can be caused due to

1. Inconsistency in data sharing
2. Process migration
3. Inconsistency due to I/O operations

 Inconsistency in data sharing

Fig:3.19

• Consider a multiprocessor with two processors, each using a private cache and
both sharing the main memory. Let X be a shared data element which has been
 referenced by both processors.
• Before update value of X is same in memory as well as both the caches
• In write through policy , if P1 updates X to X’ the same copy will be written
immediately to main memory. But inconsistency occurs between the cached
copies
 In write-back policy the main memory will be updated only when the modified data
in the cache is replaced or invalidated.so inconsistency occurs between the cached
copy and shared memory.

Qn: Describe the inconsistencies caused by process migration?

 Process Migration and I/O
 Process migration means transferring of sufficient amount of the state of the
process from, one processor to another processor.
 The process migration is done in the case of load sharing.(heavily loaded to
lightly loaded processor)

Fig:3.20
• Initially before migration, P1 have the value x in its cache and also x in shared
memory.
• Now x has been migrated to p2 and ,If p2 reads x and updates it to x’(Centre
fig), in write through policy, the value will be updated simultaneously in shared
memory also. But in p1 its still x. so inconsistencies exists.

• Now in case of write back, If p1 reads the value x , modifies it to x’ ,but it will not
be updated in shared memory which is being read in the p2, while executing the
process. So here the updated value is not used by the p2 to perform the particular
task.. (Right most figure)(P1 to p2).

 Inconsistency due to I/O operations.

Qn: How can the I/O operations bypassing cache result in cache
coherence problem? Also, suggest a solution for preventing it?
  Data movement from an I/o device to a shared memory usually does not
cause the cached copies of data to be updated.
 As a result, an input operation that writes x will write data to the shared
primary memory,causes it to become inconsistent with a cached value of x.
 Likewise, writing data to an I/O device usually use the data in the shared
primary memory, ignoring any potential cached data with different values.

Fig:3.21

• When I/O processors loads a new data X’ into the main memory (middle fig
above) inconsistency occurs between caches and shared memory.
• When outputting a data directly from the shared memory(Bypassing the cache)
also create inconsistency.
• Possible solution is to attach I/O processors to private caches(C1 and C2) as
shown in fig below. This way I/O processors share caches with the CPU. The I/O
consistency can be maintained if cache-to-cache consistency is maintained via
the bus.

Fig:3.22

TWO PROTOCOL APPROACHES to maintain Cache consistency

Qn:Explain any two cache coherence protocol ?

Qn:Describe the snoopy protocol used to ensure cachecoherence
in multiprocessor systems
 1. Snoopy Bus Protocol (used in commercial multiprocessors using bus based
memory systems)
A bus is a convenient device for ensuring cache coherence because it allows all
processors in the system to observe ongoing memory transactions. If a bus
transaction threatens the consistent state of a locally cached object, the cache
controller can take appropriate actions to invalidate the local copy. Protocols
using this mechanism to -ensure coherence are called snoopy protocol because
each cache snoops on the transactions of other caches.
2. Directory based Protocols (used in scalable multiprocessor system interconnect
processors )

3.2.2 SNOOPY BUS PROTOCOLS

• Processors with private cache tied to a common bus ,practices 2 approaches to

maintain cache consistency

1. Write Invalidate policy – invalidates all remote copies when a local cache
block is updated. In fig below processor P1 modifies(write) its cache from X
to X’ and all other copies are invalidated via the bus. Invalidated blocks are
called dirty, means, they should not be used.

Fig:3.23

2. Write Update policy – broadcast the new data block to all caches
containing a copy of the block. In fig below the new updated block content
X’ is broadcast to all cache copies via the bus. The memory copy is also
updated if write-through caches are used, if write-back caches are used
memory copy is updated later when the block is replaced
 Fig:3.24

Write- Through Caches:

• The states of a cache block copy change with respect to3 operations in the cache:-
• Read
• Write
• Replacement
• A block copy of a writethrough cache i attached to processor i can assume one of two
possible cache states:
o valid or
o invalid

In a valid state (Fig. above),

• all processors can read(R(i),R(j)) safely.
• Local processor i can also write (W(i)) safely.
•
The invalid state corresponds to :
• the case of the block either being invalidated or being replaced (Z(i) or Z(j))
• a write (w(j)) by a remote processor into its cache copy, makes all other copies
become invalidated.
Fig 3.25:State transition graph for a cache block using write through ,write-invalidate snoopy protocol

Write-Back Caches:
The valid state of a write-back cache can be further split into two cache states,labelled:-
• RW (read –write/ Exclusive) and
• RO (read only/ Shared) as shown in Fig. below.

The INV (invalidated or not-in-cache) cache state is equivalent to the invalid state
mentioned before.

This three-state coherence scheme corresponds to an ownership protocol.

Fig:3.26 State transition graph for a cache block using write-back ,write-invalidate snoopy protocol

j denotes a remote processor ,where j!=i

W[i] = Write to block by processor i. W[j] = Write to block copy In cache j by processor
(Write hit) ,j!=I (Write miss)
R[i] = Read block by processor i R[j] =read block copy In cache j by processor ,j!=i
(Read Hit) (Read Miss-replacement action to be performed)
Z[i] =Replace block in cache i Z[j] = Replace block copy in cache j!=i
(Invalidation by local processor) (Write miss-action to be performed is replacement
 by remote processor j)

• When the memory owns a block, caches can contain only the RO(Shared) copies of
the block. In other words, multiple copies may exist in the RO state and every
processor having a copy (called a keeper of the copy) can read(R(i)), R(j)) the copy
safely.

• The INV state is entered whenever a remote processor writes (w(j)) its local copy or
the local processor replaces (Z(i)) its own block copy.

• The RW state(Exclusive) corresponds to only one cache copy existing in the

entire system owned by the local processor i. Read (R(i)) and write (w(i)) can be
safely performed in the RW state

• . From either the RO state or the INV state, the cache block becomes uniquely owned
when a local write (w(i) takes place.

Write-once Protocol :-a cache coherence protocol for bus-based multiprocessors.

• This scheme combines the advantages of both write-through and write-hack
invalidations.
• In order to reduce bus traffic, the very first write of a cache block uses a write-
through policy.This will result in a consistent memory copy while all other cache
copies are invalidated.
• After the first write, shared memory is updated using a write-back policy. This
scheme can he described by the four-state transition graph shown in Fig. below The
four cache states are defined below:

Fig: 3.27

Valid: The cache block, which is consistent with the memory copy, has been read from
shared memory and has not been modified.

Invalid: The block is not found in the cache or is inconsistent with the memory copy.

Reserved: Data has been written exactly once since being read from shared memory. The
cache copy is consistent with the memory copy, which is the only other copy.

Dirty: The cache block has been modified (written) more than once, and the cache copy is
the only one in the system (thus inconsistent with all other copies).

To maintain consistency, the protocol requires two different sets of commands. The solid
lines in Fig. above correspond to access commands issued by a local processor labeled
read-miss, write-miss and write –hit. Whenever a read-miss occurs, the valid state is
entered.
  The first write-hit leads to the reserved state.
 The second write-hit leads to the dirty state,
 and all future write-hits stay in the dirty state.
 Whenever a write-miss occurs, the eache block enters the dirty state.

The dashed lines correspond to invalidation commands issued by remote processors via
the snoopy bus.
The read-invalidate command reads a block and invalidates all other copies. The write-
invalidate command invalidates all other copies of a block.

Cache Events and Action: The memory-access and invalidation commands trigger
the following events and actions:

Read-Miss: When a processor wants to read a block that is not in the cache, a read-miss
occurs. A bus read operation will be initiated. If no dirty copy exists, then main memory
has a consistent copy and supplies a copy to the requesting cache. If a dirty copy does
exist in a remote cache, that cache will inhibit the main memory and send a copy to the
requesting cache. In all cases, the cache copy will enter the valid state after a rcad-miss.

Write-Hit: If the copy is in the dirty or reserved state, the write can be carried out locally
and the new state is dirty. If the new state is valid, a write-invalidate command is
broadcast to all caches, invalidating their copies. The shared memory is written through,
and the resulting state is reserved after this first write.

Write-miss: When a processor fails to write in a local cache, the copy must come either
from the main memory or from a remote cache with a dirty block. This is
accomplished by sending a read-invalidate command which will invalidate all cache
copies. The local copy is thus updated and ends up in a dirty state.

Read-hit: Read-hits can always be performed in a local cache without causing a state
transition or using the snoopy bus for invalidation.

Block Replacement: If a copy is dirty, it has to be written back to main memory by block
replacement. If the copy is clean (i.e., in either the valid, reserved, or invalid state), no
replacement will take place.

Protocol Performance issues

• Snoopy Cache Protocol Performance determinants:
o Workload Patterns
o Implementation Efficiency
• Goals/Motivation behind using snooping mechanism
o Reduce bus traffic
 o Reduce effective memory access time
• Data Pollution Point
o Miss ratio decreases as block size increases, up to a data pollution point
(that is, as blocks become larger, the probability of finding a desired data
item in the cache increases).
o The miss ratio starts to increasing as the block size increases to data
pollution point.
• Ping-Pong effect on data shared between multiple caches
o If two processes update a data item alternately, data will continually
migrate between two cacheswith high miss-rate

3.2.3 DIRECTORY BASED PROTOCOLS

Qn:Advantage of Directory based over Snoopy bus protocol ?

Qn: Differentiate between central and distributed directory ?

• Write invalidate scheme for Snoopy Bus causes heavy bus traffic since it
invalidates cache copies on each update.
• Write update scheme for Snoopy bus updates all cache copies, some of which
may never be used.
• Hence in large multiprocessors with hundreds of processors broadcasting
becomes expensive. This leads to Directory based protocols.

Directory Structure
• In multistage network, Cache coherence is supported by using cache directories
to store information on where copies of cache block reside. Directory can be
Central or Distributed
• Directory scheme using a Central Directory stores duplicates of all cache
directories. Contention and long search time are the drawbacks in using central
directory..
• In Distributed directory scheme Each memory module maintains a separate
directory which records the state and presence information for each memory
block. The state information is local, but the presence information indicates which
caches have a copy of the block.
•
 Fig: 3.28: Basic concept of a directory based cache coherence scheme

• In fig above a read-miss (thin lines) in cache 2 results in a request sent to

memory module. The memory controller retransmits request to dirty copy in
cache 1. This cache writes back its copy. The memory module can supply a copy
to the requesting cache.
• In the case of a write-hit at cache 1 (bold lines) a command is send to the memory
controller which sends invalidation to all caches (cache 2) marked in the presence
vector residing in the directory D1.
• A directory entry for each block of data contains a number of pointers to specify
the locations of copies of the block. Each directory entry also contains a dirty
bit to specify whether a particular cache has permission to Write the
associated block of data.

Qn:Explain Full map directory based protocol?

3 different types of directory protocols

1 Full Map directories:- Full-map directories store enough data associated with each
block in global memory so that every cache in the system can simultaneously store a
copy of any block of data. That is. each directory entry contains N pointers, where N is
the number of processors in the system.

2. Limited directories;- they have a fixed number of pointers per entry, regardless of the
system size.

3. Chained Directories:-They emulate the full-map schemes by distributing the

directory among the caches

1. Full Map Directories

• Directory entry contains one bit per processor and a dirty bit. Each
bit represents the status of the block in corresponding processor’s
 cache(present or absent)
• If dirty bit is set, then only one processor’s bit is set and that
processor can write into the block.
• A cache maintains 2 bits per block. One bit indicates whether block
is valid, and other indicates whether a valid block may be written.

Fig: 3.29

• In above fig, in first state, location X is missing in all caches in the

system.
• The second state results from three cache (C1, C2 and C3)
requesting copies of location X. Three pointers (processor bits) are
set in the entry to indicate the caches that have copies of the block of
data.
• In first two states the dirty bit on left side of the directory entry is set
to clean ( C ), indicating that no processor has permission to write to
the block of data.
• The third state results from cache C3 requesting write permission
for the block. In the final state the dirty bit is set to dirty ( D ) and
there is a single pointer to the block and data in cache.
• Memory consumed by Directory is proportional to size of memory
O(N) multiplied by the size of the directory O(N). Thus the total
memory overhead is square of number of processors O(N2)

Let us examine the transition from the second state to the third state in more detail. Once
processor P3 issues the write to cache C3, the following events will take place:
(1) Cache C3 detects that the block containing location X is valid but that the
processor does not have permission to write to the block, indicated by the
block‘s write-permission bit in the cache.
 (2) Cache C3 issues a write request to the memory module containing location X
and stalls processor P3.

(3) The memory module issues invalidate requests to caches Cl and C2.

(4) Caches Cl and C2 receive the invalidate requests, set the appropriate bit to
indicate that the block containing location X is invalid and send
acknowledgments back to the memory module.

(5) The memory module receives the acknowledgments, sets the dirty hit, clears
the pointers to caches Cl and C2, and sends write permission to cache C3.

(6) Cache C3 receives the write permission message, updates the state in the
cache, and reactivates processor P3.

The memory module waits to receive the acknowledgments before allowing processor P3
to complete its write transaction. By waiting for acknowledgments, the protocol
guarantees that the memory system ensures sequential consistency.

Qn:Explain the term Eviction?

2. Limited Directories

• Designed to Solves the directory size problem by restricting the number of

simultaneously cached copies of any particular block of data limits the growth of
the directory to a constant factor.
• A directory protocol can be classified as Diri X using the notation from Agarwal
et al (1988). The symbol i stands for the number of pointers, and X is NB for a
scheme with no broadcast A full-map scheme without broadcast is represented
as DirN NB. A limited directory protocol that uses i< N pointers is denoted
Diri NB.

Fig: 3.30

• the above fig shows situation when three cache request read copies
in a memory system with Dir2 NB protocol( only 2 copies are
allowed). The two pointer directory can be viewed as a two-way set
 associative cache.
• When cache C3 requests copy of location X, the memory module
must invalidate the copy in either C1 or C2 cache. This process of
pointer replacement is called eviction.

Qn: Describe gossip protocol?

3. Chained Directories
• Limited directories have a restriction on the number of shared copies
of data blocks.(due to the limitation of pointers).
• Chained directories will not have a restriction on the number of
shared copies of data blocks
• They Keeps track of shared copies of data by maintaining chain of
directory pointers.(Singly linked chain)

Fig: 3.31

• In the fig above singly linked chain, initially assume there are no
shared copies of location X.
• Processor P1 reads location X, the memory sends a copy to cache C1
along with chain termination (CT) pointer. The memory also keeps
a pointer to cache C1.
• Subsequently, When processor C2 reads location X, the memory
sends a copy to cache C2, along with the pointer to cache C1. The
memory then keeps a pointer to cache C2..

 By repeating the above step, all of the caches can cache a copy of the location X.
 If processor P3 writes to location X, it is necessary to send a data invalidation
message down the chain.
 To ensure sequential consistency, the memory module denies processor P3 write
permission until the processor with the chain termination pointer
acknowledges the invalidation of the chain.
 Perhaps this scheme should be called a gossip protocol (as opposed to a snoopy
protocol) because information is passed from individual to individual rather than
being spread by covert observation.
If processor P3 write to location X, data invalidation message has to be send down the
chain. Also called as gossip protocol

Cache Design Alternatives:

Qn:Distinguish between private caches and shared caches?

Beyond the use of private caches, three design alteratives are suggested below. Each of
the design alternatives has its own advantages and shortcomings. There exists insufiicient
evidence to determine whether any of the alternatives is always better or worse than the
use of private caches.

Shared Cache :
An alternative approach to maintaining cache coherence is to completely eliminate the
problem by using shared caches attached to shared-memory modules. No private caches
are allowed in this case. This approach will reduce the main memory access time but
contributes very little to reducing the overall memory-access time and to resolving access
conflicts.

Non-cacheable Data :
Another approach is not to cache shared writable data. Shared data are non cacheable,
and only instructions or private data are cacheable in local caches.
Shared data include locks, process queues. and any other data structures protected by
critical sections.
The compiler must tag data as either cacheable or non cacheable. Special hardware
tagging must be used to distinguish them.

Cache Flushing :
A third approach is to use cache flushing every time a synchronization primitive is
executed. This may work well with transaction processing multiprocessor systems. Cache
flushes are slow unless special hardware is used.
Flushing can be made very selective by the compiler in order to increase efficiency.
Cache flushing at synchronization, I/O and process migration may be carried out
unconditionally or selectively.

3.2.4 Hardware Synchronization Mechanisms

Synchronization is a special form of communication in which control information is
exchanged, instead of data, between communicating process residing in the same or
different processors. Synchronization enforces correct sequencing of processors and
ensures mutually exclusive access to shared writable data.

Multiprocessor systems use hardware mechanisms to implement low-level or primitive

synchronization operations(Discused Below). or use software (operating system) level
synchronization mechanisms such as Semaphores or monitors.

Hardware mechanisms to implement synchronisation are:

• Atomic Operations
• Wired Barrier Synchronization

Atomic Operations
• Atomic operations such as read, write, or read-modify-write can be used to
implement some synchronization primitives.
• some interprocessor interrupts can be used for synchronization purposes.
• For example , Test & Set and Reset (Lock) primitives are defined below:

• To synchronize concurrent processes, the software may repeat Test&.Set until the
returned value (temp) becomes 0.
• This synchronization primitive may tie up some bus cycles while a processor
enters busy-waiting on the spin lock.
• To avoid spinning, interprocessor interrupts can be used.
• Lock tied to an interrupt is called a suspended lock.

Wired Barrier Synchronization

 • Concurrent processes residing in different processors can be synchronized rising
barriers. A barrier can be implemented by a shared-memory word which keeps
counting the number of processes reaching the barrier.
• After all processes have updated the barrier count, the synchronization point
has been reached.
• No processor can execute beyond the barrier until the synchronization process is
complete.
 Each processor uses a dedicated control vector X = (X1, X2, ..., Xm) and
 accesses a common monitor vector Y = (y1, Y2, .... .ym) in shared
memory, where m corresponds to the barrier lines used.
 Each control bit X, is connected to the base (input) of a probing
transistor.
 The monitor bit yi checks the collector voltage (output) of the transistor.
 The wired-NOR connection implies that line i will be high (1) only if
control bits Xi, from all processors are low (0).
 This demonstrates the ability to use the control bit Xi to signal the
completion of a process on processor i.
 The bit Xi is set to 1 when a process is initiated and reset to 0 when
the process finishes its execution.

 When all processes finish their jobs, the xi bits from the participating processors are
all set to 0; and the barrier line is then raised to high (1), signalling the synchronization
barrier has been crossed.
 This timing is watched by all processors through snooping on the Yi bits. Thus only
one barrier line is needed to monitor the initiation and completion of a single
synchronization involving many concurrent processes.

Figure below shows the synchronization of four processes residing on four processors
using one barrier line.
Fig: 3.32
Another example using multiple barrier lines to monitor several synchronisation points is
shown below: (Optional)

Fig: 3.33