PARALLEL COMPUTING –BCS702

Module 1

Introduction to parallel
programming, Parallel hardware and
parallel software
 Topics to be covered
• Classifications of parallel computers,
• SIMD systems,
• MIMD systems,
• Interconnection networks,
• Cache coherence,
• Shared-memory vs. distributed-memory,
• Coordinating the processes/threads,
• Shared-memory,
• Distributed-memory.
[Link] of parallel computers

There are 2 main Classification

Primary classification based on memory architecture.

Classification focuses on how processors access and share
memory in a parallel system. Here are the main classifications:
[Link] Memory Systems
In these systems, all processors share a common memory space. Any processor can
access any memory location, which simplifies programming but may lead to
memory contention.

Types:
• Uniform Memory Access (UMA):
All processors access memory with the same latency and bandwidth.
• Non-Uniform Memory Access (NUMA):
Memory access time varies depending on the memory location relative to the
processor (e.g., local vs. remote memory).

• Characteristics:
[Link] to program (due to shared address space)
[Link] for tasks with frequent data sharing
Examples: multi core desktops, symmetric multiprocessing (SMP) systems
2 . Distributed Memory Systems
Each processor has its own private memory. Processors communicate by passing
messages using a network.
Characteristics:
[Link] explicit communication (e.g., via MPI)
[Link] to very large numbers of processors
[Link] complex programming model
Examples: clusters, massively parallel processors (MPPs)

3. Hybrid Systems
These systems combine features of both shared and distributed memory systems. A
common example is a cluster of multicore nodes.
Characteristics:
[Link] memory within a node
[Link] memory across nodes
[Link] may use both threads (e.g., OpenMP) and message passing (e.g.,
MPI)
 Flynn’s Taxonomy (by Michael J. Flynn)

Flynn’s Taxonomy classifies parallel computers based on the number of

instruction streams and data streams being processed. This is orthogonal
memory-based classification.
1. SISD (Single Instruction, Single Data)

• Description: Traditional sequential computers.

• Operation: One instruction operates on one data item at a time.
• Example: Standard uniprocessor systems (old PCs, embedded systems).

2. SIMD (Single Instruction, Multiple Data)

• Description: One instruction stream operates on multiple data items
simultaneously.
• Operation: Good for data-parallel tasks like vector processing.
• Example:
– GPU cores
– Vector processors (e.g., Cray X-MP)
– Intel AVX (Advanced Vector Extensions)
[Link] (Multiple Instruction, Single Data)
• Description: Rare or mostly theoretical.
• Operation: Multiple instructions operate on the same data.
• Example: Some fault-tolerant systems (e.g., aircraft control systems with redundancy)

4. MIMD (Multiple Instruction, Multiple Data)

• Description: Most modern parallel systems.
• Operation: Each processor executes its own instructions on its own data.
• Example:
– Multicore CPUs
– Clusters
– Supercomputers
[Link] example :-vector processors
A classic example of SIMD (Single Instruction, Multiple Data) architecture.

They are designed to operate on entire vectors (arrays) of data with a single
instruction, making them highly effective for data-parallel tasks, especially in
scientific and engineering applications.

The key characteristics of vector processors

1. SIMD Architecture
• Executes one instruction on multiple data elements simultaneously. Ideal for
operations like adding two vectors, multiplying arrays, etc.

2. Vector Registers
Vector processors use special vector registers, each capable of storing an entire vector
(e.g., 64 or 128 elements).These registers allow fast access to vector elements
compared to memory.
3. Pipelined Functional Units
• Vector processors often include deep pipelines that allow high throughput.
• Different pipeline stages can process different elements of the vector at the
same time (like an assembly line).
• Example: While one element is being added, the next is being fetched, and the
previous is being stored.

4. High Throughput on Large Data Sets

• The larger the vector, the better the performance.
• Overhead is amortized over many data elements, making it efficient for large-
scale linear algebra and array operations.

5. Efficient for Data-Parallel Problems

• Well-suited for problems where the same operation must be applied to
large sets of data, like:
– Matrix computations
– Signal/image processing
– Scientific simulations
6. Stride(OFFSET) and Indexed Memory Access

Can access data with a fixed stride (e.g., every 2nd or 4th
element).Some vector processors support indexed addressing,
allowing more flexible memory patterns.

7. Explicit Vector Programming

Programmers (or compilers) must write code that explicitly uses

vector operations.
Example languages/extensions: Fortran with vector extensions,
assembly, or intrinsic in C/C++.
8. Reduced Instruction Count
Because one vector instruction replaces many scalar
instructions, the instruction count is reduced, improving
instruction fetch/decode efficiency.

9. Not Ideal for Irregular Control Flow

Vector processors perform poorly with:
Branching inside loops
Non-uniform operations
Works best when data access and control flow are
predictable.
Example for SIMD:- GPUs (Graphics Processing Units) are a modern and powerful
example of SIMD-style architectures, but with some unique characteristics that make
them distinct from traditional vector processors.

• GPU (Graphics Processing Unit) is a highly parallel processor originally designed

for graphics rendering but now widely used for general-purpose parallel
computing.

• GPUs excel at data-parallel tasks, where the same operation is performed on many
data elements simultaneously. They follow a SIMD/SIMT execution model, running
thousands of lightweight threads in parallel.

• GPUs serve as coprocessors to CPUs, offloading compute-intensive, data-parallel

workloads. Programming a GPU involves writing kernel functions (e.g., in CUDA)
that are launched from the CPU and executed concurrently by many GPU threads.
Key points:

Massively parallel hardware

Efficient for uniform, data-parallel workloads

Uses SIMT (Single Instruction, Multiple Threads) model

Requires explicit parallel programming

Organized into threads, blocks, and grids

Ideal for tasks like vector operations, matrix math, and image processing
[Link] (Multiple Instruction, Multiple Data) as the most flexible and
widely used parallel computing architecture.

• MIMD stands for Multiple Instruction, Multiple Data.

This means:
• Each processor executes its own instruction stream
• Each processor operates on its own data
• So, different processors can be doing completely different tasks at the
same time, or the same task on different parts of the data.
1. General and Flexible Architecture
• MIMD systems can support task parallelism and data parallelism.
• Suitable for a wide range of applications, including irregular and complex
computations.

2. Multiple Independent Control Units

• Each processor has its own program counter and control logic.
• This allows independent execution, unlike SIMD where all processors
follow the same instruction.

3. Can Be Shared or Distributed Memory

• MIMD systems can be implemented with:
• Shared memory: All processors access the same memory space (e.g.,
multicore systems, SMPs)
• Distributed memory: Each processor has its own local memory and uses
message passing (e.g., clusters)
4. Most Common Parallel Architecture
• Most modern parallel systems (like multicore CPUs, clusters,
supercomputers) are MIMD-based.
• Example systems: Intel multicore processors, distributed HPC clusters, Cray
and IBM supercomputers.

5. Supports Complex Programs

• Because each processor can follow a different control flow, MIMD can
handle heterogeneous tasks — unlike SIMD, which is best for uniform
tasks.
Shared memory system as a parallel computer where multiple
processors access the same physical memory space.

• It’s one of the main architectures to classify parallel systems,

particularly in contrast to distributed memory systems.

A shared memory system is a parallel architecture in which:

• All processors have direct access to a common global memory.
• Processors can read and write to the same memory locations.
• Communication between processors happens implicitly via shared
variables, not through explicit message passing.
1. Global Address Space
• All processors see the same memory — there is a single, unified address space.

2. Implicit Communication
• Data is shared simply by reading and writing shared variables in memory.
• No need for explicit send/receive operations (as in MPI).

3. Synchronization Is Required
• Since multiple threads/processors can access the same memory simultaneously,
synchronization mechanisms (like mutexes, semaphores, or barriers) are needed to avoid
race conditions.

4. Ease of Programming
• Shared memory systems are generally easier to program than distributed systems.
• Languages like OpenMP and Pthreads are commonly used for shared memory
parallelism.

5. Scalability Limitations
• As the number of processors increases, memory contention and bandwidth become
issues.
• Typically scales well to tens of processors, but poorly to hundreds or thousands.
6. Memory Access Models
Uniform Memory Access (UMA):
All processors access memory at the same speed.
Non-Uniform Memory Access (NUMA):
Memory is closer (faster) to some processors than others. Performance depends on
memory locality.
Distributed memory system
a parallel architecture in which each processor has its own
private memory, and processors communicate explicitly by
passing messages.

• This is one of the core architectural models he uses to explain

how parallel programs are written and executed in systems
like clusters and supercomputers.
A distributed memory system is a parallel computing system in
which:

• Each processor (or node) has its own local memory.

• Processors cannot access each other's memory directly.

• Communication occurs through explicit message passing,

typically using libraries like MPI (Message Passing Interface).
1. Private Local Memory
• Each processor works with its own memory space.
• Memory is not shared among processors.
• Helps avoid memory contention but increases programming complexity.

2. Explicit Communication
• To share data, processors must send and receive messages.
• Example: using MPI_Send and MPI_Recv to exchange data between processes.

3. Highly Scalable
• Since memory is distributed, the system can scale to thousands or even millions of processors.
• Common in large HPC clusters and supercomputers.

4. Complex Programming Model

• Developers must explicitly manage data distribution and communication.
• Correctness and performance depend on effective communication and data locality.

5. No Global Address Space

• Unlike shared memory systems, there is no common memory view.
• Each process has a local view of its own memory only.

6. Performance Depends on Network

• The latency and bandwidth of the interconnection network affect performance.
• Communication is more expensive than local computation.
4 .Interconnection networks
which define how processors (or nodes) are connected to each other to enable communication.

• The interconnect plays a decisive role in the performance of both distributed- and shared-
memory systems
• a slow interconnect will seriously degrade the overall performance of all but the simplest
parallel program.

Shared-memory interconnects:- Use a bus to connect processors and memory

A bus was a collection of parallel communication wires together with some hardware that
controls access to the bus.

The key characteristic:-

- The communication wires are shared by the devices
- The virtue of low cost and flexibility
- Multiple devices can be connected to a bus with little additional cost
- There will be contention for use of the bus increases, and the expected performance of the bus
decreases

The size of shared-memory systems has increased, buses are being replaced by switched
interconnects.
switched interconnects use switches to control the routing of data among the connected devices.

A crossbar is a relatively simple and powerful switched interconnect.

The diagram in Fig. 2.7(a) shows a simple crossbar

The individual switches can assume one of the two configurations shown in Fig. 2.7(b).

With these switches and at least as many memory modules as processors, there will only be a
conflict between two cores attempting to access memory if the two cores attempt to
simultaneously access the same memory module.

For exam ple, Fig. 2.7(c) shows the configuration of the switches if P1 writes to M4, P2 reads from
M3, P3 reads from M1, and P4 writes to M2.

Crossbars allow simultaneous communication among different devices, so they are much faster
than buses.

However, the cost of the switches and links is relatively high.

A small bus-based system will be much less expensive than a crossbar-based system of the same
size.
Distributed-memory interconnects

Divided into two groups: direct inter connects and indirect interconnects

In a direct interconnect each switch is directly connected to a processor-

memory pair, and the switches are connected to each other.
Fig. 2.8 shows a ring and a two-dimensional toroidal mesh
Two bisections of a ring: (a) only two communications can take place between the
halves and
(b) four simultaneous connections can take place.
 A bisection of a toroidal mesh.

If we have a square two-dimensional toroidal mesh with p = q2

nodes (where q is even), then we can split the nodes into two halves
by removing the “middle” horizontal links and the “wraparound”
horizontal links.
This suggests that the bisection width is at most 2q = 2√p.

this is the smallest possible number of links, and the bisection width
of a square two-dimensional toroidal mesh is 2√p.
 Bandwidth and Bisection bandwidth
• The bandwidth of a link is the rate at which it can
transmit data. It is given in megabits or megabytes
per second.
• Bisection bandwidth is used as a measure of
network quality. It’s similar to bisection width.
• For eg. if the links in a ring have a bandwidth of
one billion bits per second, then the bisection
bandwidth of the ring will be two billion bits per
second or 2000 megabits per second.
 Fully connected network
• Each switch is directly connected to every other
switch. Its bisection width is p2/4.
The hypercube is a highly connected direct
interconnect that has been used in actual systems.
A one-dimensional hypercube is a fully connected
system with two processors. A two-dimensional
hypercube is built from two one-dimensional
hypercubes by joining “corresponding” switches.
Similarly, a three-dimensional hypercube is built
from two two-dimensional hypercubes.
• a hypercube of dimension d has p = 2d nodes,
and a switch in a d-dimensional hypercube is
directly connected to a processor and d switches.
• The bisection width of a hypercube is p/2, so it
has more connectivity than a ring or toroidal
mesh, but the switches must be more powerful,
since they must support 1 + d = 1 + log2(p) wires,
while the mesh switches only require five wires.
• So a
• hypercube with p nodes is more expensive to
construct than a toroidal mesh
 A generic indirect network.

In an indirect interconnect, the switches may not be directly

connected to a processor. They’re often shown with
unidirectional links and a collection of processors, each of which
has an outgoing and an incoming link, and a switching network.
 A crossbar interconnect for distributed-
memory

The crossbar and the omega network are

relatively simple examples of indirect
networks.
 An omega network

• The switches are two-by-two crossbars. Observe that unlike the crossbar, there are
communications that cannot occur simultaneously.
• For example, if processor 0 sends a message to processor 6, then processor 1 cannot
simultaneously send a message to processor 7. On the other hand, the omega network is less
expensive than the crossbar. The omega network uses 1 2p log2(p) of the 2 × 2 crossbar
switches, so it uses a total of 2p log2(p) switches, while the crossbar uses p2.
 Cache coherence

• is a concept in computer architecture that

ensures all processors in a multiprocessor or
multicore system see a consistent view of
memory.
 A shared-memory system with two cores and
two caches

Suppose we have a shared-memory system with two cores, each of which has its own
private data cache. As long as the two cores only read shared data, there is no problem.
• This unpredictable behavior will occur regardless of
whether the system is using a write-through or a write-
back policy. If it’s using a write-through policy
• The main memory will be updated by the assignment x =
7.
• However, this will have no effect on the value in the cache
of core 1. If the system is using a write-back policy, the
new value of x in the cache of core 0 probably won’t even
be available to core 1 when it updates z1
• The programmer doesn’t have direct control over
when the caches are updated, so her program
cannot execute these apparently innocuous
statements and know what will be stored in z1.
• There are several problems here,
– the caches we described for single processor systems
provide no mechanism for ensuring that when the
caches of multiple processors store the same variable
– an update by one processor to the cached variable is
“seen” by the other processors. That is, that the cached
value stored by the other processors is also updated.
This is called the cache coherence problem.
 2 main approaches to ensuring cache
coherence:
• Snooping cache coherence
• Directory-based cache coherence
 Snooping cache coherence
• When the cores share a bus, any signal transmitted
on the bus can be “seen” by all the cores connected
to the bus.
• Thus when core 0 updates the copy of x stored in its
cache, if it also broadcasts this information across
the bus, and if core 1 is “snooping” the bus, it will
see that x has been updated, and it can mark its
copy of x as invalid.
• The broadcast only informs the other cores that the
cache line containing x has been updated, not that x
has been updated.
 Points to remember
Snooping cache coherence

• It is not essential that the interconnect be a bus, only that

it support broadcasts from each processor to all the other
processors.
• Snooping works with both write-through and write-back
caches.
• In principle, if the interconnect is shared—as with a bus
—With write-through caches, there’s no need for
additional traffic on the interconnect, since each core can
simply “watch” for writes.
- With write-back caches, on the other hand, an extra
communication is necessary, since updates to the cache
don’t get immediately sent to memory.
 Contd…
• Broadcasts are expensive, and snooping cache
coherence requires a broadcast every time a
variable is updated. Broadcast across the
interconnect will be very slow relative to the
speed of accessing local memory.

• So snooping cache coherence isn’t scalable,

because for larger systems it will cause
performance to degrade.
 Directory-based cache coherence
• Protocols uses a data structure called a directory.
• The directory stores the status of each cache line. Typically, this
data structure is distributed
• For example, each core/memory pair might be responsible for
storing the part of the structure that specifies the status of the
cache lines in its local memory.
• Thus when a line is read into, say, core 0’s cache, the directory entry
corresponding to that line would be updated, indicating that core 0
has a copy of the line. When a variable is updated, the directory is
consulted, and the cache controllers of the cores that have that
variable’s cache line in their caches will invalidate those lines.
• Clearly, there will be substantial additional storage required for the
directory, but when a cache variable is updated, only the cores
storing that variable need to be contacted.
 Comparison
Feature Snooping Directory-Based

All caches monitor (or “snoop”) a shared bus for memory transactions A centralized or distributed directory tracks which caches have a copy
Basic Idea
to keep copies coherent. of each memory block.

Point-to-point communication using directory lookup before sending

Main Mechanism Broadcasting all memory operations over a bus.
coherence messages.

Each cache listens for writes from other processors and Processor queries directory to check sharers/owners, then sends
Coherence Maintenance
invalidates/updates its copy if necessary. targeted invalidation or update messages.

No explicit list — coherence ensured by everyone listening to the same Directory maintains a bit vector or list indicating which caches hold
Data Tracking
bus. the block.

Small systems (few processors) — works well when broadcast overhead

Best For A large-scale multiprocessor avoids full broadcast traffic.
is low.

Poor scalability — every transaction is broadcast to all caches, bus

Scalability Limit Scales better — messages sent only to relevant caches.
becomes a bottleneck.

Latency Low latency for small systems (no lookup delay). Slightly higher latency due to directory lookup.

Traffic High traffic on the bus, especially as processor count increases. Lower overall traffic, but more complex message routing.

Implementation Simpler to implement — relies on shared bus. More complex — requires directory storage and lookup logic.

Higher — directory needs bits for each cache line × number of

Storage Overhead Minimal — no per-block sharer list.
processors.
False sharing
• False sharing is a performance-degrading phenomenon in
parallel computing, particularly in shared-memory systems.

False sharing occurs when:

• Multiple threads or processes on different cores modify
variables that reside on the same cache line, even though
the variables are logically independent.
Explanation:

• Modern CPUs use cache lines (typically 64 bytes) to load

memory into the cache.

• If two variables used by different threads happen to sit on the

same cache line, any write to one of those variables by one
thread will invalidate the cache line in another thread's core,
even if that thread is working on a different variable in the
same cache line.

• This results in excessive cache coherence traffic, slowing

down the program — even though there is no actual data
sharing or synchronization between the threads. Hence, it's
called false sharing.
Imagine an array int A[2]; accessed by two threads:

• // Thread 0
• for (int i = 0; i < N; i++)
• A[0] += 1;

• // Thread 1
• for (int i = 0; i < N; i++)
• A[1] += 1;

Even though A[0] and A[1] are accessed independently, they may lie on the
same cache line. This causes performance issues due to false sharing.
Avoiding False Sharing:

• Padding: Add extra space between variables so that they fall

on different cache lines.

• Structure alignment: Use compiler directives or attributes to

align variables properly.

• Data layout design: Place frequently updated variables far

apart in memory.
2.4 Parallel software
• Software that effectively leverages parallelism, particularly for shared-memory
and distributed-memory architectures.

1. Parallel Hardware is Everywhere

• Multi-core processors are now standard in all devices: desktops, servers, phones,
and tablets.
• This makes parallelism essential, not optional, for achieving high performance.

2. Software Still Lags Behind

• As of 2021:
– System-level software and many major applications (e.g., Excel, Photoshop,
Chrome) use some level of parallelism.
– Many applications still only use a single core, and many developers lack
experience with parallel programming.
• This mismatch between hardware capabilities and software utilization is a
key bottleneck.
3. The Implication: Developers Must Adapt
• We can no longer expect faster hardware alone to improve performance.
• To keep pushing software performance forward:
Developers must learn to write programs that exploit shared-memory and
distributed-memory systems, as well as MIMD (Multiple Instruction, Multiple
Data) and SIMD (Single Instruction, Multiple Data) models.

Coordinating the processes/threads

problems that are easy to parallelize because the work can be divided evenly
and done independently by each thread or process.

a practical explanation and example code in both OpenMP (shared memory)

and MPI (distributed memory) to show how this trivial parallelization
works.
Ex:
double x[n], y[n];
for (int i = 0; i < n; i++)
x[i] += y[i];

To parallelize:
• Suppose you have p threads or processes.
• Divide the array into p equal-sized chunks.
• Each thread/process handles its assigned chunk:
– process/thread 0 responsible for elements0, . . . , n/p − 1,
process/thread 1 would be responsible for elements n/p, .
. . , 2n/p − 1, and so on.
– This avoids any data dependency, synchronization, or
communication (in shared memory).
#include <omp.h>
#include <stdio.h>

#define N 1000000
double x[N], y[N];

int main() {
// Initialize arrays
for (int i = 0; i < N; i++)
{
x[i] = i;
y[i] = 2 * i;
}

// Parallel addition
#pragma omp parallel for
for (int i = 0; i < N; i++)
{
x[i] += y[i];
}

return 0;
}

• #pragma omp parallel for automatically divides the loop across available threads.
• No synchronization or communication needed — each thread operates on its own
part of the array.
1. What Makes Parallelization Easy
• In simple cases (like element-wise array addition):
• The programmer needs to:
– Divide the work among threads or processes so that:
(a) Each gets about the same amount of work → this is called
load balancing.
(b) There's minimal communication between threads or
processes.
• Load balancing: Making sure no thread/process is
idle while others are still working.
• These concerns are minor or trivial when:
The total amount of work is known ahead of
time.
The tasks are uniform and independent.
 2. What Makes Parallelization Hard
• The vast majority of problems are much more
determined to resist our efforts to find a
parallel solution.

For many problems, the work:

• Is not predictable in advance.
• Is generated dynamically as the program runs.
• Depends on data, requiring interaction
between threads/processes.
In these cases, programmers must:
• Synchronize processes/threads:
Ensure they perform operations in the correct
order.
Prevent race conditions, where two threads
modify the same data at the same time.
• Communicate among processes/threads:
Share data or intermediate results.
Coordinate task progress.
• Interrelation of Synchronization and
Communication
In distributed-memory systems (e.g., MPI):
– Communication often implies synchronization.
– E.g., one process can't continue until it receives
data from another.
• In shared-memory systems (e.g., OpenMP or
Pthreads):
– Synchronization primitives (like mutexes, barriers)
often handle communication as well.
– E.g., using a mutex to safely read/write shared
variables.
Shared Memory:This part introduces how memory is handled in shared-memory
systems, and how threads communicate.

• Shared-Memory Programming: Core Concepts

1. Shared vs. Private Variables
• In a shared-memory system (e.g., using OpenMP,
Pthreads, or multithreading in general):
• Shared Variables:
– Accessible by all threads.
– Any thread can read from or write to them.
– Used for communication and coordination.
• Private Variables:
– Each thread has its own independent copy.
– Used for temporary/local computations that don't affect others.
– Helps avoid race conditions and unintended interactions.
2. Communication Is Implicit

• In shared-memory programming,
communication between threads happens
through shared variables.
• This is called implicit communication — you
don’t need special functions to send/receive
data.
• Example:
– Thread A writes to shared_var
– Thread B later reads from shared_var
– This is implicit communication — nothing like
send() or receive() is used (unlike in MPI)
Advantages of Shared-Memory
• Easier to program simple parallel tasks, especially when all
threads run in the same process space.
• No need to write communication code (e.g., no message
passing).

Challenges
• Because multiple threads can access the same variables:
– Race conditions can occur (when two threads access a variable
concurrently and at least one writes).
– Requires synchronization mechanisms (e.g., mutexes, barriers, critical
sections).
#pragma omp parallel shared(a) private(i)
{
int i = omp_get_thread_num();
a[i] = i * i; // 'a' is shared, 'i' is private
}
• a is shared among all threads — used to store
results.
• i is private — each thread has its own copy, so
they don’t interfere with each other.
Dynamic Thread Paradigm
• Structure:
– There's a master thread that runs the program.
– When new work arrives (e.g., from the network), the
master dynamically creates ("forks") worker threads.
– Each worker:
• Performs a specific task.
• Terminates and joins the master once done.
• Benefits:
– Efficient resource usage: threads only exist and use
memory while needed.
– Good for event-driven systems (like web servers) or
asynchronous workloads.
Drawbacks:
• Thread creation and destruction (fork/join)
are not free — they introduce overhead.
• May not scale well if the workload is constant
and predictable.
Common Usage:
• Network servers, GUI event handlers,
background jobs, etc.
2. Static Thread Paradigm

• Structure:
– The master thread sets up the program and then forks all worker threads at
once.
– All threads run in parallel until the work is done.
– After completion, threads join the master, which may do cleanup and exit.
• Benefits:
– Better performance potential when:
• Work is predictable or long-running.
• Forking threads repeatedly would be expensive.
– Aligns closely with distributed-memory (MPI) models, where processes also run
from start to finish.
• Drawbacks:
– Idle threads still consume resources (e.g., stack space, thread-local data).
– Less flexible for irregular or unpredictable workloads.
• Common Usage:
– Scientific computing, simulations, parallel loops (e.g., OpenMP parallel for),
batch processing.
Non determinism
Introduction to MIMD and Concurrency
• MIMD: Multiple Instruction, Multiple Data systems
• Threads/processors execute asynchronously
• Leads to nondeterministic behavior in programs
• Same input → Different outputs possible

What is Nondeterminism?
• A computation is nondeterministic if:
– Same input
– Different outputs (execution-dependent)
• Caused by:
– Asynchronous execution
– Independent thread scheduling
my_val = Compute_val ( my_rank ) ;
x += my_val ;

As an example,
• suppose we have two threads, one with ID or
rank 0 and the other with ID or rank 1.
• Suppose also that each is storing a private
variable my_x, thread 0’s value for my_x is 7,
and thread 1’s is 19.
 Simple Example of Nondeterminism

When is Nondeterminism a Problem?

Harmless: Output order in logging or printing

Problematic: Shared-memory operations
Can lead to incorrect results or program crashes
What is a Race Condition?
• Two or more threads access shared resource concurrently
• Final outcome depends on which thread runs first
• Example: x += my_val;
• Not atomic: involves read, compute, write
• Threads may overwrite each other's updates

Race Condition in Action

(Timeline Example)
 Fixing Race Conditions with Mutexes
• Use mutual exclusion to protect critical sections:

Critical Sections
A critical section is code that must not be executed by more than one thread
at once
Keep critical sections:
Short
Efficient
Infrequent
//example to show critical section

#include <stdio.h>
#include <pthread.h>
long counter = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
void worker(void)
{ for (int i = 0; i < 100000; ++i) {
pthread_mutex_lock(&m); // enter critical section
counter++; // shared state
pthread_mutex_unlock(&m); // leave critical section
printf("counter = %ld\n\n",counter);
}
printf("counter = %ld\n\n",counter);
return NULL;
}

int main()
{
worker();
return 0;
Alternatives to Mutexes
 Example for busy waiting
#include <stdio.h>
#include <stdbool.h>
#include <pthread.h>

volatile bool flag = false; // shared flag

void* worker(void* arg) {

printf("Worker: doing some work...\n");
for (int i = 0; i < 100000000; i++); // simulate work
flag = true; // signal main thread
return NULL;
}

int main() {
pthread_t t;
pthread_create(&t, NULL, worker, NULL);
printf("Main: waiting for worker...\n");
while (!flag) {
// Busy wait
}

printf("Main: worker finished!\n");

pthread_join(t, NULL);
return 0;
Distributed-Memory Systems

• Each processor/core has its own private memory

• Communication between processes is explicit
• Typically use processes, not threads
• Message-passing is the most widely used API

Message Passing Basics

• Each process has a rank: 0 to p−1
• API includes basic functions: Send() and Receive()
• Processes communicate explicitly by sending messages
• Often follows the SPMD model (Single Program, Multiple Data)
Message Passing Example (Pseudocode)

Blocking and Non-blocking Communication

Blocking Send: waits until Receive is ready

Non-blocking Send: copies message and continues Receive usually

blocks until message is received Other variations exist (e.g., buffered,
synchronous)
Collective Communication (MPI)
• MPI (Message Passing Interface) is most widely used
• Common collective functions:
– Broadcast: one-to-all communication
– Reduce: combine data (e.g., sum)
• Powerful, but low-level — requires significant manual work

Challenges of Message Passing

• Manual data distribution and communication
• Must often rewrite the entire program
• Hard to parallelize incrementally
• Easy to introduce bugs
• Sometimes called:
• “The Assembly Language of Parallel Programming”
One-Sided Communication

• One process reads/writes remote memory directly

• Only one process actively participates (Send or
Receive not needed)
• Can reduce synchronization and overhead

Challenges of One-Sided Communication

• Process 0 writes to memory of Process 1:
– Must know when it’s safe
– May use flags or synchronization
• Risk of overwrites or undetected errors
• Polling for updates can increase overhead
PGAS Languages
• Partitioned Global Address Space
• Mix of shared-memory style and distributed-memory performance
• Variables:
– Private: stored in local memory
– Shared: distributed across processes
• Programmer controls data locality
• PGAS Vector Addition Example