|
Unit 4 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
[RGPV JUN 13, JUN 15 (7)] Cache coherence is the discipline
that ensures that changes in the values of shared operands are propagated
throughout the system in a timely fashion. When clients in a system maintain caches of a common memory resource,
problems may arise with inconsistent data. This is particularly true of CPUs
in a multiprocessing system. In a shared memory
multiprocessor with a separate cache memory for each processor , it is
possible to have many copies of any one instruction operand : one copy
in the main memory and one in each cache memory. When one copy of an operand
is changed, the other copies of the operand must be changed also. Cache
coherence is the discipline that ensures that changes in the values of shared
operands are propagated throughout the system in a timely fashion When clients in a system maintain caches of a common memory resource,
problems may arise with inconsistent data. This is particularly true of CPUs
in a multiprocessing system. Referring to the "Multiple
Caches of Shared Resource" figure, if the top client has a copy of a
memory block from a previous read and the bottom client changes that memory
block, the top client could be left with an invalid cache of memory without
any notification of the change. Cache coherence is intended to manage such
conflicts and maintain consistency between cache and memory. A coherency protocol is a protocol which maintains the consistency
between all the caches in a system of distributed shared
memory.
The protocol maintains memory coherence according to a specific consistency model. Older multiprocessors
support the sequential consistency model, while modern
shared memory systems typically support the release consistency or weak consistency models. The release consistency or weak consistency models. Transitions between
states in any specific implementation of these protocols may vary. For
example, an implementation may choose different update and invalidation
transitions such as update-on-read, update-on-write, invalidate-on-read, or
invalidate-on-write. The choice of transition may affect the amount of
inter-cache traffic, which in turn may affect the amount of cache bandwidth
available for actual work. This should be taken into consideration in the
design of distributed software that could cause strong contention between the
caches of multiple processors. Various models and
protocols have been devised for maintaining cache coherence, such as MSI protocol,
MESI
(aka Illinois protocol), MOSI,
MOESI,
MERSI,
MESIF,
write-once, Synapse, Berkeley, Firefly
and Dragon protocol A protocol manages the caches of a
multiprocessor system so that no data is lost or overwritten before the data
is transferred from a cache to the target memory. When two or more computer
processors work together on a single program, known as multiprocessing, each
processor may have its own memory cache that is separate from the larger RAM
that the individual processors will access. A memory cache, sometimes called
a cache store or RAM cache, is a portion of memory made of high-speed static
RAM (SRAM) instead of the slower and cheaper dynamic RAM (DRAM) used for main
memory. Memory caching is effective because most programs access the same
data or instructions over and over. By keeping as much of this information as
possible in SRAM, the computer avoids accessing the slower DRAM. When multiple
processors with separate caches share a common memory, it is necessary to
keep the caches in a state of coherence by ensuring that any shared operand
that is changed in any cache is changed throughout the entire system. This is
done in either of two ways: through a directory-based or a snooping system
Reference{kai hwang ,advance computer architecture}
[RGPV JUN 12,14(7)] In a snooping system,all caches on the bus monitor (or
snoop) the bus to determine if they have a copy of the block of data that is
requested on the bus. Every cache has a copy of the sharing status of every
block of physical memory it has. Cache misses and memory traffic due to
shared data blocks limit the performance of parallel computing in
multiprocessor computers or systems. Cache coherence aims to solve the
problems associated with sharing data. Detail: In a
bus-based multiprocessor system, cache coherence can be ensured using a
snoopy protocol in which each processor's cache monitors the traffic on the
bus and takes appropriate action when it sees a write request being sent to
memory for a variable at an address matching one that it holds. This website
contains a number of models demonstrating different types of snoopy protocol:
Write Through / Write Invalidate Model
• Write to shared data: an invalidate
is sent to all caches which snoop and invalidate any copies • Cache invalidation will force a
cache miss when accessing the modified shared item • For multiple writers only one will
win the race ensuring serialization of the write operations • Read Miss: – Write-through: memory is always
up-to-date –
Write-back: snoop in caches to find most recent copy Write
Broadcast (Update) Protocol (typically write through): • Write to shared data: broadcast on
bus, processors snoop, and update any copies • To limit impact on bandwidth,
track data sharing to avoid unnecessary broadcast of written
data that is not shared • Read miss: memory is always
up-to-date • Write
serialization: bus serializes requests! Copyback / Write Invalidate Protocol
The
Copyback / Write Invalidate protocol (see section 8.9 of Michael J. Flynn's
book on "Computer Architecture" (ISBN 0-86720-204-1) requires each
cache line to have two status bits: Valid and Modified. Each line can be in
one of three possible states: Snooping
Solution (Snoopy Bus) • Send all requests for data to all
processors • Processors snoop to see if they
have a copy and respond accordingly • Requires broadcast, since caching
information is at processors • Works well with bus (natural
broadcast medium) • Dominates for small scale machines
Snoopy-Cache
Controller Complications • Cannot update cache until bus is
obtained • Two step process:
– Arbitrate for bus
– Place miss on bus and complete operation • Split transaction bus:
– Bus transaction is not atomic
– Multiple misses can interleave, allowing two caches to grab block in
the Exclusive state
– Must track and prevent multiple misses for one block
Reference{kai hwang ,advance computer architecture}
[RGPV JUN 13,15(7)] These snoopy bus-based
systems are easy to build, but unfortunately as the number of processors on
the bus increases, the single shared bus becomes a bandwidth bottleneck and
the snoopy protocol’s reliance on a broadcast mechanism becomes a severe
scalability limitation. To address these
problems, architects have adopted the distributed shared memory (DSM)
architecture. In a DSM multiprocessor each node contains the processor and
its caches, a portion of the machine’s physically distributed main memory,
and a node controller which manages communication within and between nodes.
Rather than being connected by a single shared bus, the nodes are connected
by a scalable interconnection network. The DSM architecture allows
multiprocessors to scale to thousands of nodes, but the lack of a broadcast
medium creates a problem for the cache coherence protocol. Snoopy protocols
are no longer appropriate, so instead designers must use a directory-based
cache coherence protocol. Directory per cache that tracks state
of every block in every cache • Which caches have a copy of block,
dirty vs. clean • Info per memory block vs. per
cache block? – PLUS: In memory => simpler
protocol (centralized/one location) – MINUS: In memory => directory
is ƒ(memory size) vs. ƒ(cache size) To prevent directory from being a
bottleneck, distribute directory entries with memory, each keeping track of
which processor have copies of their blocks Similar
to Snoopy Protocol: Three states • Shared: Multiple processors have
the block cached and the contents of the block in memory (as well as all
caches) is up-to date. • Uncached No processor has a copy
of the block (not valid in any cache) • Exclusive: Only one processor
(owner) has the block cached and the contents of the block in memory is
out-to-date (the block is dirty) In addition to cache state, must
track which processors have data when in the shared state • usually bit vector, 1 if processor
has copy • Writes to non-exclusive data =>
write miss • Processor blocks until access
completes • Assume messages received and acted
upon in order sent Terms:
typically 3 processors involved • Local node where a request
originates • Home node where the memory
location of an address resides • Remote node has a copy of a cache
block, whether exclusive or shared No
bus and do not want to broadcast: • interconnect no longer single
arbitration point • all messages have explicit
responses Example
Directory Protocol Message sent to directory causes two
actions: • Update the directory • More messages to satisfy request We assume operations atomic, but
they are not; reality is much harder; must avoid deadlock when run out of
buffers in network
[RGPV JUN 13(7)] Routing
in multicomputer
In most multicomputer systems, a message enters the
network from a source node and is switched or routed towards its destination
through a series of intermediate nodes.
1. circuit switching /routing 2. packet switching/routing 3. virtual cut-through switching
/routing 4. wormhole switching. /routing circuit switching
/routing ·
In
circuit switching, a dedicated path is established between the source and the
destination before data transfer initiates. ·
Once
the data transfer is initiated the message is never blocked. ·
As
the channels creating the path are reserved exclusively, buffering of data is
not required. ·
On
the other hand, establishing the path requires significant overhead: during
the data-transmission phase, all
channels are reserved for the entire duration of message transfer. ·
Circuit
switching thus degrades performance and is no longer used in commercial
multicomputer systems.
·
In
packet switching, a message is divided into packets that are independently
routed towards its destination. ·
The
destination address is encoded in the header of each packet. The entire packet
is stored at every intermediate node and then forwarded to the next node in
its path. ·
The
main advantage of packet switching is that the channel resource is occupied
only when a packet is actually transferred.
·
In
order to reduce the time to store the packets at each node, Kermani and
Kleinrock introduced a technique called virtual cut-through ·
In
this, while routing toward its destination, a message is stored at an
intermediate node only if the next channel required is occupied by another
packet. ·
Now,
the distance between the source and destination has little effect on
communication latency.
·
Wormhole
switching is a variant of the virtual cut-through technique that avoids the
need for large buffer spaces. ·
In
wormhole switching, a packet is transmitted between the nodes in units of
flits, the smallest units of a message on which flow control can be
performed. ·
The
header flit(s) of a message contains all the necessary routing information
and all the other flits contain the data elements. The flits of the message
are transmitted through the network in a pipelined fashion
[RGPV JUN 12(10)] Deadlock occurs when multiple processes in networked computers request
for resources and that is not available to the process for infinite time,
this condition is called the deadlock. A situation where there are activities (e.g.,
messages each waiting for another to finish something. Since a waiting
activity cannot finish, deadlock is forever. A situation where a message can move from node to node but will never
get to its destination. Starvation The fate of a contender for a resource that is never granted
the resource due to an unfair contention-resolution policy. Handling Deadlock
Clearing Deadlock Detecting deadlock for certain too time consuming.Possible
Implementation: Compression-Free
Routing
Resource Dependence A relationship between two resources indicating the first may
not be available until after the second is available. (That is,
the first needs the second to finish what it's doing.) Network Resources
Dependence Graph
Network Dependence Graph
Acyclic Dependence Example: Dimension-Order Mesh
Routing Route mesh in dimension order. Is minimal (good) but oblivious (bad). Virtual Channel: A connection between two nodes which can be used as a single link but which physically must share a link
with other virtual channels. To routing and flow control mechanisms,
virtual channel equivalent to link. Since multiple virtual channels
can share a single link bandwidth
of each virtual channel less than link. Virtual Channel Deadlock-Free KNC Routing Example Avoiding deadlock in 5-ary 1-cube:
•
.
A vector is a set of scalar data
items, all of the same type, stored in memory. Usually, the vector elements
are ordered to have a fixed addressing increment between successive elements
called the stride. •
Vector instructions: One or two vector operands are fetched form
the respective vector registers, enter through a functional pipeline unit,
and produce result in another vector register. •
To access a vector a memory, one must specify its
base, stride, and length. •
Since each vector register has fixed length, only
a segment of the vector can be loaded into a vector register. Vector Processing Principles •
A vector is a set of scalar data items, all of
the same type, stored in memory. Usually, the vector elements are ordered to
have a fixed addressing increment between successive elements called the
stride. •
A vector processor is an ensemble of hardware
resources, including vector registers, functional pipelines, processing
elements, and register counters, for performing vector operations. Vector
processing occurs when arithmetic or logical operations are applied to
vectors. The conversion from scalar processing to vector code is called
vectorization. Vector processing speedup 10..20 compared with scalar
processing. A compiler capable of vectorization is called vectorizing
compiler or vectorizer. Vector instructions 1.
Vector-vector instructions One or two vector operands are fetched form the
respective vector registers, enter through a functional pipeline unit, and
produce result in another vector register. 2.
Vector-scalar instructions 3. vector-memory
instructions Store-load of vector registers 4. Vector
reduction instructions maximum, minimum, sum, mean value. 5. Gather
and scatter instructions Two instruction registers are used to gather or
scatter vector elements randomly through the memory (operations with sparse
vectors). 6.
Masking instructions The Mask vector is used to compress or to expand a
vector to a shorter or longer index vector (bit per index correspondence). Vector-access memory schemes •
Vector operands may have arbitrary length. •
Vector elements are not necessarily stored in
contiguous memory locations. •
To access a vector a memory, one must specify its
base, stride, and length. •
Since each vector register has fixed length, only
a segment of the vector can be loaded into a vector register. •
Vector operands should be stored in memory to
allow pipelined and parallel access. Access itself should be pipelined. •
C-Access memory organization The m-way low-order
memory structure, allows m words to be accessed concurrently and overlapped. •
S-Access memory organization All modules are
accessed simultaneously storing consecutive words to data buffers. The low
order address bits are used to multiplex the m words out of buffers. •
C/S-Access memory organization. •
Eight-way interleaved memory (m = 8 and w = 8). m
is called the degree of interleaving. •
The major cycle
is the total time required to complete the access of a single word
form a memory. The minor cycle is the
actual time needed to produce one word, assuming overlapped access of successive
memory modules separated in every memory cycle .
The Synchronous parallel architectures coordinate
Concurrent operations in lockstep through global clocks, central control
units, or vector unit controllers. A synchronous array of parallel processors
is called an array processor. These processors are composed of N identical
processing elements (PES) under the supervision of a one control unit (CU)
This Control unit is a computer with high speed registers, local memory and arithmetic logic unit.. An array
processor is basically a single instruction and multiple data (SIMD)
computers. There are N data streams; one per processor, so different data can
be used in each processor These processors consist of a number of memory modules which can be
either global or dedicated to each processor. Most SIMD computers use a single control
unit and distributed memories, except for a few that use associative
memories, Spatial parallelism among PEs. A distributed memory SIMD consists
of an array of PEs (supplied with local
memory) which are controlled by the array control unit. Program and data are loaded into the control memory through the host computer and
distributed from there to PEs local memories. Distributed SIMD model •
In this
type of model, memories are distributed to all the processors. Each processor
has its own local memory SIMD models dierentiates on base of memory
distribution and addressing scheme used. Most SIMD computers use a single
control unit and distributed memories, except for a few that use associative
memories. •
Distributed
memory model : Spatial parallelism among PEs. A distributed memory SIMD consists of an array of PEs
(supplied with local memory) which are controlled by the array control
unit. Program and data are loaded into the control memory through the host computer
and distributed from there to PEs local memories. Shared
SIMD model In this type of model, memories are shared
among all the processors. Each processor has shared global memory
[ RGPV JUN 15 (2),JUN 14(7)] he ability
of an operating system
to execute
different parts of a program,
called threads, simultaneously.
The programmer
must carefully design the program in such a way that all the threads can run
at the same time without interfering with each other Requirements of Multithreading •
Storage
need to Processor Utilization vs.
Latency •
hold
multiple context’s PC, registers, status word, etc. •
Coordination
to match an event with a saved context •
A way to
switch contexts •
Long
latency operations must use resources not in use . Process communication ·
Shared
Memory ·
Potential
long latency on every load –
Cache
coherency becomes an issue –
Examples
include NYU’s Ultra computer, IBM’s RP3, BBN’s Butterfly, MIT’s Alewife, and
later Stanford’s Dash. –
Synchronization
occurs through share variables, locks, flags, and semaphores. Message
Passing –
Programmer deals with
latency. This enables them to minimize
the number of messages, while maximizing the size, and this scheme allows for
delay minimization by sending a message so that it reaches the receiver at
the time it expects it. –
Examples include Intel’s PSC and
Paragon, Caltech’s Cosmic Cube, and Thinking Machines’ CM-5 –
Synchronization occurs through
send and receive Features –
An instruction from a different
context is launched at each clock cycle –
No interlocks or bypasses thanks
to a non-blocking pipeline –
Optimizations: –
Leaving context state in proc
(PC, register #, status) –
Assigning tags to remote request
and then matching it on completion Simultaneous Multithreading •
Straightforward extension to
conventional superscalar design. –
multiple program counters and
some mechanism by which the fetch unit selects one each cycle, –
a separate return stack for each
thread for predicting subroutine return destinations, –
per-thread instruction
retirement, instruction queue flush, and trap mechanisms, –
a thread id with each branch
target buffer entry to avoid predicting phantom branches, and –
a larger register file, to
support logical registers for all threads plus additional registers for register
renaming. The size of the register
file affects the pipeline and the scheduling of load-dependent instructions
Reference{kai hwang ,advance computer architecture} . |
