DEF and USE

Statements:

1. A = 1.0
2. B = A + C - 2.0

Step 1: Identify DEF and USE for each statement

 DEF (definition) means variables assigned a new value in the statement.

 USE means variables whose values are read/used in the statement.

Statement 1: A = 1.0

 DEF: A (we assign 1.0 to A)

 USE: None (no variables are used to compute the value)

Statement 2: B = A + C - 2.0

 DEF: B (we assign a new value to B)

 USE: A, C (both are used to compute the right-hand side expression)

Step 2: Explain data dependencies

 Data dependency occurs when a statement depends on the value computed in a

previous statement.
 Statement 2 depends on statement 1 because it uses A, which is defined in statement
1.
 If the value of A changes in statement 1, it directly affects the computation of B in
statement 2.

Summary:

Statement DEF USE Explanation

A = 1.0 A - Defines A
B = A + C - 2.0 B A, C Uses A (defined above) and C (assumed defined elsewhere)
 Types Of Data Dependencies

What is data dependence?

If two statements (let’s call them S1 and S2) use or define the same variable, then they
depend on each other in some way. This is called data dependence.

There are 4 main types of data dependence:

1. True / Flow Dependence

 When it happens:
A variable is defined in S1 and used in S2.
 What it means:
S2 needs the result from S1 to do its work.
 Example:
 S1: A = B + C;
 S2: D = 2 * A;
o A is defined in S1.
o A is used in S2.
So this is a true dependence.

2. Anti Dependence

 When it happens:
A variable is used in S1 and then defined in S2.
 What it means:
The second statement overwrites a variable that was used earlier.
 Example:
 S1: A = B + C;
 S2: B = 0;
o B is used in S1.
o B is defined (assigned) in S2.
This is anti dependence because S2 changes a variable that S1 already used.

3. Output Dependence

 When it happens:
A variable is defined in both S1 and S2.
  What it means:
Two statements are writing to the same variable.
 Example:
 S1: A = B + C;
 S2: A = A - D;
o A is defined in both S1 and S2.
So this is output dependence.

4. Input Dependence

 When it happens:
A variable is used in both S1 and S2, but not modified.
 What it means:
Both statements are just reading the same variable — no conflict.
 Example:
 S1: X = A + B;
 S2: Y = B - C;
o B is used in both, but not changed.
So this is input dependence.

Summary Table

Safe for
Type DEF & USE overlap What’s happening
DEF(S1) ∩ USE(S2) ≠ ∅ S2 needs result from S1
parallel?

DEF(S2) ∩ USE(S1) ≠ ∅ S2 overwrites a value S1 used

True Dependence ❌ No
Anti Dependence Risky
DEF(S1) ∩ DEF(S2) ≠ ∅ Both write to the same variable
Output
Risky
USE(S1) ∩ USE(S2) ≠ ∅ Both just read the same variable Yes
Dependence
Input Dependence

Loop Array And Dependence

Problem:

You have loops working on arrays:

Do I = 0 to N-1
A[2*I + 1] = B[I]
D[I] = A[2*I]
End Do
Key idea:

When dealing with arrays, you can’t just treat the whole array as one variable for
dependence. Instead, you need to look at which specific elements (indexes) of the arrays are
being accessed.

Why?

Because different iterations of the loop might read or write different elements of the array.
Some elements might overlap (cause dependence), others might not.

Step 1: Look at array accesses carefully

 First statement: A[2*I + 1] = B[I]

o It writes to element A[2*I + 1]
o It reads B[I]
 Second statement: D[I] = A[2*I]
o It reads from element A[2*I]
o It writes to D[I]

Step 2: Check if dependence happens

 Does writing to A[2*I + 1] in iteration I affect reading from A[2*J] in some

iteration J?
 In other words, can 2*I + 1 ever be equal to 2*J for any integers I and J?

Step 3: Solve the equation

We want to check if:

2*I + 1 = 2*J

Is this possible for some I and J?

 Rearrange:

2*I + 1 = 2*J
=> 1 = 2*J - 2*I
=> 1 = 2*(J - I)

 The right side is always even (because it's 2 times an integer).

 Left side is 1 (odd).
  So, no integer values of I and J can make this true.

Conclusion:

 No dependence between these two statements on the array A elements.

 They access different elements of A — one accesses odd indexes (2*I + 1) and the
other accesses even indexes (2*I).
 So these two statements can run safely in parallel without worrying about data
dependence on A.

Summary:

 For arrays, dependence depends on whether array indices overlap.

 Just looking at the array name is NOT enough.
 Here, A[2*I + 1] and A[2*I] refer to different parts of A, so no dependence.

LOOP DEPENDENCE ANALYSIS

What is Loop Dependence Analysis?

It’s a way to check if different iterations of a loop depend on each other or not.

Why does it matter?

If iterations don’t depend on each other, then:

 We can run those iterations at the same time (in parallel).

 Different processors can work on different iterations simultaneously — making the
program run faster.

Example of the question:

Can processor A work on iteration i=1, while processor B works on iteration i=2 at the
same time?

How do we check?
 1. Look at each statement inside the loop.
2. Find which variables are defined (DEF) and which are used (USE).
3. Check if the same variable (or array element) is involved in different iterations.

Important:

 For arrays, check if the subscript (index) overlaps between different iterations.
 If two iterations access the same memory location and one writes, the other reads or
writes, then they depend on each other and cannot be done in parallel.

Step-by-step:

Imagine the loop has these two statements for each iteration i:

S1: A[f(i)] = ... // defines A at index f(i)

S2: ... = A[g(i)] // uses A at index g(i)

 Check if for some i and j (i ≠ j),

f(i) == g(j) → meaning iteration i writes to the same element that iteration j
reads (or vice versa).
 If yes → Dependence exists → no parallelization.
 If no → iterations are independent → can run in parallel!

Simple example:
For i = 1 to N
A[i] = B[i] + 1; // S1: defines A[i]
C[i] = A[i-1] + 2; // S2: uses A[i-1]
End For

 Does iteration i depend on iteration i-1?

 Yes, because S2 reads A[i-1] which was written in iteration i-1.
 So iteration i needs iteration i-1 to finish first → cannot run in parallel.

Summary:

 Loop dependence analysis checks if loop iterations can run independently or not.
 Use DEF and USE sets and consider array indices.
 If two iterations access the same element, with at least one write, then they are
dependent.
 If no overlapping access, iterations can run in parallel on different processors!
 Program Transformations

1. Induction Variables

These are variables inside a loop whose values increase or decrease in a fixed pattern (like
arithmetic progression).

Example:

m = 0;
for (i = 1; i <= N; i++) {
m = m + k; // m increases by 'k' each time
x[m] = a[i];
}

Here, m is an induction variable because every iteration it changes in a predictable way (m =

m + k).

Why important?

 Compilers can use this property to optimize loops (e.g., replacing repeated addition
with multiplication).

2. Forward Dependency

When the result of the next iteration depends on the current iteration’s value.

Example:

for (i = 1; i <= N; i++) {

x[i] = x[i+1]; // x[i] needs value from the future (i+1)
}

Problem: The value at x[i+1] is needed before it is updated.

Solution: Copy data to a temporary array first:

for (i = 1; i <= N; i++) {

xold[i] = x[i]; // Save old values
}
for (i = 1; i <= N; i++) {
x[i] = xold[i+1]; // Use saved values
}

3. Backward Dependency

When the result of the current iteration depends on the previous one’s result.
Example:

for (i = 1; i <= N; i++) {

x[i] = x[i-1] + y[i]; // Current uses previous (x[i-1])
}

Here, x[i] depends on x[i-1].

This is hard to parallelize because each step waits for the previous one to finish.

4. Breaking Out of a Loop

Sometimes, loops stop in the middle when a condition is met.

Example:

for (i = 1; i <= N; i++) {

if (x[i] == 10) break; // Stop if condition met
else {
// keep doing work
}
}

This is tricky for parallel execution because you don’t know in advance where it will stop.

5. Loop Splitting

Instead of doing multiple tasks in one loop, we split them into separate loops.
This often makes loops easier to optimize or parallelize.

Example 1:
// Original
for (i = 1; i <= N; i++) {
a[i] = b[i] + c[i];
c[i] = a[i-1];
}

// Split version
for (i = 1; i <= N; i++) {
a[i] = b[i] + c[i];
}
for (i = 1; i <= N; i++) {
c[i] = a[i-1];
}

Now, each loop has only one clear job.

Example 2:
// Original
for (i = 1; i <= N; i++) {
a[i] = b[i] + c[i];
c[i] = a[i+1];
}

// Split version
for (i = 1; i <= N; i++) {
x[i] = c[i];
c[i] = a[i+1];
}
for (i = 1; i <= N; i++) {
a[i] = b[i] + c[i];
}

Here, splitting makes the loop more structured and avoids conflicts.

In summary:

 Induction variables → variables that change predictably in a loop.

 Forward dependency → future values needed now.
 Backward dependency → current depends on past values.
 Break in loop → loop may stop early, harder to parallelize.
 Loop splitting → separate a complex loop into multiple simpler ones.

6. Loop Interchange

It means swapping the order of nested loops (outer ↔ inner).

This is usually done to improve performance (cache efficiency, parallelism, vectorization).

Basic Example
// Original
for (i = 1; i <= N; i++) { // Outer loop
for (j = 1; j <= M; j++) { // Inner loop
A[i][j] = A[i][j] + 1;
}
}

Now, if we interchange the loops:

// After interchange
for (j = 1; j <= M; j++) { // Outer loop
for (i = 1; i <= N; i++) { // Inner loop
A[i][j] = A[i][j] + 1;
}
}
Both give the same result, but performance may change.

Why Do We Interchange Loops?

1. Cache Efficiency

 Memory is stored row by row (row-major order in C, column-major in Fortran).

 If we access data row by row, it’s faster.
 If we access data column by column, it may cause cache misses.

Example:

// Bad (column-major access in C)

for (j = 1; j <= N; j++) {
for (i = 1; i <= N; i++) {
sum += A[i][j]; // Accessing column-wise (slow)
}
}

// Good (row-major access in C)

for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
sum += A[i][j]; // Accessing row-wise (fast)
}
}

2. Parallelization

 Some loop orders create dependencies (one iteration depends on another).

 By interchanging, we can sometimes remove dependencies → making it
parallelizable.

Example:

// With dependency
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
A[i][j] = A[i-1][j] + 1; // depends on previous row
}
}

// After interchange → dependency is along i, but j-loop is parallel

for (j = 1; j <= N; j++) {
for (i = 1; i <= N; i++) {
A[i][j] = A[i-1][j] + 1;
}
}

3. Vectorization
  Modern CPUs can process multiple elements at once (SIMD).
 Loop interchange can arrange data so CPUs can vectorize more easily.

In Summary:

 Loop Interchange = swap inner and outer loops.

 Why? → To improve memory access speed, parallelism, and vectorization.
 Must be done carefully → if there are loop-carried dependencies, results may
change.

Important Constraints in Shared Memory

1. Any process can wait for an arbitrary amount of time between any
two instructions

This means:

 When multiple processes (programs) are running, the operating system may pause
one process at any time.
 So, a process might stop after one line of code, and another process might run in
between.

Example:

 Imagine two people writing numbers on a whiteboard.

 Person A writes 5, then pauses.
 Person B comes and writes 10.
 Then Person A continues and writes the next step.

This shows that execution is not continuous—there can be gaps (waiting times) between
instructions.

2. Instructions cannot be expected to execute atomically

Atomic = something that happens all at once (indivisible).

 At the programming level, we often think instructions are atomic.

 But at the machine level, a single statement may break into multiple smaller steps.
 Because of this, another process can interrupt in between these steps.
Example: a = a + 1

Looks simple, right? But at the machine level, it’s actually several instructions:

1. Read value of a from memory into CPU register.

2. Add 1 to the register.
3. Store the new value back to memory.

So a = a + 1 is NOT atomic → it’s 3 steps.

Why is this important? (Race condition)

Suppose two processes run:

 Process 1: a = a + 1
 Process 2: a = a + 1

If a = 5 initially…

1. Process 1 reads a = 5.
2. Process 2 reads a = 5 (before Process 1 stores the update).
3. Process 1 adds 1 → result = 6, stores 6.
4. Process 2 adds 1 → result = 6, stores 6.

Final result = 6 instead of 7 → data lost!

This is called a race condition and happens because a = a + 1 was not atomic.

In summary:

 A process can pause anytime, letting others run.

 A high-level statement (like a = a + 1) is actually multiple machine steps, not a
single atomic operation.
 Because of this, if two processes run at the same time, unexpected results (like race
conditions) can happen.

Process Creation and Destruction

1. Creating Processes

 A process = a running program (like a worker doing a task).

 Sometimes, one process (the parent) creates other processes (the children) to share
the work.
Example in code:

id = create_process(N);

 This makes N child processes.

 The parent and child processes can be told to do different jobs.

switch(id) {
case 0: // parent
Do job 1;
break;
case 1: // child 1
Do job 2;
break;
case 2: // child 2
Do job 3;
break;
...
}

Analogy: Imagine a teacher (parent process) telling each student (child process) to solve a
different question in parallel.

2. Process Exit and Join

 After finishing their job, child processes exit (they die).

 But the parent process must wait for all children to finish before continuing.

Join_process(N, id);

 This ensures that all parallel tasks are done before moving on.

Analogy: Teacher waits until all students submit their answers, then collects everything and
continues teaching.

Visibility of Data
When processes/threads run, the question is: Who can see what data?

1. Information Sharing

 Processes (UNIX style): By default, each process has its own memory.
→ One process’s changes are not visible to others (unless special shared memory is
used).
 Threads (within the same process):
→ All threads share the same memory.
→ Any change by one thread is immediately visible to others.
Analogy:

 Processes = each student has their own notebook. They don’t see others’ notes unless
they share.
 Threads = students writing in the same notebook, so everyone sees updates.

2. Shared Memory

 Special memory that multiple processes can access.

 Functions:
o shared() → allocate shared memory (like giving a common notebook).
o free_shm(id) → free that shared memory (like throwing away the notebook).

Mutual Exclusion
When multiple processes/threads share memory, they may interfere with each other (race
condition).
To avoid this, we use locks.

 init_lock(id) → create a lock (like putting a lock on the notebook).

 lock(id) → before writing, a process must take the lock (no one else can write).
 unlock(id) → release the lock after writing (others can now write).

Analogy:

 Imagine students sharing a notebook.

 Only one student at a time can write because they pass around the “pen” (the lock).

In Summary:

 Process Creation → parent spawns child processes for parallel tasks.

 Exit/Join → parent waits for children to finish before continuing.
 Data Visibility → processes don’t share memory unless special shared memory is
used; threads share memory by default.
 Mutual Exclusion → locks prevent race conditions when multiple threads/processes
access the same data.

MPI (Message Passing Interface)

What is a process?
 A process is like a running program.
 It has two important parts:
o Program Counter: This is like a bookmark that remembers which instruction the
process is currently running.
o Address Space: This is like a private workspace or memory area where the process
stores its data.

Example:
Imagine you open a music player app on your computer. That music player is a process. It remembers
what song is playing (program counter) and has its own space to store data like your playlist (address
space).

Processes and threads

 A process can have multiple threads.
 Threads are smaller units inside a process that can run different parts of the program at the
same time.
 Each thread has its own program counter and stack (a stack is like a place where it keeps
track of what functions it’s running).
 All threads in the same process share the same address space (they can access the same
data).

Example:
In the music player, one thread might handle playing the music, while another thread shows the song
progress bar. Both threads share the playlist data in the same address space.

MPI (Message Passing Interface)

 MPI is a way for processes to communicate with each other.
 Important: Processes have separate address spaces, meaning they can’t directly see each
other’s data.
 So, they communicate by sending messages back and forth.

Example:
If you have two separate programs running on different computers, and you want them to work
together, you might use MPI to send data (like a chat message) from one to the other.

Interprocess Communication (IPC)

Since processes have separate address spaces, IPC involves two main things:

1. Synchronization: Making sure processes coordinate their actions correctly (like waiting for
each other before proceeding).
2. Data Movement: Actually sending data from one process’s memory to another’s.
Data Parallelism (SIMD – Single Instruction, Multiple Data)

 Everyone is doing the same thing at the same time, but on different data.
 SIMD means a single instruction is applied to multiple data items at once.

Example:
Imagine a group of workers peeling potatoes. Each worker peels one potato, but all of them are
doing the same action (peeling) at the same time.

In computing:
If you want to add 1 to every number in a list, data parallelism means:

 All processors run the same instruction: “add 1”

 Each works on a different part of the list at the same time.

Types of Parallel Computing Models

Task Parallelism (MIMD – Multiple Instruction, Multiple Data)

 Everyone is doing different things on different data.
 Each processor may be running different code on different inputs.

Example:
In a restaurant kitchen:

 One person is making pizza, another is cooking pasta, and another is making a salad.
 Each person does a different task, working with different ingredients.

In computing:
One core is sorting a list, another is compressing an image, another is downloading a file — all at the
same time.

SPMD – Single Program, Multiple Data

 All processors run the same program, but they may do different things depending on their
input or position.
 It's like MIMD in practice, but all units start with the same code.
 They’re not tightly synchronized — each runs independently.

Example:
Let’s say a classroom of students gets the same assignment sheet, but each student is told to solve
different questions based on their row number.

All students run the same program (assignment sheet), but:

  Row 1 solves Q1–3
 Row 2 solves Q4–6
 Row 3 solves Q7–9

They might finish at different times and don’t need to wait for each other.

SPMD vs SIMD vs MIMD

Conce
Instructions Data Sync? Real-World Example
pt
Differe
SIMD Same Synchronized Everyone peels a potato at once
nt
Differe
MIMD Different Not necessarily One cooks, one washes, one chops
nt
Same Differe Not synced per
SPMD All follow same guide, do different parts
(program) nt operation

Send = Mailing a Letter

 When a process sends a message, it’s like you’re writing a letter and putting it in the
mailbox to send to someone.
 You choose who it’s going to, write your message, and send it off.

Example:
Process A sends a message to Process B → like Alice mailing a birthday card to Bob.

Receive = Picking Up a Letter

 When a process receives a message, it’s like checking your mailbox and reading any letters
that have arrived.
 The process has to be ready and waiting (or check the mailbox regularly) to get the message.

Example:
Process B checks its "mailbox" and finds the message from Process A → like Bob checking his
mailbox and finding Alice’s card.

Scatter and Gather

Scatter:

 One message is broken up and sent to different places in memory.

  Like sending one big gift box, but when it’s opened, the items inside go to different shelves.

Example:
You send a box of school supplies to your house. When it arrives:

 Pencils go to the desk,

 Paper goes to the drawer,
 Markers go to the art shelf.

In computing:
A process sends a list of data, and each part is placed into a different variable or memory location.

Gather:

 The reverse of scatter. You collect data from multiple places and put it into one message to
send.
 Like gathering all the ingredients from different kitchen shelves into one shopping basket.

Example:
You collect apples from the fridge, sugar from the pantry, and flour from the cabinet, and put them in
one basket to bring to your friend.

In computing:
A process gathers different pieces of data and sends them together in a single message.

Network Performance

1. Latency – The delay before anything starts happening

 It’s the time between sending the message and when the first byte arrives at the receiver.

Real-life example:
You send a letter. Latency is the time it takes before your friend sees the envelope in their mailbox.

Lower latency = faster response time.

2. Bandwidth – How much data can be sent per second

 It’s like the width of a highway: how many cars (or messages) can travel per second.
 Higher bandwidth = more data can be sent at once.

Real-life example:
If you're mailing books, latency is how long it takes the first book to arrive, but bandwidth is how
many books you can send per hour.
Summary Table
Concept Analogy Simple Explanation
Send Mailing a letter Process sends a message to another
Receive Checking mailbox Process receives a message from another
Scatter Unpacking a box to different shelves One message goes to multiple memory spots
Data from many places packed into one
Gather Collecting from shelves into a box
message
Latency Time before a letter is delivered Delay before first data byte is received
Bandwidth Letters per hour How fast you can send lots of data

What is Cooperative Communication?

 It’s when two processes work together to exchange data.
 One process sends the data explicitly.
 The other process receives it explicitly.
 Both have to be involved actively

How it works in Message-Passing

 Process A wants to send data → it actively sends the message.
 Process B is waiting → it actively receives the message.
 Both processes coordinate (cooperate) to make sure data is correctly passed.

Advantage of Cooperative Communication

 Since the receiver must explicitly receive the data, any changes in its memory happen only
when it agrees.
 This means no surprises — the receiver is always ready and aware when data comes in.
 It combines communication (sending data) and synchronization (agreeing on when data
is sent/received).

Push Model (Active Data Transfer)

 The sender pushes data to the receiver.
 Sender decides when to send; receiver must be ready to accept.
 It’s like the sender “pushing” a package into the receiver’s hands, but only if the receiver is
standing there to take it.

Simple Real-Life Example:

Imagine two friends exchanging notes in class:

 Alice writes a note and passes it to Bob directly.

 Bob is watching and takes the note when Alice hands it over.
 Bob doesn’t get the note unless he actively takes it.
 Both need to cooperate — Alice can’t just throw it across the room; Bob needs to be ready.

What are One-Sided Operations?

 In one-sided communication, only one process actively participates.
 The other process doesn't need to explicitly do anything at the moment.
 The sender can write to or read from the memory of another process without the other
process doing anything right then.

Think of it like this:

Instead of both people needing to cooperate (like in cooperative communication), here only one
person is active, and the other doesn't have to respond immediately.

Remote Memory Access

There are two common one-sided operations:

1. Remote Write (Put):

a. One process writes data into another process’s memory.
b. The receiver doesn’t need to call a “receive” function.
2. Remote Read (Get):
a. One process reads data from another process’s memory.
b. The other process doesn’t need to “send” it; the reader just grabs it.

Real-Life Examples

Remote Write (Put) – Like leaving a note on someone’s desk:

 You walk over to someone’s desk and leave a note.

 They didn’t have to be there or pay attention at that moment.
 They’ll see the note when they check their desk later.

Remote Read (Get) – Like taking a book off someone’s shelf:

 You quietly walk over and take a book from your friend’s shelf.
 They don’t need to hand it to you or even know right away.
 You just pull the data when you need it.

Communication & Synchronization are Decoupled

  In cooperative operations, communication and synchronization happen together (both sides
need to be ready).
 In one-sided operations, they’re separated:
o Communication happens when one process wants.
o Synchronization can happen before or after, as needed.

Pull Model (Passive Data Transfer)

 In a pull model, the process pulls data when it wants it — like the get operation.
 The other process doesn’t “push” the data — it’s just sitting there, ready to be taken.

What is Collective Communication?

 It’s communication between more than two processes at the same time.
 All the processes involved cooperate to send or receive data in a specific pattern.

1. Barrier (Synchronize All Processes)

 Barrier is used to synchronize all processes in a group.
 It makes all processes wait until everyone reaches a certain point before moving forward.

Analogy:
Imagine a group of friends playing a game. Everyone has to wait at the starting line until all of them
are ready. Once everyone’s ready, they can all start together.

In computing:
If you have multiple processes running, a barrier will make all processes wait at the barrier point.
Once every process reaches it, they continue.

2. Broadcast (One-to-All)
 Broadcast is when one process sends data to all other processes in a group.

Analogy:
Imagine you have one speaker in a classroom, and the speaker announces the same message to the
whole class at the same time.

In computing:
Process A has some data and needs to send it to all other processes in the group. Process A broadcasts
the data to everyone.
3. Multicast (One-to-Many)
 Multicast is when one process sends data to many selected processes. It’s like a broadcast,
but the message goes to specific recipients, not everyone.

Analogy:
Imagine you’re a teacher, and you give handouts only to the students sitting in the front row, not the
whole class.

In computing:
Process A sends data to a specific set of processes (not all of them).

4. All-to-All
 All-to-All is when every process sends data to every other process.

Analogy:
Imagine each person at a party tells their own unique story to everyone else in the room.

In computing:
Each process sends data to every other process. So, all processes are sending and receiving data
from each other.

5. Reduction (All-to-One)
 Reduction is when all processes send data to one process, and then that one process
combines the data in some way (like summing up numbers, finding a max, etc.).

Analogy:
Imagine a group of friends collecting coins. Everyone puts their coins into a single basket, and then
one person counts all the coins.

In computing:
Every process contributes data (like a number) to one process, which then reduces it (adds,
multiplies, or performs another operation on it).

Summary of Collective Communication

Operatio
Description Example
n
Barrier Synchronize all processes at a point Everyone waiting at the start line until ready
Broadcas
One-to-all communication One speaker announcing to the whole class
t
Multicas One-to-many communication Teacher giving handouts to selected students
 t
All-to-All Every process sends data to all others Everyone telling their story at a party
Reductio
All-to-one, combining data Everyone contributes coins to one person to count
n

What is a Message-Passing Library Specification (an API)?

 A message-passing library (like MPI – Message Passing Interface) is a set of functions or
tools that allow different processes (programs) to communicate with each other over a
network.
 It's like a manual that explains how to send and receive messages between different
computers or processors in a parallel system.
 It's not a language (like Python or C), nor a compiler (the tool that translates your code into
machine code). It’s a library that provides a set of functions for communication.

Analogy:
Imagine you’re in a large office with multiple departments. The message-passing library is like the
internal office communication system (phone, email, etc.) that helps all departments talk to each
other. It doesn’t tell you how to do your job, but it gives you the tools to communicate.

Extended Message-Passing Model

 The extended message-passing model is just a fancy way of saying that the library supports
a wide range of communication and advanced parallel computing scenarios. This model
helps coordinate complex tasks and data between different processes.
 It’s flexible and designed to handle more complex needs beyond simple two-way
communication.

Analogy:
Think of a messaging system that doesn’t just send simple texts (like a basic phone call) but can also
handle group messages, files, video calls, and even conferences (more complex interactions). This
allows for a much broader range of tasks.

Not a Language or Compiler Specification

 The library does not tell you how to write your program. It provides functions for
communication, but you still need to write your code in your chosen programming
language (like C, C++, or Python).
 It does not compile your code either. It simply provides functions (like MPI_Send,
MPI_Recv, etc.) that allow you to send and receive messages.

Analogy:
Imagine the library as a messaging app (like WhatsApp) – it’s the tool for communication, but you
still need to type out the message yourself (you choose the language) and press “send” (you decide
when to communicate).
For Parallel Computers, Clusters, and Heterogeneous Networks
 It’s designed for systems with multiple computers or processors working together. These
can be:
o Parallel Computers: A single computer with multiple processors working in
parallel.
o Clusters: Multiple computers connected over a network working together.
o Heterogeneous Networks: Different types of systems (e.g., different hardware or
operating systems) working together.

Analogy:
You can think of it like a team of people working on different parts of a project. Some people are in
the same office (parallel computers), some are in different offices but connected by email (clusters),
and some people are in different cities with different tools (heterogeneous networks). The messaging
system helps them coordinate and communicate no matter where they are or what tools they’re
using.

Full-Featured
 The library is designed to handle advanced communication tasks like high-performance
data exchange, synchronization, and complex computations. It’s robust and capable of
handling a variety of situations.

Analogy:
It’s like having a full-featured toolbox for all sorts of repairs. Whether you need to tighten a bolt,
hammer a nail, or fix a complex machine, you have the tools available.

Designed for End Users, Library Writers, and Tool Developers

 End users: People who use the library to send and receive messages in their parallel
programs.
 Library writers: People who write the library itself, adding new features or improving
performance.
 Tool developers: People who build tools or software on top of the library to make
programming easier or more efficient.

Analogy:
Think of it as a community effort:

 End users use the messaging app to send messages.

 App developers build and improve the app.
 Tool creators develop features like filters or games within the app to enhance the experience.

Portable
  The library is designed to work on many different types of systems. It’s portable, meaning
the same code you write using this library can run on different computers, networks, or even
different kinds of hardware without changes.

Analogy:
You write a letter in a certain language, and it can be read by anyone across the world, no matter
what language they speak or what system they use (as long as they understand the language).

Basic MPI Code

#include "mpi.h"
#include <stdio.h>
int main(int argc, char *argv[])
{
MPI_Init(&argc, &argv);
printf("Hello, world!\n");
MPI_Finalize();
return 0;
}

Explanation:
int main(int argc, char *argv[])
MPI_Init(&argc, &argv);
This initializes the MPI environment.
Must be called before any other MPI functions.
Prepares the program to run in parallel across multiple processes.
The &argc and &argv pass command-line info to MPI, allowing it to manage arguments if needed.
_______________________________________________________________________________
Since this program uses MPI, this message will be printed by every process running the program.

MPI_Finalize();
This cleans up and shuts down the MPI environment.
Must be called at the end of all MPI programs.
After this call, no MPI functions can be used.

This program initializes MPI, prints "Hello, world!" from every process (e.g., if you run with 4
processes, you’ll see 4 lines), then cleans up and exits.

 Each “Hello, world!” is printed by a different process.

 The order of lines might not be the same every time because processes run independently
and print asynchronously.
 To see which process prints what, you can modify the code like this:

#include "mpi.h"
#include <stdio.h>

int main(int argc, char *argv[])

{
MPI_Init(&argc, &argv);

int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Get process ID (rank)

printf("Hello, world from process %d!\n", rank);

MPI_Finalize();
return 0;
}

Running the modified program with 4 processes might print:

Hello, world from process 0!
Hello, world from process 2!
Hello, world from process 1!
Hello, world from process 3!

 Each process has a unique rank (ID), starting from 0.

 This helps you identify which process is printing.

Error Handling
You're diving into one of the most important aspects of MPI programming: error handling. In
distributed systems, a single failure can ripple across all processes—so how you handle errors can
make or break your application. Let’s unpack each statement in depth:
 1. By Default, an Error Causes All Processes to Abort
 MPI uses a default error handler called MPI_ERRORS_ARE_FATAL.
 If any MPI function encounters an error (e.g., invalid communicator, out-of-range rank), this
handler calls MPI_Abort, which:
o Immediately terminates all processes in the communicator.
o Returns a non-zero exit code to the system.

Why this default?

 In tightly coupled parallel programs, one process failing often means the computation is no
longer valid.
 Aborting prevents deadlocks or corrupted results.

Example:

MPI_Comm_rank(MPI_COMM_WORLD, &rank); // If MPI_COMM_WORLD is

invalid, all processes abort

2. The User Can Cause Routines to Return (with an Error

Code) Instead
You can override the default behavior by setting a different error handler:

MPI_Errhandler_set(MPI_COMM_WORLD, MPI_ERRORS_RETURN);

Now, instead of aborting, MPI functions will return an error code like MPI_ERR_COMM,
MPI_ERR_RANK, etc.

Benefits:
 You can check the return value (ierr) and decide what to do:
o Log the error
o Retry the operation
o Skip the faulty part and continue

Example:

int ierr = MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (ierr != MPI_SUCCESS) {
printf("MPI error occurred in rank retrieval\n");
}

3. In C++, Exceptions Are Thrown (MPI-2)

MPI-2 introduced C++ bindings where errors could be handled using exceptions, making it more
idiomatic for C++ developers.

Example:

try {
int rank = MPI::COMM_WORLD.Get_rank();
} catch (MPI::Exception& e) {
std::cerr << "MPI Exception: " << e.Get_error_string() <<
std::endl;
}

Important Note:
 These C++ bindings were deprecated in MPI-3 and are no longer recommended.
 Most modern C++ MPI programs use C bindings with custom wrappers or exception logic.

4. A User Can Also Write and Install Custom Error

Handlers
MPI allows you to define your own error-handling logic by creating a custom error handler.

Steps:
1. Define a handler function:

void my_handler(MPI_Comm *comm, int *err_code, ...) {

// Custom logic: log, recover, notify, etc.
}

2. Create and attach the handler:

MPI_Errhandler errhandler;
MPI_Comm_create_errhandler(my_handler, &errhandler);
MPI_Comm_set_errhandler(MPI_COMM_WORLD, errhandler);

Use Cases:
  Logging detailed diagnostics
 Notifying external systems
 Attempting recovery or fallback strategies

5. Libraries Might Want to Handle Errors Differently

from Applications
This is a subtle but powerful design principle.

Why the difference?

 Libraries are meant to be reused across many applications. They should:
o Avoid aborting the entire program
o Return error codes or raise exceptions
o Let the application decide how to respond
 Applications, on the other hand, might:
o Abort if a critical error occurs
o Display user-friendly messages
o Log and escalate errors

Example:
A matrix multiplication library might catch an MPI error internally and return a status code. The
calling application can then choose to retry, skip, or terminate.

Summary Table
Aspect Default Behavior Customizable? Best For
Error Handling Abort all processes Yes Critical failures
Return Codes No abort Yes Graceful recovery
C++ Exceptions Thrown (MPI-2) ❌ Deprecated Legacy C++
Custom Handlers User-defined Yes Logging, debugging
Library vs App Different strategies Yes Modularity vs control

If you're building a real-world MPI application, mastering error handling is essential. Want help
writing a custom error handler or simulating an MPI error to test your setup?
Basic MPI communication routines

1. MPI_Send

The function MPI_Send is used to send data from one process to another.

Syntax:

int MPI_Send(void *data_to_send, int send_count, MPI_Datatype send_type,

int destination_ID, int tag, MPI_Comm comm);

Parameters explained:

 data_to_send → A pointer to the actual data you want to send.

 send_count → Number of elements you want to send.
 send_type → The datatype of elements being sent (e.g., MPI_INT, MPI_FLOAT).
 destination_ID → The ID (rank) of the process you want to send data to.
 tag → An integer label to identify the message. Helps the receiver distinguish
between multiple incoming messages.
 comm → The communicator (usually MPI_COMM_WORLD), which defines the group of
processes that can communicate.

Behavior:

 When you call MPI_Send, the function blocks until the system has safely stored or
delivered the message.
 This means you can safely reuse or change the buffer (data_to_send) only after
MPI_Send returns.
 So, it provides both data transfer and a bit of synchronization.

2. MPI_Recv

The function MPI_Recv is used to receive data sent by another process.

Syntax:

int MPI_Recv(void *buffer, int recv_count, MPI_Datatype recv_type,

int source_ID, int tag, MPI_Comm comm, MPI_Status *status);

Parameters explained:

 buffer → Memory location where the incoming message will be stored.

 recv_count → Maximum number of elements the buffer can hold.
 recv_type → The datatype of elements expected (e.g., MPI_INT, MPI_FLOAT).
 source_ID → The ID (rank) of the process you expect the data from. You can also
use MPI_ANY_SOURCE if you don’t care who sends it.
  tag → Must match the tag in the sender’s message. You can also use MPI_ANY_TAG if
you don’t care.
 comm → The communicator.
 status → A structure (output) that gives extra info about the message (like actual
source, tag, and number of elements received).

Behavior:

 MPI_Recv blocks until the expected message arrives and is copied into the buffer.
 After return, you can immediately use the received data.

3. Example

Let’s say we have two processes:

 Process 0 sends an integer.

 Process 1 receives that integer.

#include <mpi.h>
#include <stdio.h>

int main(int argc, char** argv) {

MPI_Init(&argc, &argv);

int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (rank == 0) {
int data = 42;
MPI_Send(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
printf("Process 0 sent %d\n", data);
} else if (rank == 1) {
int received_data;
MPI_Status status;
MPI_Recv(&received_data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD,
&status);
printf("Process 1 received %d\n", received_data);
}

MPI_Finalize();
return 0;
}

Output (order may vary depending on runtime):

Process 0 sent 42
Process 1 received 42

In short:

 MPI_Send: “Here, take this data.” (blocks until safe)

  MPI_Recv: “I’m waiting for data.” (blocks until received)

What is OpenMP?

 OpenMP = Open Multi-Processing.

 It is a tool (API) used in C, C++, and FORTRAN to make programs run in parallel
on shared memory machines (like multicore CPUs).
 Instead of writing low-level threading code, you just add special instructions
(directives) to tell the compiler where parallelism should happen.

How does it work?

 These instructions are written using #pragma in C/C++.

 They tell the compiler: “Hey, run this part of the code in parallel using multiple
threads.”
 The compiler then creates and manages the threads for you.

Directive format
#pragma omp directive [clause list]

 #pragma omp → tells the compiler this is an OpenMP directive.

 directive → the action (e.g., parallel, for, critical).
 clause list → extra options (like number of threads, private/shared data).

Example: Parallel Region

#pragma omp parallel
{
// This block runs in parallel by multiple threads
printf("Hello from thread!\n");
}

 When the program reaches #pragma omp parallel:

o The main thread (thread 0) creates a group of threads.
o Each thread runs the code inside the block.

Important Points
 1. Program starts in serial mode (single thread).
2. When it hits a parallel directive, multiple threads are created.
3. The main thread becomes the master thread (thread ID = 0).
4. Other threads are given their own IDs (1, 2, …).
5. After the parallel block, threads join back and execution continues serially.

In short:
OpenMP lets you turn normal code into parallel code just by adding special #pragma omp
lines. The compiler handles thread creation, synchronization, and shared data automatically.

Problem Without Reduction

Suppose you want to calculate the sum of an array in parallel:

 Each thread adds part of the array.

 If all threads directly update the same variable sum, they will interfere (race
condition).

We need a way to let each thread have its own local copy, and then combine them safely at
the end.

What reduction Does

#pragma omp parallel reduction(+: sum) num_threads(8)

 reduction(+: sum) means:

1. Each thread gets its own private copy of sum, initialized to 0 (the identity for
+).
2. Each thread adds to its private copy.
3. When the parallel block ends, OpenMP combines all private sums into the
final shared sum using +.
 Works with operators like +, *, -, &, |, ^, &&, ||.

Example
#include <stdio.h>
#include <omp.h>

int main() {
int sum = 0;

#pragma omp parallel reduction(+: sum) num_threads(4)

{
 int id = omp_get_thread_num();
sum += id; // each thread adds its ID to its private copy
printf("Thread %d local sum = %d\n", id, sum);
}

printf("Final sum = %d\n", sum);

return 0;
}

What Happens Here

 4 threads are created.

 Each has its own sum starting from 0.
 Suppose threads IDs are 0,1,2,3 → local sums = 0,1,2,3.
 At the end, OpenMP combines them:

sum=0+1+2+3=6sum = 0 + 1 + 2 + 3 = 6

In short:

 reduction = private copies for each thread + safe combination at the end.
 Prevents race conditions when accumulating results like sum, product, min, max, etc.

Parallel + For

 The for directive is used when you want to run a for loop in parallel.
 Each thread gets a portion of the loop iterations to execute.
 You usually combine it with #pragma omp parallel → written as:

#pragma omp parallel

{
#pragma omp for
for (int i = 0; i < N; i++) {
// work split among threads
}
}

OpenMP divides the loop iterations across threads automatically.

Useful Clauses with for

 private(var) → each thread gets its own copy of var.

 firstprivate(var) → like private, but initialized with the original value.
 lastprivate(var) → after the loop, the last iteration’s value is copied back.
 reduction(op: var) → reduces private results into a single result.
  schedule(type, chunk) → controls how iterations are divided (static, dynamic,
guided).
 nowait → allows threads to skip waiting at the end of the loop.
 ordered → ensures certain parts run in order (rarely needed).

Example (Parallel For Loop)

#include <stdio.h>
#include <omp.h>

int main() {
int N = 8;
int arr[N];

#pragma omp parallel

{
#pragma omp for private(i)
for (int i = 0; i < N; i++) {
arr[i] = i * i; // each thread calculates different parts
printf("Thread %d computes arr[%d] = %d\n",
omp_get_thread_num(), i, arr[i]);
}
}

printf("Final array: ");

for (int i = 0; i < N; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}

Each thread computes a portion of the array.

Parallel + Sections

 The sections directive is used when you want different tasks (not loop iterations) to
run in parallel.
 Each section is assigned to a thread.

#pragma omp parallel sections

{
#pragma omp section
{
// Task 1
}

#pragma omp section

{
// Task 2
}
}

Useful when tasks are unrelated but can run at the same time.
In Simple Words:

 parallel for → split loop iterations across threads.

 parallel sections → split independent tasks across threads.

What is the schedule clause?

When you use #pragma omp for, OpenMP needs to decide which thread runs which loop
iterations.
The schedule clause controls this distribution.

General form:

#pragma omp for schedule(type [, chunk])

 type → static, dynamic, guided, or runtime

 chunk (optional) → number of loop iterations each thread gets at a time

Types of Scheduling

1. Static Scheduling

 Iterations are divided evenly among threads before the loop starts.
 Each thread gets a fixed set of iterations.
 If you specify a chunk, each thread gets chunk-sized blocks in a round-robin fashion.

Example:

#pragma omp for schedule(static, 2)

If 8 iterations and 4 threads → each thread gets 2 iterations.

Best for: loops where all iterations take about the same time.

2. Dynamic Scheduling

 Iterations are given to threads on the fly.

 A thread grabs the next chunk of iterations whenever it finishes its current work.
 Good for uneven workloads.

Example:
#pragma omp for schedule(dynamic, 2)

 Each thread takes 2 iterations at a time, and when done, grabs more.

Best for: when some iterations take longer than others.

3. Guided Scheduling

 Similar to dynamic, but chunks start large and get smaller over time.
 Helps balance load while reducing overhead.

Example:

#pragma omp for schedule(guided, 2)

 Threads first get large blocks, then smaller ones.

Best for: large loops with unpredictable workload.

4. Runtime Scheduling

 The scheduling type is not fixed in the code.

 Instead, it is chosen at runtime using the environment variable:
 export OMP_SCHEDULE="dynamic,4"

 Very flexible for testing performance without changing code.

Example:

#pragma omp for schedule(runtime)

Summary Table
Schedule Type How Work is Assigned When to Use

static Evenly divided, fixed chunks Balanced workloads

dynamic Threads grab chunks as they finish Irregular workloads

guided Large chunks first, smaller later Large, varying workloads

runtime Decided at runtime via env variable For tuning/test flexibility

In short:

 static → equal division (simple, efficient).

  dynamic → give work as needed (load balancing).
 guided → smart balance (big → small chunks).
 runtime → let user decide at run time.

Normal Behavior of for Directive

By default, every OpenMP for loop ends with an implicit barrier.

 That means all threads must wait until every thread finishes its assigned iterations
before moving on.
 This is useful in many cases but sometimes it slows things down unnecessarily.

What nowait Does

The nowait clause removes that barrier.

 Threads that finish their work can move on immediately to the next directive.
 Other threads will continue their work without blocking the fast ones.

Syntax:

#pragma omp for nowait

for (int i = 0; i < N; i++) {
// loop work
}

Example Problem: Searching Two Lists

Suppose you want to check if a name exists in two separate lists:

#include <stdio.h>
#include <omp.h>

int main() {
char *list1[] = {"Alice", "Bob", "Charlie"};
char *list2[] = {"Eve", "Bob", "David"};
char *name = "Bob";
int found1 = 0, found2 = 0;

#pragma omp parallel

{
#pragma omp for nowait
for (int i = 0; i < 3; i++) {
if (strcmp(list1[i], name) == 0)
found1 = 1;
}

#pragma omp for nowait

for (int i = 0; i < 3; i++) {
if (strcmp(list2[i], name) == 0)
 found2 = 1;
}
}

printf("Found in list1? %d\n", found1);

printf("Found in list2? %d\n", found2);
return 0;
}

Why Use nowait Here?

 Without nowait:
o After the first for, all threads would stop and wait before moving to the
second list.
 With nowait:
o Threads can immediately start checking the second list without waiting for
others to finish the first.

This saves time when loops are independent (like checking two different lists).

In short:

 nowait lets threads skip the waiting barrier.

 Good when loops are independent and don’t need synchronization.
 Helps improve performance by reducing idle time.

What is sections?

 While for is for loops, sections is for different tasks.

 Each section inside a sections block is treated as a separate job, and OpenMP
assigns them to threads.
 Useful when you want to run independent pieces of code in parallel.

General Form
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
{
// Task 1
}

#pragma omp section

{
// Task 2
}
 #pragma omp section
{
// Task 3
}
}
}

 Each section block is given to one available thread.

 If there are more tasks than threads, some threads may run more than one section.

Example

Imagine you want to perform three different tasks:

1. Compute factorial
2. Compute Fibonacci
3. Print a message

#include <stdio.h>
#include <omp.h>

int factorial(int n) {
int f = 1;
for (int i = 1; i <= n; i++) f *= i;
return f;
}

int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
{
printf("Factorial(5) = %d (Thread %d)\n", factorial(5),
omp_get_thread_num());
}

#pragma omp section

{
printf("Fibonacci(6) = %d (Thread %d)\n", fibonacci(6),
omp_get_thread_num());
}

#pragma omp section

{
printf("Hello from thread %d!\n", omp_get_thread_num());
}
}
}
 return 0;
}

Output (example)
Factorial(5) = 120 (Thread 1)
Fibonacci(6) = 8 (Thread 2)
Hello from thread 3!

(The exact thread IDs may differ each run.)

Key Points

 sections → divides tasks (not loops).

 Each section is run once by one thread.
 All threads wait at the end of the sections block unless you add nowait.

In short: Use sections when you have different independent tasks to run in parallel.

1. Barrier

 All threads must wait until every thread reaches this point.
 Ensures no thread goes ahead too far.

Example:

#pragma omp parallel

{
work1();
#pragma omp barrier // wait here until all threads finish work1
work2();
}

2. Single

 Only one arbitrary thread executes the block.

 Other threads skip it, but wait at the end (unless you add nowait).

Example:

#pragma omp single

{
printf("This is printed only once.\n");
}
3. Master

 Only the master thread (ID = 0) executes the block.

 Other threads skip it (no implicit barrier here).

Example:

#pragma omp master

{
printf("Executed only by master thread (0).\n");
}

4. Critical

 A block of code executed by only one thread at a time.

 Used to protect shared data from race conditions.

Example:

#pragma omp critical

{
sum += x; // only one thread at a time can update sum
}

5. Atomic

 Makes a single memory update atomic (thread-safe).

 Lighter than critical, but only works for simple updates.

Example:

#pragma omp atomic

sum += x; // update is atomic

6. Nowait

 Removes the implicit barrier at the end of constructs like for, single, or sections.
 Lets threads move ahead without waiting for others.

Example:

#pragma omp for nowait

for (int i = 0; i < N; i++) {
work(i);
}
7. Ordered

 Ensures that certain parts of a loop are executed in sequential order, even inside a
parallel loop.

Example:

#pragma omp parallel for ordered

for (int i = 0; i < 5; i++) {
work(i);
#pragma omp ordered
printf("Output in order: %d\n", i);
}

Summary Table
Directive Meaning

barrier All threads wait here before moving on

single Only one (any) thread executes block

master Only thread 0 executes block

critical Block executed by one thread at a time (prevents race conditions)

atomic Single memory update is atomic (lighter than critical)

nowait Threads don’t wait at the end of a construct

ordered Executes code in the original sequential order

In short: These constructs help control who executes what and ensure safe access to shared
data in OpenMP.

1. OMP_NUM_THREADS

 Sets the default number of threads to be created in a parallel region.

 Example:

export OMP_NUM_THREADS=8

Means: each #pragma omp parallel will start with 8 threads (unless overridden by
num_threads() clause).
2. OMP_DYNAMIC

 Controls whether OpenMP can adjust the number of threads dynamically at

runtime.
 Useful when system load changes.
 Example:

export OMP_DYNAMIC=TRUE

Threads may increase or decrease depending on workload.

3. OMP_NESTED

 Enables nested parallelism (parallel regions inside parallel regions).

 Example:

export OMP_NESTED=TRUE

Inner #pragma omp parallel will create its own team of threads instead of merging into
the outer team.

4. OMP_SCHEDULE

 Sets the scheduling policy for #pragma omp for schedule(runtime).

 Example:

export OMP_SCHEDULE="static,4"

Each thread gets chunks of 4 iterations in round-robin order.

If you change it to:

export OMP_SCHEDULE="dynamic,2"

Each thread grabs 2 iterations at a time, dynamically assigned.

Example: Setting Environment Variables

In Linux/macOS (bash):

export OMP_NUM_THREADS=8
export OMP_DYNAMIC=FALSE
export OMP_NESTED=TRUE
export OMP_SCHEDULE="static,4"

In C Shell:
setenv OMP_NUM_THREADS 8
setenv OMP_DYNAMIC FALSE
setenv OMP_NESTED TRUE
setenv OMP_SCHEDULE "static,4"

Summary
Variable What it Does

OMP_NUM_THREADS Sets number of threads in parallel regions

OMP_DYNAMIC Allows OpenMP to adjust thread count dynamically

OMP_NESTED Enables nested parallel regions

Sets scheduling policy for loops (static, dynamic, etc.) when runtime is
OMP_SCHEDULE
used