Hello World Program using OpenMP

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

void Hello(void); // Thread function

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

int thread_count = strtol(argv[1], NULL, 10); // number
of threads

#pragma omp parallel num_threads(thread_count)

Hello(); // each thread executes this function

return 0;
}

void Hello(void) {
int my_rank = omp_get_thread_num(); // thread ID
int thread_count = omp_get_num_threads(); // total
threads

printf("Hello from thread %d of %d\n", my_rank,

thread_count);
}

Steps to Compile and Run OpenMP Program

Compilation:
To compile an OpenMP program using GCC, the -fopenmp ag must be used:
gcc -g -Wall -fopenmp -o omp_hello omp_hello.c

Execution:
The number of threads is given as a command-line argument:
./omp_hello 4

(This runs the program with 4 threads.)

Output:
Every thread prints a message.
Since threads run in parallel, the order of output is unpredictable.
Example:
Hello from thread 0 of 4
fl
Hello from thread 2 of 4
Hello from thread 1 of 4
Hello from thread 3 of 4

Explanation of #pragma Directive (Exam

Answer)
• In C/C++, #pragma is a compiler directive used to give special instructions to the
compiler.

• Pragmas are not part of standard C but are extensions.

If a compiler does not support a particular pragma, it simply ignores it.

• OpenMP uses pragma directives to specify parallel regions.

• All OpenMP directives begin with:

#pragma omp

•
Example:

#pragma omp parallel num_threads(4)

Meaning:

• Create a team of 4 threads.

• Each thread will execute the next structured block of code.

• An implicit barrier exists at the end of the block, so all threads synchronize before
continuing.

Short 2–3 Line De nition (Very Exam Friendly)

• #pragma is a compiler directive used to provide additional instructions to the compiler.

• OpenMP uses #pragma omp directives to specify parallel regions in a program.

• If unsupported, pragmas are ignored, so the program still compiles and runs sequentially.
fi
 Differences Between Pthreads and OpenMP
Pthreads OpenMP

1. Library-based API: Pthreads is a POSIX 1. Compiler-based API: OpenMP requires compiler

thread library linked with C programs. support since it uses #pragma omp directives. A
Works with any C compiler that supports the compiler without OpenMP support cannot compile
Pthreads library. parallel code.

2. Low-level, explicit thread control: 2. High-level abstraction: Programmer can simply

Programmer must explicitly create threads, mark a block (e.g., loop) as parallel, and the
manage attributes, assign tasks, and handle compiler/runtime decides thread creation and work
synchronization. distribution.

3. Harder to program: More code required 3. Easier to program: Parallelization can be added
to manage thread creation, joining, and incrementally by inserting pragmas into existing
communication. serial code.

4. More exible: Allows full control over 4. Less exible at low level: Some ne-grained
thread behavior, scheduling, and interaction. thread interactions are harder to express since the
Suitable for complex low-level threading. compiler handles many details.

5. Portable across any platform with a 5. Not portable if compiler does not support
Pthreads library. OpenMP.

6. Works well for systems programming 6. Designed mainly for shared-memory parallel
and OS-level threading. programs and scienti c computing.

7. No incremental parallelization: Hard to 7. Supports incremental parallelization: Existing

convert a serial program into parallel code serial code can be parallelized step-by-step using
gradually. pragmas.

• Pthreads is a low-level thread library where the programmer explicitly creates and manages
threads.

• OpenMP is a high-level, compiler-supported API that uses #pragma omp directives to

parallelize code.

• Pthreads gives full control but requires more coding, while OpenMP is easier and supports
incremental parallelization.
fl
fl
fi
fi
“In OpenMP, what is meant by a team of threads? Explain the master, parent, and child
threads and their roles within a parallel region with a neat diagram.”

Team of Threads in OpenMP

In OpenMP, when a program encounters a parallel directive, the single main thread creates
additional threads so that a block of code can execute in parallel.
The collection of all threads created to execute this parallel block is called a team of threads.

Before the parallel region, the program has only one thread.
When the parallel region begins:

• The original thread continues executing.

• Additional threads are created.

• Together, they form a team.

Master, Parent, and Child Threads

1. Master Thread

• The master thread is thread 0 of the team.

• It is the thread that originally starts the program.

• It participates in the parallel region unless explicitly excluded (using master, single,
etc.).

• After the parallel region ends, the master resumes normal sequential execution.

2. Parent Thread

• The parent thread is the thread that encounters a #pragma omp parallel directive.

• It creates (forks) new threads to form the team.

• In most cases, the parent thread is the master thread itself.

• After the parallel region, child threads terminate, and the parent thread continues.

3. Child Threads

• These are the threads created by the parent thread when entering the parallel region.

• They are numbered 1, 2, ..., thread_count − 1.

• Each child thread executes the same block of code in parallel with the master.
 • When the parallel region ends, child threads terminate.

Roles Inside a Parallel Region

1. Thread creation (Forking phase)
◦ Parent thread encounters the parallel directive.

◦ It creates thread_count – 1 child threads.

◦ Together, they form a team.

2. Parallel execution
◦ All threads (master + children) execute the same block of code.

◦ Each thread has its own stack and private local variables.
3. Implicit barrier at end of parallel region
◦ All threads must nish the block before any proceeds.

4. Join phase
◦ Child threads terminate.

◦ Parent (usually master) continues with the next statements after the parallel block.

Overall Relationship
• The parent thread creates the team.

• Inside the team, the master thread (ID 0) and child threads execute the parallel code.

• When the parallel region ends, the execution returns to the single parent thread.
fi
Neat Exam Diagram (Thread Fork–Join
Model)
Single Thread (Before Parallel Region)
|
| encounters #pragma omp parallel
|
-------------------------------
| | |
| | |
Master Thread Child Thread 1 Child Thread 2
\ | /
\ | /
\ | /
---- Parallel Region ----
(Team of Threads)
(All execute)
--------------------------
| Barrier |
--------------------------
|
| Child threads exit
|
Master/Parent thread continues
(After Parallel Region)
Fork-Join Model in OpenMP – Explained
The fork-join model is the fundamental execution model used by OpenMP for parallel
programming. It describes how threads are created and synchronized during the execution of a
program.

Explanation
A program starts with a single main thread (called the master thread). When it encounters a
parallel region, this master thread forks (creates) a team of additional threads. All these threads
execute the code inside the parallel region.

After completing the parallel section, all threads join back into a single thread (the master), and the
program continues sequentially.

Steps in the Fork-Join Model

1. Single Thread Execution

• The program begins with one thread only (master thread).

2. Fork Phase

• When the master thread reaches a #pragma omp parallel directive, it spawns
(forks) multiple threads.

• These newly created threads are called child threads.

3. Parallel Execution

• The master and child threads together form a team of threads.

• They execute the instructions inside the parallel block.

4. Join Phase

• After the parallel region ends, all child threads terminate.

• The master thread continues the execution of the program sequentially.

Diagram
Single Master Thread
|
| encounters parallel region
V
--------- Fork ---------
| | |
Thread 0 Thread 1 Thread 2 ... (Team of Threads)
| | |
| <---- Parallel Work -->|
-------------------------
|
| join
V
Master Thread continues

Key Features
• Follows a shared-memory model (threads share variables unless speci ed private).

• Threads are created only around parallel regions, not throughout the program.

• Ensures synchronization before and after parallel blocks.

Short Exam-Friendly De nition

The fork–join model in OpenMP describes how a single master thread creates a team of
threads at the start of a parallel region (fork), all threads execute in parallel, and then they
synchronize and terminate at the end of the region (join), returning control to the master
thread.
fi
fi
Why Conditional Compilation Using _OPENMP
Is Important & What Errors Occur Without It
Conditional compilation with the macro _OPENMP is used to check whether the compiler actually
supports OpenMP. The macro is automatically de ned only when the program is compiled with
OpenMP enabled. This makes the program portable, meaning it can be compiled on any system —
regardless of whether OpenMP is available.

Importance of Using _OPENMP

1. Prevents Compilation Errors

If a compiler does not support OpenMP:

• It will not understand the header le omp.h

• It will not recognize OpenMP library calls

Using:

#ifdef _OPENMP
#include <omp.h>
#endif
avoids errors and ensures only valid code is compiled.

2. Avoids Unde ned Function Errors

Function calls such as:

omp_get_thread_num();
omp_get_num_threads();
exist only in OpenMP libraries.
Without _OPENMP, these calls cause “unde ned reference” errors during compilation or linking.

Using conditional code:

#ifdef _OPENMP
my_rank = omp_get_thread_num();
#else
my_rank = 0;
#endif
ensures a safe fallback for serial execution.

3. Allows Code to Run on Both OpenMP and Non-OpenMP Systems

fi
fi
fi
fi
 If OpenMP is unavailable:

• The parallel sections degrade gracefully to single-threaded execution

• The program still runs correctly

• No crashes or unpredictable behavior occur

This makes the program portable across:

• Different compilers

• Environments where OpenMP is disabled

• Systems without OpenMP libraries

4. Improves Program Reliability and Maintainability

Using _OPENMP keeps the program clean and prevents unexpected failures when moving between:

• Development machines

• University lab systems

• HPC clusters

Errors That Occur If _OPENMP Is Not Used

If we do not use conditional compilation and compile with a non-OpenMP compiler:

1. Header File Error

fatal error: omp.h: No such file or directory

2. Unde ned Function Errors

undefined reference to 'omp_get_thread_num'

undefined reference to 'omp_get_num_threads'
3. Parallel Constructs Ignored

The compiler silently ignores:

#pragma omp parallel

→ Code becomes serial even though OpenMP functions are still executed → runtime crash.

4. Wrong Thread Values

Without conditional fallback, variables like:

fi
my_rank, thread_count
remain uninitialized, leading to:

• Incorrect output

• Segmentation faults

• Nonsense calculations

Final Combined Exam-Ready Paragraph

Conditional compilation using _OPENMP is important because it allows OpenMP-speci c code to
be included only when the compiler actually supports OpenMP. This ensures portability and
prevents errors when the program is compiled on systems without OpenMP. Without this check,
including omp.h and calling functions like omp_get_thread_num() or
omp_get_num_threads() will cause compilation and linking errors. The compiler will also
ignore #pragma omp parallel, making the program run serially while still trying to call
missing OpenMP functions, leading to crashes or incorrect behavior. By using _OPENMP, the
program cleanly switches to a safe serial version, making it reliable and portable across different
systems.

fi
Critical Section and Race Condition
In parallel programming, multiple threads execute simultaneously and often need to access shared
memory or shared variables. If this access is not controlled properly, serious errors can occur. Two
important concepts related to this are race conditions and critical sections.

1. Race Condition (De nition & Explanation)

A race condition occurs when two or more threads/processes try to read and update a shared
resource at the same time, and the nal output depends on the unpredictable timing of these
operations.
Since thread execution is concurrent, the order in which updates happen may vary each time the
program is run, resulting in incorrect, inconsistent, and non-deterministic outputs.

Why race conditions happen

• Threads operate concurrently.

• Shared data (global variables, arrays, counters etc.) is not protected.

• At least one thread performs a write/update operation.

Example

Assume:

global_sum = 0
Thread 0 computed value = 1
Thread 1 computed value = 2
Both threads execute:

global_sum += my_value;
If the following interleaving occurs:

Time Thread 0 Thread 1

0 Reads global_sum = 0

1 Reads global_sum = 0

2 Computes 0 + 1 Computes 0 + 2
3 Writes 1 Writes 2

Final result becomes 2, and the contribution of Thread 0 is lost.

This is a race condition.

Why race conditions are dangerous

fi
fi
 • Produces wrong output

• Output varies from run to run

• Dif cult to detect and debug

• Can crash programs or corrupt data

2. Critical Section (De nition & Purpose)

A critical section is a block of code that accesses or modi es shared data and therefore must be
executed by only one thread at a time.
To ensure this, parallel programming languages and APIs provide synchronization constructs.

In OpenMP

We can protect a critical section using:

#pragma omp critical

{
global_sum += my_value;
}
This ensures:

• Mutual exclusion

• Only one thread enters the block at any time

• No overlapping updates

• Shared data remains consistent

Other ways to protect a critical section

• Mutex locks

• Semaphores

• Atomic operations

• Locks in Pthreads (pthread_mutex_lock)

• OpenMP atomic directive

3. Relationship Between Race Condition and Critical Section

• A race condition happens because a critical section is not protected.

• A critical section eliminates race conditions by enforcing mutual exclusion.

fi
fi
fi
 • In short:
Race condition = problem
Critical section = solution

4. Importance in Parallel Programming

In parallel computing, correctness of a program depends on how shared data is managed. If race
conditions are not controlled, programs may:

• Produce incorrect outputs

• Lose performance due to thread interference

• Become non-reproducible (different results each run)

• Fail in high-performance applications (HPC, scienti c computing)

Using critical sections ensures:

• Data integrity

• Program correctness

• Predictable behavior

• Safe cooperation among threads

5. Diagram for Better Understanding (Exam-friendly)

Thread 0 Thread 1
---------------- ----------------
global_sum += 1 global_sum += 2
| |
| (overlap occurs) |
V V
Race Condition leads to WRONG result

Correct use:

#pragma omp critical

{
global_sum += my_value;
}

Only one thread enters -> NO race condition

fi
OpenMP Program to Compute Sum of First n
Natural Numbers
To compute the sum 1 + 2 + 3 + … + n using OpenMP, the work is divided among
multiple threads.
Each thread computes a partial sum of a subset of numbers, and then these partial results are
combined to get the total sum.

We use:

✅ #pragma omp parallel for reduction(+:sum)

• parallel for distributes loop iterations among threads

• reduction(+:sum) ensures each thread keeps a local copy of sum, and nally all
local sums are combined safely

• This avoids race conditions and gives a correct result

Program (Full Marks – 4–5 marks)

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

int main() {
int n, i;
long long sum = 0;

printf("Enter the value of n: ");

scanf("%d", &n);

// Parallel computation of sum

#pragma omp parallel for reduction(+:sum)
for (i = 1; i <= n; i++) {
sum += i;
}

printf("Sum of first %d natural numbers = %lld\n", n,

sum);
return 0;
}
fi
How It Works
1. Threads are created when entering the parallel for region.

2. Each thread computes a partial sum of assigned iterations.

3. reduction(+:sum) ensures:

◦ Each thread has a private copy of sum

◦ After loop completes, OpenMP automatically combines all partial sums using +

4. The master thread prints the nal result.

Sample Output
Enter the value of n: 10
Sum of first 10 natural numbers = 55
fi
Note on Scope of Variables in OpenMP
In serial (normal) programming, the scope of a variable refers to the part of the program where that
variable can be accessed.
For example:

• A variable declared inside a function has function-wide scope

• A variable declared outside any function (global) has le-wide scope

In OpenMP, scope refers to the set of threads that can access a variable inside a parallel region.
OpenMP classi es variables into two major types:

1. Shared Variables
A shared variable is accessible by all threads in the team.

Characteristics

• One memory location is shared by all threads

• All threads can read and write the same variable

• Race conditions may occur if updates are not synchronized

Rules

Variables declared before a parallel block automatically become shared.

Example

In the trapezoidal rule program, variables:

a, b, n, global_result, thread_count

are declared in main() before the parallel directive, so all threads in the team can access them.

This is important because each thread needs the values of a, b, and n when calling the Trap()
function.

2. Private Variables
A private variable is accessible by only one thread.

Characteristics

• Each thread gets its own copy of the variable

fi
fi
 • The value is stored on the thread’s private stack

• Modifying a private variable does not affect other threads

Rules

Variables declared inside a parallel block (including function-local variables called inside parallel
regions) become private.

Example

In the “Hello, World” OpenMP program:

int my_rank, thread_count;

These variables are declared inside the function called within the parallel block.
Therefore each thread gets its own private copy of my_rank and thread_count.

Similarly, in the trapezoidal rule:

global_result_p

is private to each thread, but it points to a shared variable (global_result), so its referenced
value is shared.

Important Observations
1. Shared variables maintain value before and after the parallel block

• At the start of the block, a shared variable has the same value as before

• After the block ends, its value re ects the nal updates done by the threads

2. Some situations must use shared scope

For example:

*global_result_p += my_result;
*global_result_p must be shared, because the nal result must be visible to all threads and
must be available in main after the parallel block.

Otherwise:

• The critical directive would be unnecessary

• The nal result could not be collected correctly

fi
fl
fi
fi
Summary (Write This for Exams)
• Variables declared before a parallel region have shared scope.

• Variables declared inside a parallel region (including inside functions called inside the
region) have private scope.

• Shared variables are visible to all threads, while private variables are visible to only one
thread.

• The value of shared variables is preserved before and after the parallel block, while private
variables exist only during thread execution.

• OpenMP provides clauses (private, shared, firstprivate, lastprivate,

etc.) to override default scoping rules.
Reduction Clause in OpenMP – Explained
The reduction clause in OpenMP is used when multiple threads compute partial results that must
be combined into a single nal result using a reduction operator (such as +, *, -, &, |, ^, &&, ||).
It helps avoid race conditions and eliminates the need for manual critical sections.

Why Reduction is Needed?

Consider the trapezoidal rule example:

Serial version

global_result = Trap(a, b, n);

Parallel version problem

If we try:

global_result += Local_trap(a, b, n);

#pragma omp critical

This is wrong because the entire expression (including the call to Local_trap) becomes
serialized.
Only one thread can execute it at a time, which destroys parallelism and makes the program slower.

To solve this, we need:

• Each thread to compute its result independently

• Combine (reduce) these partial results at the end

This is exactly what the reduction clause does.

How the Reduction Clause Works

Syntax

reduction(<operator> : <variable list>)

Example

global_result = 0.0;

#pragma omp parallel num_threads(thread_count) \

reduction(+: global_result)
fi
 {
global_result += Local_trap(a, b, n);
}

What OpenMP does internally

Creates a private copy of global_result for each thread

Initializes each private copy to the identity value for the operator

For + → 0

For * → 1

For && → 1, etc.

Each thread updates its private variable

At the end of the parallel region, OpenMP automatically performs a critical merge:

global_result = sum(private_result_0, private_result_1, ...);

The nal result is stored in the shared global_result.

This is equivalent to doing:

double my_result = 0.0; // private

my_result += Local_trap(...);

#pragma omp critical

global_result += my_result;

But OpenMP handles it automatically and more ef ciently.

Supported Reduction Operators in C

OpenMP supports the following operators inside a reduction clause:

Operato Identity
r Value
+ 0
* 1
- 0
& ~0
| 0
fi
fi
 ^ 0
&& 1
|| 0

Key Points to Remember

✔ 1. Reduction variables are shared

But each thread has a private copy during execution.

✔ 2. Private copies are initialized using identity values

Example:

• Addition → 0

• Multiplication → 1

✔ 3. Final combination happens after the parallel block

Threads merge their results into the shared variable automatically.

✔ 4. Avoids race conditions

No need for manual locks or critical sections.

✔ 5. Maintains parallelism

Unlike putting the entire operation in a critical block, reduction allows all threads to run the
expensive computation simultaneously.

✔ 6. Floating-point results may differ slightly

Because oating-point addition is not associative, results may vary depending on the number of
threads.

Short Exam-Ready De nition

"In OpenMP, the reduction clause allows multiple threads to compute partial results
independently and automatically combine them into a single shared variable using a reduction
operator. OpenMP creates private copies of the variable, initializes them with identity values,
performs parallel computation, and combines all partial values at the end. It avoids race
conditions and preserves parallel performance."
fl
fi
 1. What is a loop-carried dependence? Explain with an example. OR
Consider the loop a [ 0 ]= 0;
for ( i = 1; i < n ; i ++) a [ i] = a [ i−1] + i ;
There’s clearly a loop-carried dependence, as the value of a[i] can’t be computed without
the value of a[i−1]. Can you see a way to eliminate this dependence and parallelize the
loop?

1. Introduction
In parallel programming, especially with OpenMP, one of the main challenges is identifying
whether a loop can be safely parallelized.
A major factor that prevents parallel execution is loop-carried dependence.
This concept helps decide whether iterations can run independently or must execute in sequence.

2. De nition of Loop-Carried Dependence

A loop-carried dependence exists when:

✔ An iteration of a loop depends on the output of a previous iteration,

✔ So the next iteration cannot start until the previous one completes.

Formally, iteration i depends on iteration j (j < i) if:

The value computed in iteration j is needed by iteration i.

This creates a dependency chain, forcing sequential execution.

3. General Example
sum = 0;
for (i = 1; i <= n; i++)
sum = sum + A[i];
Iteration i uses the updated value of sum from iteration i−1.
Therefore, the loop cannot be parallelized directly.

4. Given Example and Analysis

Given code

a[0] = 0;
for (i = 1; i < n; i++)
a[i] = a[i-1] + i;
fi
Why is there a loop-carried dependence?

To compute a[i], the loop uses:

• a[i - 1] which was produced in the previous iteration.

Thus:

Iteration 1 depends on iteration 0

Iteration 2 depends on iteration 1
Iteration 3 depends on iteration 2
...
This chain forces sequential execution.

5. Diagram Showing Loop-Carried Dependence

Iteration 0: a[0] = 0
↓ (depends)
Iteration 1: a[1] = a[0] + 1
↓
Iteration 2: a[2] = a[1] + 2
↓
Iteration 3: a[3] = a[2] + 3
↓
…

Each iteration requires the result from the previous iteration ➝ Loop-carried dependence exists.

6. Why Can't This Loop Be Parallelized

Directly?
OpenMP executes iterations simultaneously.
But here:

• Thread computing a[3] needs value of a[2]

• Thread computing a[2] needs value of a[1]

• And so on…

If threads run in parallel, some threads will use incorrect or uninitialized values.

Hence, parallelization is unsafe unless the dependence is removed.

7. Eliminating the Dependence (Mathematical
Method)
Let’s expand the loop manually:

a[1] = a[0] + 1 = 1
a[2] = a[1] + 2 = 1 + 2 = 3
a[3] = a[2] + 3 = 1 + 2 + 3 = 6
...
So:

Thus the loop becomes:

for (i = 1; i < n; i++)

a[i] = i * (i + 1) / 2;

Now each a[i] is independent.

8. Parallel Version Using OpenMP

#pragma omp parallel for
for (i = 1; i < n; i++)
a[i] = i * (i + 1) / 2;

Why this works

• Each iteration uses only i

• No shared dependency between iterations

• Safe for parallel execution

9. Summary (Exam-Ready Conclusion)

A loop-carried dependence occurs when an iteration requires the value computed in a previous
iteration.
In the loop:

a[i] = a[i-1] + i;
each iteration depends on the previous one, creating a dependency chain that prevents direct
parallelization in OpenMP.

By recognizing the mathematical pattern:

[
a[i] = \frac{i(i+1)}{2}
]

the loop becomes independent.

The rewritten loop can be ef ciently parallelized.

Thus, removing loop-carried dependencies is essential for exploiting parallelism in OpenMP

programs.
fi
 ⭐ Parallelizing the OpenMP Program for
Estimating π – Detailed Answer
Estimating π using numerical methods is a common example in parallel programming. One widely
used technique is the Midpoint Rule applied to the integral:

This integral can be approximated by dividing the interval ([0,1]) into n sub-intervals and summing
their contributions.

1. Serial Logic of π Estimation

The serial program computes:

step = 1.0 / n;
sum = 0.0;

for (i = 0; i < n; i++) {

x = (i + 0.5) * step;
sum += 4.0 / (1.0 + x*x);
}

pi = step * sum;

Here, each iteration is independent, because the value of sum simply accumulates contributions.

2. Why π Estimation is Easy to Parallelize

The loop is an example of embarrassingly parallel computation:

• No iteration depends on any other (no loop-carried dependencies).

• Each thread can independently compute partial sums.

• Only the nal accumulation needs coordination.

This makes it ideal for OpenMP parallelization.

fi
3. Parallelizing the Loop Using OpenMP
The simplest and most ef cient way to parallelize it is by using:

✔ parallel for

✔ reduction(+:sum)

The reduction clause eliminates the need for manual critical sections.

4. Parallel OpenMP Program to Estimate π

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

int main() {
long long n = 1000000000; // number of intervals
double step = 1.0 / (double)n;
double sum = 0.0;

#pragma omp parallel for reduction(+:sum)

for (long long i = 0; i < n; i++) {
double x = (i + 0.5) * step;
sum += 4.0 / (1.0 + x * x);
}

double pi = step * sum;

printf("Estimated value of π = %f\n", pi);

return 0;
}

5. Explanation of the Parallel Components

(a) #pragma omp parallel for

• Creates a team of threads.

• Divides the loop iterations among available threads.

• Each thread performs its subset independently.

(b) reduction(+:sum)
fi
 • Each thread maintains its own private copy of sum.

• Intermediate results stored locally → avoids race conditions.

• At the end, OpenMP automatically combines partial sums using addition.

This is safer and faster than using critical or manual locks.

6. Why Reduction Clause Is Important

Without reduction:

• Multiple threads write to sum simultaneously → race condition, incorrect results.

• Using a critical section serializes updates → defeats parallelism.

Reduction avoids both problems by:

• Creating private partial sums

• Combining them only once at the end

7. Performance Advantages
Parallelizing π estimation gives:

• Nearly linear speedup for large n.

• Excellent CPU utilization.

• Minimal synchronization overhead.

• Scalable to many cores.

⭐ Scheduling Loops in OpenMP – Explained
In OpenMP, when a loop is parallelized using #pragma omp parallel for, the iterations
of the loop must be divided among multiple threads. The method used to assign these iterations is
called scheduling. Ef cient scheduling is important because it directly affects load balancing,
speedup, and the overall performance of the parallel program.

⭐ 1. Why Scheduling is Needed?

By default, most OpenMP compilers use block (static) partitioning.
Example:
If there are n iterations and t threads, each thread gets approximately n/t iterations.

However, this may be inef cient when:

• Some iterations take more time than others

• Later iterations are more expensive

• Workload per iteration is unpredictable

This imbalance leads to idle threads and poor speedup.

Hence, OpenMP provides different scheduling strategies using the schedule() clause.

⭐ 2. The schedule Clause

General syntax:

schedule(type [, chunk_size])
Where type ∈ {static, dynamic, guided, auto, runtime}
and chunk_size is a positive integer.

⭐ 3. Types of Schedules

A. static
Iterations are divided among threads before the loop starts.

✔ Features:

• Lowest overhead

• Best when all iterations take equal time

fi
fi
 • Uses block or cyclic assignment depending on chunk size

✔ Example:

#pragma omp parallel for schedule(static, 1)

This gives cyclic scheduling (round-robin).

Example assignment for 12 iterations, 3 threads:

schedule(static,1) schedule(static,2) schedule(static,4)

0,3,6,9 0,1,6,7 0-3

1,4,7,10 2,3,8,9 4-7
2,5,8,11 4,5,10,11 8-11

B. dynamic
Iterations are assigned as threads ask for them.

✔ Features:

• Good for unpredictable workloads

• Threads take next chunk after nishing current work

• Slightly more overhead

Example:

#pragma omp parallel for schedule(dynamic, 4)

C. guided
Similar to dynamic, but chunk size starts large and gradually decreases.

✔ Features:

• Designed for workloads where cost decreases/increases steadily

• Ensures load balancing

• Highest overhead among the three

Example:

#pragma omp parallel for schedule(guided)

fi
D. auto
Compiler decides automatically.

schedule(auto)

E. runtime
Schedule is chosen at runtime using environment variable:

export OMP_SCHEDULE=“dynamic,4"

Used when experimenting.

⭐ 4. Comparison Example (Given in Text)

Function f(i) takes time proportional to i.

• Default static schedule → poor load balance

• Using schedule(static,1) → cyclic scheduling

• Speedup improved from 1.33 to 1.99 for 2 threads

This shows that scheduling can dramatically improve performance.

⭐ 5. When to Use Which Schedule?

Situation Best Schedule
All iterations take same time static

Cost increases or decreases gradually static with small chunk size

Unpredictable iteration cost dynamic or guided

Testing multiple schedules runtime
⭐ 6. Example Code Using Schedule Clause
sum = 0.0;

#pragma omp parallel for num_threads(thread_count) \

reduction(+:sum) schedule(static, 1)
for (i = 0; i <= n; i++)
sum += f(i);
Producer–Consumer Problem in OpenMP
(Message Passing Model)
The producer–consumer problem is a classic synchronization problem where producer threads
generate data (messages) and consumer threads process or consume that data. In OpenMP,
producers and consumers can communicate using shared memory, typically by using a queue as
the shared buffer.

A queue supports two operations:

• enqueue() → insert at rear

• dequeue() → remove from front

In parallel programming, multiple threads may try to enqueue or dequeue at the same time, leading
to race conditions, so synchronization is required.

⭐ 1. Concept of Producer–Consumer Using

OpenMP
In OpenMP, a queue can act as a message buffer:

• Producer thread inserts messages into the queue

• Consumer thread removes messages

Since multiple threads may access the queue at once, enqueueing and dequeueing must be carefully
synchronized.

⭐ 2. Message Passing with Queues in

OpenMP
Each thread has:

• A message queue

• Two counters:

◦ enqueued → number of messages added

◦ dequeued → number of messages removed

Message passing works like this:

1. A thread creates a message

2. It chooses a random destination thread

3. It enqueues the message in that thread’s queue

4. Periodically, each thread checks its own queue to receive messages

⭐ 3. Pseudocode for Message Passing

✅ Sending messages (Producer behavior)

void Send_msg() {
mesg = random();
dest = random() % thread_count;

#pragma omp critical

Enqueue(queue[dest], my_rank, mesg);
}
Explanation:

• Enqueueing must be protected with critical because it updates shared data like the rear
pointer of the queue.

• Without protection, two threads updating the queue at the same time may cause lost
messages → race condition.

⭐ Receiving messages (Consumer behavior)

void Try_receive() {
queue_size = enqueued - dequeued;

if (queue_size == 0)
return;

else if (queue_size == 1)
#pragma omp critical
Dequeue(queue[my_rank], &src, &mesg);

else
Dequeue(queue[my_rank], &src, &mesg);

Print_message(src, mesg);
}
Logic:

• If there's only 1 message, a con ict may occur between enqueue and dequeue → use
critical

• If 2 or more messages, dequeue is safe without synchronization because only the owner
removes messages.

⭐ 4. Termination Detection (Done Function)

bool Done() {
queue_size = enqueued - dequeued;

if (queue_size == 0 && done_sending == thread_count)

return TRUE;
else
return FALSE;
}
Each thread increments done_sending when it nishes sending.

⭐ 5. Use of atomic in Producer–Consumer

The statement:

#pragma omp atomic

done_sending++;
is used instead of critical because:

✔ atomic protects only a single memory update

✔ Faster than critical

✔ Uses hardware-level atomic instructions
✔ Guarantees that only one thread updates the variable at a time

What atomic protects:

• The read–modify–write of the variable done_sending

What it does NOT protect:

• Any other operations inside an expression

• It works only on statements of the form:

fl
fi
x++; ++x;
x--; --x;
x op= expr;
Hence atomic is ideal for simple counters.

⭐ 6. Diagram: Producer–Consumer with

Queues in OpenMP
┌──────────────────────────────┐
│ Shared Message Queues │
├──────────────────────────────┤
Thread 0 →│ Queue[0]: msgs from others │
Thread 1 →│ Queue[1]: msgs from others │
Thread 2 →│ Queue[2]: msgs from others │
└──────────────────────────────┘
▲ ▲
│ │
Producers send Consumers receive
using from own queue
#pragma omp critical

⭐ 7. Why Synchronization is Needed?

✔ Race conditions occur when:

• Two producers try to enqueue simultaneously

• A producer enqueues while a consumer dequeues from a nearly empty queue

✔ critical solves:

• Complex updates like manipulating queue pointers (front/rear)

✔ atomic solves:

• Simple updates like incrementing counters such as done_sending

Without these, the program may:

• Lose messages

• Crash

• Produce inconsistent queue states

⭐ FINAL EXAM-READY SUMMARY
The producer–consumer problem in OpenMP is implemented using shared message queues.
Producers generate messages and place them in queues, while consumers remove messages. Queue
operations like enqueue must be synchronized using the critical directive to avoid race
conditions. Counters such as done_sending can be updated using atomic, which provides
faster hardware-supported synchronization for single-step updates. Message passing is implemented
by each thread alternately sending and receiving messages using Send_msg() and
Try_receive() functions. Proper synchronization ensures that no message is lost and that all
threads terminate correctly.
 2. Write the OpenMP parallel code for matrix–vector multiplication and explain the purpose
of each OpenMP clause ---------------(CACHE COHERENCE)

OpenMP Parallel Matrix–Vector

Multiplication (with Clause Explanation)
OpenMP Code

#include <omp.h>

void mat_vec(double **A, double *x, double *y, int m, int n,

int thread_count) {

int i, j;

#pragma omp parallel for num_threads(thread_count) \

default(none) private(i, j) shared(A, x, y, m, n)
for (i = 0; i < m; i++) {
y[i] = 0.0;

for (j = 0; j < n; j++) {

y[i] += A[i][j] * x[j];
}
}
}

✔ Explanation of Each OpenMP Clause

1. #pragma omp parallel for

• Parallelizes the outer loop.

• Each iteration i (each row of the matrix) is independent → safe to split across threads.

• No loop-carried dependency → perfect for OpenMP.

2. num_threads(thread_count)

• Speci es exact number of threads to use.

• Useful for performance tuning and experiments.

3. default(none)
fi
 • Enforces explicit listing of all shared and private variables.

• Avoids accidental shared variables → prevents race conditions.

• Makes the code safer and more readable.

4. private(i, j)

• Each thread gets its own copy of loop index variables.

• Prevents threads from overwriting each other’s loop counters.

5. shared(A, x, y, m, n)

• These variables are common across all threads.

• A and x are read-only → safe as shared.

• y is shared but each thread writes a different element (y[i]), so no true data race.

✔ CACHE COHERENCE, FALSE SHARING

& PERFORMANCE ISSUES (8-mark theory)
1. Why cache matters

• CPU operations are fast; accessing main memory is slow.

• So processors keep copies of data in cache lines (typ. 64 bytes).

• If a thread updates a variable inside a cache line, that entire line becomes invalid in other
threads’ caches → must be reloaded.

This is cache coherence.

2. What is false sharing?

False sharing occurs when:

• Two threads write to different variables

• BUT the variables lie in the same cache line

Example:
Thread 0 updates y[0]
Thread 1 updates y[1]

If y[0] and y[1] are inside the same 64–byte cache line → each update invalidates the other’s
cache line → constant reloading.

Even though threads are NOT sharing actual data, their cache lines are shared ⇒ performance
collapses.

3. Why false sharing occurs in matrix–vector

multiplication
Case: A = 8 × 8,000,000

• Vector y has 8 elements.

• All y[0] … y[7] may lie in one cache line.

• With 4 threads:

◦ Thread 0 updates y[0]

◦ Thread 1 updates y[1]

◦ Thread 2 updates y[2]

◦ Thread 3 updates y[3]

• Every write invalidates EVERY other thread’s cache line version.

🔴 Massive false sharing → very low ef ciency.

4. Why performance is better in 8000 × 8000

and 8,000,000 × 8
• In these matrices, y has many elements.

• Each thread works on a large contiguous block of y.

• Edge overlap between thread regions is small (only at boundaries).

• False sharing is negligible.

fi
5. Solutions to avoid false sharing
✔ Method 1: Padding

Add dummy elements so each y[i] lies in its own cache line.

Example:

double y[m][8]; // padded to 64 bytes (8 doubles)

✔ Method 2: Private accumulation

Each thread computes a private temporary vector and updates shared y later.

double my_y = 0;
Write to the shared vector only once after nishing the row.
fi
Below is the complete 8-mark exam-ready answer + a thread-safe OpenMP tokenizer program
using strtok_r.

Thread Safety in OpenMP — 8-mark Answer

Thread safety refers to the ability of a block of code or a function to be executed simultaneously by
multiple threads without causing incorrect behavior, race conditions, or data corruption. In
shared-memory parallel programming (such as OpenMP), multiple threads often access shared
variables or call library functions. If these operations are not carefully controlled, the results can
become unpredictable.

In OpenMP, thread safety can be ensured through several mechanisms:

1. Avoiding Shared Global State

Functions like strtok, rand, and localtime internally use static variables, causing shared
state among threads. Calling them simultaneously corrupts data. A thread-safe alternative
(strtok_r, rand_r, etc.) must be used, which stores state in per-thread private variables.

2. Using OpenMP Clauses

• private(var) → Every thread gets its own copy.

• firstprivate(var) → Private copy but initialized with parent value.

• shared(var) → All threads access the same variable (must be used carefully).

• reduction(op: var) → Safe accumulation without race conditions.

3. Using Synchronization Constructs

• #pragma omp critical — Only one thread executes the block at a time.

• #pragma omp atomic — Safer for single memory updates.

• #pragma omp barrier — Ensures threads reach a point before continuing.

• Mutexes/locks: omp_set_lock(), omp_unset_lock().

4. Using Thread-Safe Library Functions

Prefer re-entrant APIs like:

• strtok_r instead of strtok

• rand_r instead of rand

• localtime_r instead of localtime

5. Avoiding False Sharing

Ensure each thread writes to different cache lines or uses padding to prevent slowdowns due to
cache invalidation.

✅ Thread-Safe Multi-Threaded Tokenizer in

OpenMP (Using strtok_r)
This is the corrected version of Program 5.7 from the textbook.

✔ Thread-safe tokenizer using strtok_r:

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

void Tokenize(char *lines[], int line_count, int

thread_count) {
int i, j, my_rank;
char *my_token;
char *saveptr; // Thread-private pointer for strtok_r

#pragma omp parallel num_threads(thread_count) \

default(none) private(i, j, my_rank, my_token,
saveptr) \
shared(lines, line_count)
{
my_rank = omp_get_thread_num();

#pragma omp for schedule(static, 1)

for (i = 0; i < line_count; i++) {
printf("Thread %d > line %d = %s\n", my_rank, i,
lines[i]);

j = 0;

// FIRST call: pass the line

my_token = strtok_r(lines[i], " \t\n", &saveptr);

// SUBSEQUENT calls: pass NULL

while (my_token != NULL) {
printf("Thread %d > token %d = %s\n",
my_rank, j, my_token);
 my_token = strtok_r(NULL, " \t\n", &saveptr);
j++;
}
}
}
}

int main() {
char line0[] = "Pease porridge hot.";
char line1[] = "Pease porridge cold.";
char line2[] = "Pease porridge in the pot";
char line3[] = "Nine days old.";

char *lines[] = {line0, line1, line2, line3};

int line_count = 4;

Tokenize(lines, line_count, 2);

return 0;
}

✅ Why this Program Is Thread-Safe

1. strtok_r uses a per-thread save pointer (saveptr), avoiding shared static memory.

2. saveptr, my_token, i, j are declared private, so each thread has its own copy.

3. lines and line_count are shared (safe because each thread processes different lines).

4. The schedule(static,1) distributes exactly one line per thread in a round-robin

manner.
Parallelizing the Trapezoidal Rule Using
OpenMP – Explained
The trapezoidal rule is a numerical integration technique that estimates the area under a curve by
dividing the interval ([a,b]) into n subintervals and approximating the area using trapezoids.
The serial algorithm computes:

Parallelization Idea (Using OpenMP)

To speed up this computation, we break the work among multiple threads.
Following Foster’s design methodology:

1. Decomposition

Two main tasks:

• Compute the local sum of trapezoids assigned to each thread.

• Add local sums to obtain the nal global result.

2. Assigning Work

We divide the total number of trapezoids (n) equally among threads:

Each thread gets its own subinterval:

• Thread 0: ([a, a+local_n \cdot h])

• Thread 1: ([a+local_n h, a+2 local_n h])

• …

• Thread t: starts at (a + t \cdot local_n h)

Each thread applies the serial trapezoidal logic on its own interval.
fi
3. Combining Results

All threads compute a private partial sum.

Finally, they update the shared global_result:

#pragma omp critical

global_result += my_result;
A critical section is required because simultaneous updates create a race condition. Only one
thread should update the shared variable at a time.

Parallel OpenMP Program (Trapezoidal Rule)

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

double f(double x) {
return x*x; // Example function f(x) = x^2
}

int main() {
double a, b, h, global_result = 0.0;
int n, i, thread_count;

printf("Enter a, b and n:\n");

scanf("%lf %lf %d", &a, &b, &n);

thread_count = 4; // Example: 4 threads

h = (b - a) / n;

#pragma omp parallel num_threads(thread_count)

{
int my_rank = omp_get_thread_num();
int local_n = n / thread_count;

double local_a = a + my_rank * local_n * h;

double local_b = local_a + local_n * h;
double x, my_result = (f(local_a) + f(local_b)) /
2.0;

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

x = local_a + i * h;
my_result += f(x);
 }

my_result *= h;

#pragma omp critical

global_result += my_result;
}

printf("Estimated integral = %.14f\n", global_result);

return 0;
}

How OpenMP Parallelization Works

✔ parallel directive

Creates a team of threads.

✔ Each thread computes a local sum

Independent, no data con ict.

✔ critical section

Ensures safe update of the global result.

✔ Reduced execution time

As the workload is divided among threads.

fl