PARALLEL COMPUTING

Chapter Three: Parallel Computer Architectures & Networks

-Introduction
 Motivation for parallel architectures (performance, scalability, efficiency)
 Challenges in parallel systems (communication, synchronization, memory
access or memory bandwidth, race conditions, deadlocks, consistency)
-Parallel Architectures
 Overview of parallel computer architectures
 Shared memory systems
 Uniform Memory Access (UMA)
 Non-Uniform Memory Access (NUMA)
 Cache coherence (cache coherence problem, Cache coherence
protocols(Snooping protocols & Directory-based protocols))
 Distributed-memory systems (i.e. Message passing model)
 Hybrid memory systems
 Advantages and limitations of each architectures
-Role of Interconnection networks and routing protocols in
parallel systems
 Introduction
 Why do you need to know about hardware architecture?
 Hardware determines (parallel) software performance. In order to write
efficient parallel software, you must be aware of the hardware design and
constraints.
 It is ultimately the hardware architecture that determines the cost
(execution time) associated with each algorithmic idea.
 Parallel Computer Architecture is actually a type (or extension) of computer
hardware architecture.
 How multiple processors/cores, memory, caches and interconnections are
designed and organized in hardware to execute tasks in parallel.
 Computer Architecture (in general)→ Design of a computer system (CPU,
memory, I/O)
 Parallel Computer Architecture→ Design of systems with multiple processing
units working together
 Introduction
 Why do you need to know about hardware architecture?
 Much of parallel computer architecture is about:-
 Designing machines that overcome the sequential and parallel bottlenecks to achieve
higher performance and efficiency.
 Making programmer’s job easier in writing correct and high-performance parallel
programs
 Ordering of operations such as: A, B, C, D
 In what order should the hardware execute (and report the results of) these
operations?
 Preserving an “expected” (more accurately, “agreed upon”) order simplifies
programmer’s life
 Ease of debugging; ease of state recovery, exception handling
 Preserving an “expected” order usually makes the hardware designer’s life
difficult
 Especially if the goal is to design a high-performance processor
 Processors want to do things out-of-order for performance! But make it
appear in-order externally (for correctness)
prints the message "Hello, world:"
prints the message "Hello, world:"
to the console.

. to the console.

Essential techniques for managing shared resources in

parallel programming (issues memory, synch, race
conditions, order, mutual exclusions, deadlocks…..)
 #pragma omp critical:
 This directive specifies that a block of code should be executed by only one thread at a
time, ensuring that no two threads enter the critical section simultaneously. This is useful
for protecting shared resources.
 #pragma omp barrier:
 This directive creates a barrier in the code where all threads must synchronize before any
thread can continue. It ensures that all threads reach this point before proceeding.
 #pragma omp atomic:
 This directive ensures that a specific update to a variable is done atomically, preventing
race conditions without the overhead of a critical section.
 False Sharing
 False sharing happens when multiple threads access different variables, but those
variables are stored in the same cache line, causing unnecessary cache invalidation and
performance loss. Bring it into true sharing via padding, MESI……..
prints
printsthe
themessage
message"Hello, world:"
to the console.

"Hello, world:"
prints the message "Hello, world:"
to the console.

to the console.

Classic Introductory OpenMP C program

 #include <stdio.h>
 #include <omp.h>
 int main() {
 printf("Hello, world:"); // prints the message "Hello, world:" to the console.
 #pragma omp parallel // Create multiple threads and execute the following
block in parallel.
 printf(" %d", omp_get_thread_num());
 printf("\n");
 return 0; // ends the program
 }
prints
printsthe
themessage
message"Hello, world:" to the console.

"Hello, world:"
prints the message "Hello, world:"
to the console.

to the console.

Parallel C program with OpenMP

 Parallelism vs Order
 Threads execute in parallel → faster
 But output order is unpredictable, invites race conditions, output may be mixed
 So parallel computer architectures have been designed but must be enforced
not to do in parallel by programmers
 Hardware allows parallel execution
 But order is not guaranteed unless enforced
 If we want to control some basic problems such as clean output (no mixed
o/t), race conditions, we can make the parallel section as follows
 #pragma omp parallel{
 #pragma omp critical
 printf(" %d", omp_get_thread_num());
}
prints
printsthe
themessage
message"Hello, world:"
to the console.

"Hello, world:"
prints the message "Hello, world:"
to the console.

to the console.

Modified Program (Using barrier)

 #include <stdio.h>
 #include <omp.h>
Barrier = Hardware Synchronization
 intmain() { Hello, world: 2 0 3 4?
 printf("Hello, world:");
 #pragma omp parallel {
 printf(" %d", omp_get_thread_num());
 #pragma omp barrier // Synchronization point
 #pragma omp single
 printf("\n"); // Only one thread prints newline after all threads finish
}
 return 0;
}
 Components of Parallel Computer Architecture

 Components explain what the parallel system is made of and how

parallelism is physically achieved.
 Why components are necessary?
 Discussing components helps to answer:
 What makes parallel computing possible?
 How do multiple processors work together?
 Where do performance issues (like synchronization or cache coherence) come from?
 Components connect theory (parallelism) with real hardware design
 Main Components of Parallel Computer Architecture
 Processing Elements (CPUs (multi-core processors), GPUs, APUs, FPUs)
 Memory system (RAM, caches) (Memory Hierarchy)
 Interconnection networks
 I/O System, synchronization mechanisms, and execution models.
 Components of Parallel Computer Architecture

 Processors are the central processing units responsible for executing

instructions and performing computations in parallel computing systems.
 Different types of processors, such as CPUs, GPUs, and APUs, offer varying
degrees of parallelism and computational capabilities.
 Central Processing Units (CPU)
Multi-core CPUs: These CPUs feature multiple processing cores
integrated onto a single chip, allowing parallel execution of tasks.
Each core can independently execute instructions, enabling higher
performance and efficiency in multi-threaded applications.
Multi-threaded CPUs: Multi-threaded CPUs support the simultaneous
execution of multiple threads within each core. This feature enhances
throughput and responsiveness by overlapping the execution of
multiple tasks, particularly in applications with parallelizable
workloads.
 Components of Parallel Computing Architecture

 Graphical Processing Units (GPU)

 Stream processors: GPUs consist of numerous stream processors,
also known as shader cores, responsible for executing computational
tasks in parallel. These processors are optimized for data-parallel
operations and are particularly well-suited for graphics rendering,
scientific computing, and machine learning tasks.

CUDA cores: CUDA (Compute Unified Device Architecture) cores

are specialized processing units found in NVIDIA GPUs. These cores
are designed to execute parallel computing tasks programmed using
the CUDA parallel computing platform and application programming
interface (API). CUDA cores offer high throughput and efficiency for
parallel processing workloads.
 Components of Parallel Computing Architecture

 Accelerated Processing Units (APU)

CPU cores: Accelerated Processing Units (APUs) integrate
both CPU and GPU cores on a single chip. The CPU cores
within APUs are responsible for general-purpose computing
tasks, such as executing application code, handling system
operations, and managing memory.

GPU cores: Alongside CPU cores, APUs also include GPU

cores optimized for parallel computation and graphics
processing. These GPU cores provide accelerated performance
for tasks such as image rendering, video decoding, and parallel
computing workloads.
Components of Parallel Computing Architecture
 Components of Parallel Computing Architecture

 Registers
 General-purpose registers: Registers directly accessible by the CPU cores for storing
temporary data and intermediate computation results.
 Special-purpose registers: Registers dedicated to specific functions, such as program
counter, stack pointer, and status flags, essential for CPU operations and control flow.
 Cache Memory
 L1 Cache: Level 1 cache located closest to the CPU cores, offering fast access to
frequently accessed data and instructions.
 L2 Cache: Level 2 cache situated between L1 cache and main memory, providing larger
storage capacity and slightly slower access speeds.
 L3 Cache: Level 3 cache shared among multiple CPU cores, offering a larger cache size
and serving as a shared resource for improving data locality and reducing memory access
latency.
 Components of Parallel Computing Architecture

 Main Memory (RAM)

 Dynamic RAM (DRAM): Main memory modules composed of dynamic
random-access memory cells, used for storing program instructions and
data during program execution.
 Static RAM (SRAM): Caches and buffer memory within the memory
hierarchy, offering faster access speeds and lower latency compared to
DRAM because it uses flipflops to store data rather DRAM uses
capacitors and transistors to store data, which needs charging and
discharging for storing and increase latency. Closer to the CPU
compared to DRAM.
 Video RAM (VRAM): Dedicated memory on GPUs used for storing
textures, framebuffers, and other graphical data required for rendering
images and videos. VRAM enables high-speed access to graphics data
and enhances the performance of GPU-accelerated applications.
 Components of Parallel Computing Architecture
Secondary Storage (Disk)
 Hard Disk Drives (HDDs): Magnetic storage devices used for long-term data storage and
retrieval in parallel computing systems. HDDs provide high-capacity storage but slower access
speeds compared to main memory.
 HDDs have slower read and write speeds and higher latency than SSDs, making them less
suitable for parallel computations that demand speed.
 HDDs have slower random-access times compared to SSDs, which can hinder performance in
parallel computing scenarios.
 SSDs tend to be more expensive per gigabyte than HDDs.
 Solid State Drives (SSDs): Flash-based storage devices offer faster access speeds and lower
latency than HDDs. SSDs are commonly used as secondary storage in parallel computing
systems to improve I/O performance and reduce data access latency.
 SSDs offer much faster read and write speeds compared to HDDs, leading to quicker data
access and processing times.
 SSDs have lower latency (the time it takes to access data), which is crucial for parallel
computations where rapid data retrieval is essential.
 SSDs excel at random access, meaning they can quickly access data from any location on the
drive, a key advantage for parallel processing that often involves accessing data from various
locations.
Components of Parallel Computing Architecture
 Components of Parallel Computing Architecture

 Interconnection Networks
 In a shared memory MP, we need to connect different processors and
 memory modules
 Types of interconnect:
➢Shared bus
➢Crossbar: Fully connected
➢Ring
➢Mesh
➢2-D Torus
➢Hypercube
 Number of hops vs. number of links: Compare N processors and M memory
modules
 Components of Parallel Computing Architecture

 Buses
 System Bus: Connects the CPU, memory, and other internal
components within a computer system. It facilitates
communication and data transfer between these components.

 Memory Bus: Dedicated bus for transferring data between the CPU
and main memory (RAM). It ensures fast and efficient access to
memory resources.

 I/O Bus: Input/Output bus connects peripheral devices, such as

storage devices, network interfaces, and accelerators, to the CPU
and memory in a parallel computing system.
 Components of Parallel Computing Architecture

 Switches
 Crossbar Switches: High-performance switches that provide multiple paths for data transmission
between input and output ports. They enable simultaneous communication between multiple pairs of
devices, improving bandwidth and reducing latency.
 Packet Switches: Switches that forward data in discrete packets based on destination addresses.
They efficiently manage network traffic by dynamically allocating bandwidth and prioritizing
packets based on quality of service (QoS) parameters.
 Networks
 Ethernet: A widely used networking technology for local area networks (LANs) and wide area
networks (WANs). It employs Ethernet cables and switches to transmit data packets between
devices within a network.
 InfiniBand: A high-speed interconnect technology commonly used in high-performance computing
(HPC) environments. It offers low-latency, high-bandwidth communication between compute nodes
in clustered systems.
 Fiber Channel: A storage area network (SAN) technology that enables high-speed data transfer
between servers and storage devices over fiber optic cables. It provides reliable and scalable
connectivity for enterprise storage solutions.
Components of Parallel Computing Architecture
 One definition of parallel computer architecture
 A parallel computer is a collection of processing elements, memory &
caches that cooperate to solve large problems fast. Key issues:
 Resource Allocation:- This is about how you design the system
 how large a collection? How many processors do we need? Is there multicore
processor? Or Is there GPU HW in that of we want to implement parallelism?
 how powerful are the elements? How powerful should each processor be?
 how much memory? Cache?
 Data access, Communication and Synchronization:-This is the heart of parallel computing
 how do the elements cooperate and communicate? How do processors talk?
 how are data transmitted between processors? How do they share data?
 what are the abstractions and primitives for cooperation? How do they coordinate?

 Performance and Scalability:- This is about how fast the system actually runs
 how does it all translate into performance?
 Does adding processors really make it faster? What happens when we keep adding processors?
 One definition of parallel computer architecture
 A parallel architecture is defined by how these three things work together:
 1. Resources allocation (hardware design)
 2. Communication & coordination (interaction)
 3. Performance & scalability (result)-Speedup achieved, Efficiency, Ability to grow system
 Parallel architecture performance depends on the interaction between
resource allocation, communication, and synchronization mechanisms.
 Efficient systems minimize communication overhead, balance workload
among processors, and provide scalable interconnection networks.
 Poor coordination or excessive communication limits scalability and reduces
performance.
 The efficiency of a parallel architecture is determined by how well its
hardware resources support low-cost communication and synchronization to
achieve scalable performance.
 Why study parallel arch & programming models?
 The Answer before 15 or more years: High Performance (Speed)
 Because it allows you to achieve high performance beyond what we get with CPU clock frequency
scaling.
 To achieve higher performance by increasing CPU clock frequency. Performance was improved
mainly by: Increasing clock speed (GHz scaling)
 The Answer Today: Everywhere Computing + Efficiency + Scalability + Speedup
 Because it seems to be the best available way to achieve higher performance in the foreseeable
future. Now it is the main path to performance improvement, is not clock speed.
 CPU clock rates are no longer increasing! ---The higher the clock speed, the more heat is
generated, and we've now hit a stage where it is no longer efficient to increase processor
Parallelism speed due to the amount of energy that goes into cooling it.
 Instruction-level-parallelism is not increasing either!
 Improving performance further on sequential code becomes very complicated +
diminishing returns
 Without explicit parallelism or architectural specialization, performance becomes a zero-sum game.
 Specialization is more disruptive than parallel programming (and is mostly about parallelism
anyway)
 Why study parallel arch & programming models?
 In the past, CPUs were designed with a single core running at very high clock
frequencies, because increasing the clock speed was the main way to improve
performance.
 However, this approach reached physical limits due to heat generation and high-
power consumption, making it difficult to keep increasing the clock frequency.
 CPU clock speed scaling has stopped due to heat and power limits, and instruction-level parallelism
has reached diminishing returns.

 As a result, improving performance now depends mainly on parallel computing and

parallel computer architectural specializations.
 Modern CPUs are designed with multiple cores running at moderate clock speeds
instead of one very fast core.
 Each core can execute tasks simultaneously, allowing the system to perform many operations in
parallel.
 This shift means that performance improvement now comes from parallel execution across multiple
cores, rather than just increasing the speed of a single core.
 Parallel Computer Architectures
Parallel architectures are generally classified based on memory
 Shared Memory organization and communication style.
 Distributed Memory Common Parallel Architectures
 Hybrid Memory
 Historically, parallel architectures were tightly coupled to specific programming models,
leading to divergent architectures with no clear, and predictable growth pattern.
 The development of parallel computer architectures and the programming models used to
write software for them were closely intertwined.
 As a result of this tight coupling, different parallel architectures emerged, each with
unique characteristics and programming models, leading to a landscape of diverse and
sometimes incompatible systems.
 The lack of a unified approach to parallel computing and the proliferation of different
architectures and programming models resulted in a pattern of growth that was not easily
predictable or scalable.
 Each new architecture often required a new set of programming tools and techniques,
hindering widespread adoption and standardization.
 What is the solution for decoupling?
 The solution to the problem of tightly coupled parallel architectures and
programming models, which led to divergent and sometimes incompatible
systems?
 Focus on standardization, abstraction, and portability to break away from

the historical tight coupling between hardware and software which leads to
the above most common parallel architectures.
 When we say parallel architectures that are tightly coupled to specific programming
models, meaning the hardware design is optimized for a particular way of expressing
parallelism.
 The introduction of high-level programming models has been a critical step in decoupling
parallel hardware from specific software paradigms.
 Programming models like OpenMP and CUDA offer higher-level abstractions, allowing
developers to focus on parallelism without worrying about the specific hardware being
used.
 These models provide a consistent interface to parallelize code, whether you're running on
a multi-core CPU, a GPU, or even a distributed system.
 What is the solution for decoupling?
 OpenMP: A directive-based parallel programming model that enables multi-
threading within shared-memory systems. By using compiler directives,
OpenMP allows for parallel execution without needing to worry about the
underlying hardware architecture.
 CUDA: A parallel computing platform and application programming interface
(API) that allows developers to write software that can run on GPUs,
abstracting away the hardware-specific intricacies.

 Message-Passing Interfaces (MPI): For distributed-memory systems, MPI

standardized how processes communicate in a parallel environment.
 By abstracting the communication between processors, MPI allowed for a more
portable way of writing parallel programs that could run on different distributed
architectures, without being tightly coupled to the underlying hardware.
 Shared Memory Architecture
 Shared Memory Architecture
 All processors (cores) share a single global memory space.
 Data is stored in a single global memory accessible by all processors.
 Every processor (or core) can read from and write to the same global physical
memory space (RAM).
 Processors share memory resources, but can operate independently
 One processor’s memory changes are seen by all other processors
 Easier to program
➢Communication occurs through shared variables
➢Synchronization through locks, semaphores, barriers, critical stored in shared
memory
 Need interconnection network between all processors and all memory
 Two Types of architectures:
➢Uniform Memory Architectures (UMA): e.g., Symmetric Multiprocessors
➢Non-Uniform Memory Architectures (NUMA): Access & latency to memory is different
 Uniform Memory Access (UMA
 Uniform Memory Access (UMA) and Non-Uniform Memory Access (NUMA) are
architectures defining how processors access shared memory.
Uniform Memory Access (UMA):
 All processors in a UMA system have equal access times to any memory location.
 A single memory is used and accessed by all the processors present the
multiprocessor system with the help of the interconnection network.
 Each processor has equal memory accessing time (latency) and access speed.
 It can employ either of the single bus, multiple bus or crossbar switch.
 As it provides balanced shared memory access, it is also known as SMP (Symmetric
multiprocessor) systems.
 Equal memory access, single memory controller, shared memory pool (shared bus)
 Bandwidth is divided and ideal for small systems
 Latency and bandwidth are the same for all processors and all memory locations.
 This is also called a symmetric multiprocessor (SMP).
 The latency to a word in memory does not depend on which processor/core asks for it.
 Uniform Memory Access (UMA
(Single
UMA)

Where:-
 Each processor is first connected to the cache then the cache is linked to the bus.
 At last, the bus is connected to the memory.
 This UMA architecture reduces the contention for the bus through fetching the
instructions directly from the individual isolated cache.
 It also provides an equal probability for reading and writing to each processor.
 Uniform Memory Access (UMA
 UMA uses single, multiple, crossbar buses

 Limitations of UMA
 Limited scalability
 Bandwidth bottleneck
 Memory contention
 Restricted memory capacity
 Not ideal for larder/complex systems
 Non-Uniform Memory Access (NUMA)
 Each processor has its own local memory, and access to that local memory is faster
than accessing memory on another processor's board (remote memory).
 NUMA is often used in systems with multiple SMPs linked together.
 Suitable for real-time and time-critical applications where faster access to local data
is crucial.
 Not all processors have equal access time to all memories
 Memory is physically distributed but logically shared among all cores
 Every CPU can access all memory but access time depend on location.
 If cache coherency is maintained, then may also be called CC-NUMA - Cache
Coherent NUMA
 HOW DOES IT WORK ?
 A CPU first checks the L1 cache on the microprocessor when searching for data
at a certain memory address.
 After then, it switches to the larger L2 cache chip before reaching the third level
of cache (L3). This third level is provided by the NUMA setup.
 The processor will check the distant memory, which is close to the other
microprocessors, if it is still unable to locate the data.
 Non-Uniform Memory Access (NUMA)
 One drawback of SMP is that when more processors are added, the shared
bus or data channel becomes overloaded, which slowing down performance.
 In order to prevent all accessible data from travelling on the main bus,
NUMA adds an intermediate level of memory that is shared across a few
microprocessors.
 This aids in addressing performance bottleneck problems in UMA.
 Non-Uniform Memory Access (NUMA)
 NUMA?
 Local and remote memory
A processor can access both its local memory and remote memory attached to other
processors.
 Faster local access
 Every processor access to its local memory is much faster than accessing
remote memory attached to other processors.
 This non-uniformity in access times is the key features of NUMA.
 Scalable architecture than UMA
 Multiple memory controllers but one MC in UMA
 Ideal for larger/complex systems
 Shared Memory Architecture
 Shared Memory Multiprocessors: Memory Hierarchy
 Problem: sharing memory means more than one processor can send requests to
memory
➢High memory bandwidth required
 To avoid sending lots of memory requests, processors use caches to:
aims
➢Filter out many memory requests
 To reduce overhead on the shared mem/bus
➢Reduce average memory latency  To increase speed
➢Reduce memory bandwidth requirements
 Typically, more than one level of caches is used
➢L1 caches: small and fast
➢L2 caches: bigger, slower
➢L3 caches: largest, slower
➢L3 cache is shared because it is the last-level cache and serves all CPU cores,
allowing efficient data sharing, reduced duplication, and better use of chip space.
 Shared Memory Multiprocessors: Memory Hierarchy
 Cache coherence---it is the uniformity of shared resource data in multiple
local caches
 Problem: Using caches means multiple copies of the same memory location
may exist
➢leads to cache coherence/ memory coherence issues/problems
➢ Updates to the same location may lead to bugs
 Example:
Processor 1 reads A
Processor 2 reads A
Processor 1 writes to A
Now, processor 2’s cache contains stale data, here is the problem
 Cache coherence need to be implemented in hardware using a cache
coherence protocol
 Shared Memory Multiprocessors: Memory Hierarchy
A memory system is coherent if:
 1. A read by processor P to address X that follows a write by P to address X,
should return the value of the write by P (assuming no other processor wrote
to X in between).

 2. A read by processor P1 to address X that follows a write by processor P2

to X returns the written value by P2... if the read and write are “sufficiently
separated” in time (assuming no other write to X occurs in between).

 3. Writes to the same address are serialized: two writes to address X by any
two processors are observed in the same order by all processors.
 Should be in some order even if they operate at the same time

 (Example: if values 1 and then 2 are written to address X, no processor

observes X having value 2 before value 1).
 Shared Memory Multiprocessors: Memory Hierarchy
 Conditions for cache coherence like above cases
 Condition 1: obeys program order (as expected of a uniprocessor system)

 Condition 2: “write propagation”: Notification of a write must eventually get to the

other processors. Note that precisely when information about the write is propagated
is not specified in the definition of coherence.
 Coherent view of memory/cache

 Condition 3: “write serialization”

 Write Serialization.
 Even if writes happen in parallel, they are made to appear as if they
happened one after the other (in-some-order).
 It’s called global ordering of writes to the same memory location
 No two writes occur “at the same time” from the system’s point of view.
 Shared Memory Multiprocessors: Memory Hierarchy
 Cache coherence problems
 The same value A has different values in different private caches which is inconsistency.
 This particular inconsistency is called cache coherence problem
 Modern processors replicate contents of memory in local caches
 Problem: processors can observe different values for the same memory location

 Assume the computation order is done 1st P1, then p2, p3, p4? Is the above cc-problem?
 Why do we introduce this cache coherence problem into our shared architectures?
 Shared Memory Multiprocessors: Memory Hierarchy
 Cache coherence problems
 Shared Memory Multiprocessors: Memory Hierarchy
 Cache coherence protocol classification
 Cache coherence(same memory location) –the behavior of reads and writes
to the same memory location. If multiple processors access the same variable
(same memory address), do they see the same value?
 Memory consistency models (different memory locations)--the behavior of
reads and writes with respect to accesses to other memory locations.
 Hardware based solutions to cache coherence problems exist as below.
 Two main types of cache coherence protocols:
➢Snooping-based protocol/ bus-based protocol
❑Each cache monitors (snoops on) the shared communication medium (bus) to track
memory operations from other processors. Snooping = listening/watching
❑When one processor reads/writes data, it sends a message on the bus
❑ Each processor’s cache continuously listens to the bus to detect (Reads, Writes, Updates
from other processors). Based on what they hear, they (Update their data or Invalidate their
copies). Broadcast Communication:- Every operation is announced to all caches.
 Shared Memory Multiprocessors: Memory Hierarchy
 Snooping-based protocol/ bus-based protocol
 In snooping-based cache coherence protocols, all caches monitor a shared
communication bus to observe memory operations performed by other
processors.
 When a processor updates a memory location, it broadcasts the operation,
and other caches snoop the bus and forcing other caches to invalidate or
update their local copies, ensuring consistency across all processors using
policies like MESI.
 This ensures that all processors maintain a consistent view of shared data.
 How this protocol maintain coherence?
 Common snooping protocol approaches
 Write-update-write through
 Write update-write back
 Write invalidate-write through
 Write invalidate-write back
 Shared Memory Multiprocessors: Memory Hierarchy
 Write policy → how updates are propagated to other caches
 Write-update
 Write-invalidate
 Memory write policy → how data is written to main memory
 Write-through
 Write-back

 Write-update + Write-through
 How it works
 When a processor writes:
 It updates its cache
 It updates all other caches (write-update)
 It also writes to main memory immediately (write-through)
 Shared Memory Multiprocessors: Memory Hierarchy
 Write-update + Write-back
 How it works
 When a processor writes:
 Updates its cache
 Sends updated value to other caches
 Does NOT update memory immediately
 Memory updated only when cache block is replaced

 Write-invalidate + Write-through Write-invalidate + Write-back

 How it works How it works
When a processor writes:
 When a processor writes:
 Updates its cache
 Updates its cache  Invalidates other caches
 Invalidates copies in other caches  Does NOT update memory immediately
 Memory updated only when needed (replacement)
 Writes to memory immediately
 Shared Memory Multiprocessors: Memory Hierarchy
 Directory Based Protocols
❑Sharing status of any block in memory is kept in one location
❑Implementing cache coherence
 The snooping cache coherence protocols from the last lecture relied on
broadcasting coherence information to all processors over the chip
interconnect. How?
 Every time a cache miss occurred, the triggering cache communicated with
all other caches!
 What limits the scalability of snooping-based approaches to cache coherence
 How a directory-based scheme avoids these problems
 How the storage overhead of the directory structure be reduced (and at what
cost)
 How the interconnection network (bus, point-topoint, ring) affect scalability
and design choices
 Shared Memory Multiprocessors: Memory Hierarchy
 Directory Based Protocols
 Scalable cache coherence using directories
 Snooping schemes broadcast coherence messages to determine the state of a
line in the other caches

 Alternative idea: avoid broadcast by storing information about the status of

the line in one place: a “directory”
 - The directory entry for a cache line contains information about the state of the
cache line in all caches.
 - Caches look up information from the directory as necessary
 - Cache coherence is maintained by point-to-point messages between the caches
on a “need to know” basis (not by broadcast mechanisms)
 Shared Memory Multiprocessors: Memory Hierarchy
 Directory Based Protocols
In a directory-based coherence system, we typically have three main storage components:
 Private Cache (per processor)--Each processor has its own local cache (L1/L2)
 Main Memory (RAM)---------This is the global memory, The actual data (all memory blocks)
 Directory (the key component)-------This is what makes the system “directory-based”
 For each memory block:
 State (Shared, Modified, etc.)
 Sharer list → which processors have a copy
 Sometimes: Owner (who modified it)
 Why use directory-based protocol?
 Scalability--Works for hundreds or thousands of processors &No global broadcast needed
 Efficient communication--Only sends messages to processors that actually have the data
 Avoids bus bottleneck---No shared bus required & Works in distributed systems
 Disadvantages
 More complex, Directory storage overhead, Slightly higher latency per request
 Directory Based Protocols

 Now suppose p1 wants to access A which is stored in the main memory of p3

 So p1 knows the locations of A from the central directory of p1 itself via p2p n/w.
 Then p1 requests p3 for data of A
 Now p3 responding to p1 with the data A and put to its cache as A and store to its directory
also as A:S_p1,p3.
 Now if p3 wants to update A; 1st it sends p2p message to p1 as invalidate your old copy since
am going to update.
 Now p1 makes A:I on its directory and then send acknowledgment message to p3
 Now shared list on p3 directory is updated as A:S_p3 means remove p1 now
 Now A:M_p3 becomes modified by p3 and ready for other p2p commn who is in need.
 Directory Based Protocols

 A directory-based protocol maintains cache coherence by keeping a

record of which processors hold copies of each memory block and
enforcing access rules.
 One writer only----Only one processor can modify a block at a time
 Multiple readers allowed-------Many processors can read if no one is writing
 When a processor requests to write, the directory sends invalidation
messages to all other processors holding that block, ensuring only one
valid copy exists.

 For read operations, it allows multiple processors to share the data.

 This centralized tracking guarantees that all processors see consistent
and up-to-date values.
 MSI in Shared Memory
• MSI protocol is a cache coherence protocol used in parallel computer systems to
keep data consistent across multiple processor caches.
• MSI (Modified–Shared–Invalid) protocol is a set of rules that ensures all processors
see the correct and up-to-date value of shared data by assigning each cache line one
of three states.
• MSI is a cache coherence protocol (state machine).
• It defines the state of a cache line in each processor’s cache:
• MSI States
• M (Modified)
• Data is updated (dirty)
• The data has been updated (written) by a processor
• It is different from main memory
• Only this cache has the correct copy
• S (Shared)----The data is clean (same as memory); It can exist in multiple caches
• Multiple caches may have copies
• I (Invalid)----The cache line is not valid; It must be reloaded before use
• Data is not valid in the cache
 Shared Memory Architecture
 Extensions for MSI Protocol
 MESI
➢Same as MSI but adds an E “Clean-Exclusive” state
➢E state is for read-only blocks that aren’t modified compared to memory
➢Read request by another CPU to an E-block: State changes to S
➢Write request by same CPU to an E-block: State silently upgraded to M
➢Advantage: Saving coherence bandwidth
 ❑ Silent upgrade to M with no coherence requests
 ❑ Evicting a block in E does not require writing data to memory

 MOESI or MOEFSI
➢Same as MESI, but adds an O “Own” state
➢O state is for blocks that are different from memory and owned by cache. When another CPU requests
a block in M, the cache sends it to the other CPU and changes state to O
➢Cache with O block is responsible for sending data to other read requesters, and updating memory
when the block is evicted
➢Advantages:
 ❑ Less memory traffic: Memory only updated on an eviction of the O-block, not on a read request for an M-block
 ❑ Less coherence traffic: Only the cache with the O-block is responsible for sending shared copy on a read request
 Shared Memory: Pro and Con
 Advantages
• Global address space provides a user-friendly programming perspective to
memory
• Data sharing between tasks is both fast and uniform due to the proximity of
memory to CPUs

 Disadvantages:
• Primary disadvantage is the lack of scalability between memory and CPUs.
Adding more CPUs can geometrically increases traffic on the shared memory-
CPU path, and for cache coherent systems, geometrically increase traffic
associated with cache/memory management.
• Programmer responsibility for synchronization constructs that insure "correct"
access of global memory.
• Expense: it becomes increasingly difficult and expensive to design and
produce shared memory machines with ever increasing numbers of processors.
 Distributed Memory
 Like shared memory systems, distributed memory systems vary widely but share a
common characteristic.
 Distributed memory systems require a communication network to connect inter-
processor memory.
 Distributed-memory architecture comprises multiple independent processing units,
each with its own memory space.
 Communication between processors is achieved through message passing over a
network.
 This architecture offers scalability and fault tolerance but requires explicit data
distribution and communication protocols.
 Processors have their own local memory. Memory addresses in one processor do not
map to another processor, so there is no concept of global address space across all
processors.
 Because each processor has its own local memory, it operates independently.
 Changes it makes to its local memory have no effect on the memory of other
processors. Hence, the concept of cache coherency does not apply.
 Distributed Memory
 When a processor needs access to data in another processor, it is usually the
task of the programmer to explicitly define how and when data is
communicated.
 Synchronisation between tasks is likewise the programmer's responsibility.
 The network "fabric" used for data transfer varies widely, though it can can
be as simple as Ethernet.
 Distributed memory model is a memory architecture model used in parallel or
distributed systems.
 Each processor has its own private memory
 Processors communicate using message passing
 Example Technologies:
 MPI (Message Passing Interface)
 Supercomputers using cluster nodes
 Clusters
 Grid Computing

 Modern systems can simulate distributed memory inside one physical machine.
 Distributed Memory: Pro and Con
 Advantages
• Memory is scalable with number of processors. Increase the number of
processors and the size of memory increases proportionately.
• Each processor can rapidly access its own memory without interference and
without the overhead incurred with trying to maintain cache coherency.
• Cost effectiveness: can use commodity, off-the-shelf processors and networking.

 Disadvantages
• The programmer is responsible for many of the details associated with data
communication between processors.
• It may be difficult to map existing data structures, based on global memory, to
this memory organization.
• Non-uniform memory access (NUMA) times
 Hybrid Distributed-Shared Memory
 The largest and fastest computers in the world today employ both
shared and distributed memory architectures.

 The shared memory component is usually a cache coherent SMP machine.

Processors on a given SMP can address that machine's memory as global.
 Hybrid architectures combine elements of both shared-memory and
distributed-memory systems.
 These architectures leverage the benefits of shared-memory parallelism
within individual nodes and distributed-memory scalability across multiple
nodes, making them suitable for a wide range of applications.
 Hybrid Distributed-Shared Memory
 The distributed memory component is the networking of multiple
SMPs. SMPs know only about their own memory - not the memory
on another SMP.

 Therefore, network communications are required to move data from

one SMP to another.

 Current trends seem to indicate that this type of memory architecture

will continue to prevail and increase at the high end of computing for
the foreseeable future.

 Advantages and Disadvantages: whatever is common to both shared

and distributed memory architectures.
 Interconnection networks and routing protocols
 Interconnection networks and routing protocols are the backbone of parallel and
distributed systems, determining how efficiently processors, memory, and
accelerators communicate.
 Interconnection networks connect processors and memory in a parallel computer,
facilitating communication and data transfer.
 Static (Direct) Networks: Use point-to-point communication links, where each node is
directly connected to others.
 Dynamic (Indirect) Networks: Employ switches to connect nodes dynamically, allowing for
more flexible communication paths.
Interconnection Network Topologies
 Buses (signle bus or Multi bus)-- A simple topology where all processors share a common
bus for data exchange.
 Crossbar: Provides a direct connection between any pair of nodes, but can be expensive and
power-intensive.
 Multistage: Uses multiple stages of switches to connect nodes, offering scalability and
flexibility.
 Routing Protocols
 A routing protocol defines how messages (data) travel from one processor to
another through that network.
 In parallel systems processors frequently exchange data and many messages travel at the
same time
 Therefore, without proper routing we may face Congestion, Delay, Deadlocks, Poor
performance
 Main Functions of Routing Protocols
 1. Path Selection---Choose a route from source to destination
 2. Traffic Management----Avoid congested paths
 3. Deadlock Avoidance----Prevent circular waiting of messages
 4. Fault Tolerance----Reroute if a link/node fails
 Routing protocols in parallel systems define how messages are transmitted between processors
through an interconnection network.
 They determine the path taken by data, manage congestion, and ensure efficient communication.
 Effective routing protocols are essential for achieving high performance and scalability in parallel
architectures.
Thank you…!!!