Concurrent Processors
• Processors that can execute multiple
instructions at the same time ( Concurrently)
• Concurrent processors can make
simultaneous access to memory and can
execute multiple operations simultaneously.
• These processors execute from one
program stream and have single instruction
counter but instructions are so rearranged
that concurrent instruction execution is
achieved.
Memory Coherence in Shared
Memory Multiprocessor
• Each node in a multiprocessor system
possesses a local cache.
• Since the address space of the processors
overlaps, different processors can be
holding (caching) the same memory
segment at the same time.
• Further each processor may be modifying
these cached location simultaneously.
• Cache coherency problem is to ensure that
all caches contain same most updated
copy of data.
Memory Coherence in Shared
Memory Multiprocessor
• The protocol that maintains the consistency
of data in all the local caches is called the
cache coherency protocol.
• The most important distinction among
various protocols is the way they distribute
information about writes to memory to the
other processors in the system.
– Snoopy Protocol: a write is broad cast to all
processors in the system
– Directory Based: Write is only sent to those
processors that are known to possess a copy.
Snoopy Protocol
• Snoopy protocols are simpler, as
ownership information need not be stored
in system.
• Theses protocols create great deal of
additional bus or network traffic while
doing the broadcast to all the processors.
• Snoopy protocols are bus based and used
in shared bus Multiprocessors.
• Snoopy protocols assume that all of the
processors are aware of , and receive, all
bus transactions ( snoop on the bus)
Snoopy Protocol
• Snoopy protocols are further classified
based on the type of action local
processor must take when an altered line
is recognized.
• There are two types of actions
– Invalidate: all copies in other caches are
invalidated before changes are made to data
in a particular line. The invalidate signal is
received from the bus and all caches which
posses the same cache line invalidate their
copies.
Snoopy Protocol
– Update: Writes are broadcast on the bus and
caches sharing the same line snoop for data
on the bus and update the contents and state
of their cache lines.
Another set of distinction among protocols is
based on if main memory is updated when a
write occurs or only cache contents are
updated.
Directory Based Protocols
• These protocols maintain the state
information of the cache lines at a single
location called directory.
• Only the caches that are stated in the
directory and are thus known to posses a
copy of the newly altered line, are sent
invalidate or write update information.
• Since there is no need to connect to all
caches, in contrast to snoopy protocols,
directory based protocols can scale better.
Directory Based Protocols
• As the number of processor nodes and
number of cache lines increase, the size of
directory can become very large.
• In addition to distinction based on action
taken by local processor in terms of
invalidate or update cache lines, there is
important distinction among directory
based protocols depending on directory
placement.
– Central Directory
– Distributed Directory
Directory Based Protocols
• Central Directory: Directory is placed or
associated with the memory system. Each
line in memory has an entry defining the
users of the line.
One bit vector per
Directory
memory line
1 0 1 0
Cache 2 Cache 1 Cache 0
Cache3
Directory Based Protocols
• Distributed Directory: Memory has only
one pointer which identifies the cache that
last requested it. A subsequent request to
that line is then referred to that cache and
requestor Id is placed at the head of list.
One bit vector per
Directory
memory line
3
Cache 0 Cache 2 Cache 1
Cache3 T
0 2
Directory Based Protocols
• In the distributed directory this process is
done serially through the use of the lists.
• In update protocols using central directory,
the directory sends a count number to the
writer ( indicating no. of users).
• Processors having copy of the line are
informed that line is being updated along
with write data.
• The processors after updating send ack to
writing cache. ( Total ack = Count)
Directory Based Protocols
• In distributed directory, writing processor
becomes head of the list then update
signal together with new data is forwarded
down the list.