Parallel Prog

CSE 4211 – Parallel and Distri

Md. Nasif Osman K

Assistant Profe
Dept. of CSE, R
 A Paradigm S

❑ To make it clear that sequential and paralle

alternative algorithms for finding the sum of
❑ This example is sufficiently simple that
identify it and generate a more parallel soluti
simple illustration of the conceptual differe
and a parallel solution.
❑ To begin, we assume that the sequence has n

and that these have been stored in an arr

 A Paradigm S

❑ Iterative Sum: Perhaps the most intuitive so

it sum, to 0 and then iteratively add the e
computation is typically programmed usin
reference the elements of the sequence.

❑ Addition over the real numbers is an associative

commutative operation, implying that its values n
not be summed in the order specified, least index
greatest index.
 A Paradigm S

❑ Pair-Wise Summation: More parallel order

pairs of data values yielding the intermediate

which are added in pairs,

yielding more intermediate sums, which are themse

added in pairs, and so on.
❑ This solution can be visualized as inducing a tree
the computation, where,
✓ the original data values are leaves,
✓ the intermediate nodes are the sum of the no
below them, and
✓ the root is the overall sum
 A Paradigm S

❑ Parallel Prefix Sum: A closely related op

sum, commonly called a scan in many pa
begins with the same sequence of n values,

but the desired computation is the sequence

such that each 𝑦𝑖 is the sum of the first i elem

 A Paradigm S

❑ Parallel Prefix Sum:

❖ The summation by pairs approach can
values.
❖ Each leaf processor storing 𝑥𝑖 ; could co
the sum of all elements to its left, tha
summing by pairs, we know the sum of al
❖ And if we save that information, we c
directly summing them.
❖ To do so, we start at the root, whose pref
before the elements of the sequence—is
subtree.
❖ The total for its left subtree is the prefix
 A Paradigm S
❑ Parallel Prefix Sum:
❖ Applying this idea inductively, we get the f
▪ Compute the grand total at the root by pair-wise
▪ On completion, imagine the root receiving a 0 fro
▪ All non-leaf nodes receive a value from
their parent, relay that value to their left
child, and send their right child the sum
of the parent’s value and their left child’s
value that was computed on the way up;
these are the prefixes of their child
nodes.
▪ Leaves add the prefix value from above
and the saved input.
❖ The values moving down the tree are
the prefixes for the child nodes.
 A Paradigm S
❑ Parallel Prefix Sum: The computation
computation.
✓ It requires an up sweep and a down swe
each level in a sweep can be performed
✓ At most two add operations are
required at each node, one going
up and one coming down, plus the
routing logic.
✓ Thus, the parallel prefix also has
logarithmic time complexity.
✓ We organized the parallel
algorithms to change the order of
the computation.
 A Paradigm S

❑ Sequential Prefix Sum:

Pros
1. Simple and intuitive: Just one loop, 1. No
Easy to write, debug, and verify. on th
core
2. Low overhead: No threads, no 2. Slo
synchronization. No extra memory 𝑂 𝑛
structures (like trees).
3. Cache-friendly: Linear memory
access → very efficient on CPUs.
4. Works best for small inputs
 A Paradigm S
❑ Parallel Prefix Sum:
Pros
1. Much faster: Time = 𝑂 log 𝑛 ; Huge 1. Mo
speedup for large 𝑛. down
(cores
2. Exploits modern hardware: Works well 2. Ov
on - Multi-core CPUs and GPUs. Synch
Comm
3. Scalable: Performance improves with 3. No
more processors . small
domin
4. Enables other parallel algorithms: 4. Me
Parallel sorting, Graph algorithms, Data reduc
compaction. seque
 Parallelism Using Multiple I

❑ A thread, or thread of execution, is a unit of

❑ A thread has everything needed to execute
program text, a call stack, and a program
memory with other threads.
❑ Thus, multiple threads can cooperate to com
❑ For example,

The loop index i would be local to the call sta

array x would be shared. By assigning each th
values, multiple threads can work on the prob
parallelism.
 Parallelism Using Multiple I

❑ A Multithreaded Solution to Counting

concrete, let’s assume that we will execute
computer with eight processors (P0 to P7).
❑ Each processor has a
private L1 cache; it
shares an L2 cache with
its “chip-mate" and
shares an L3 cache with
the other processors.
❑A cache is fast
(compared to the RAM)
memory for storing
instructions and data
while a program runs.
 Parallelism Using Multiple I

❑ The serial code to count the number of 3s fo

 Parallelism Using Multiple I

❑ Try 1:
➢ We will use a threads programming mod
a dedicated processor, and the threads
through shared memory (including the cac
➢ Thus, each thread has its own process s
and file state.
➢ To implement a parallel version of the p
array so that each thread is responsible fo
of the array, where t is the number of thre
➢ Assume, t = 4 threads and length = 16.
 Parallelism Using Multiple I

❑ Try 1: We can implement this logic with t

takes two arguments—the name of a functi
identifies the thread’s ID—and spawns a
function with the thread ID as a parameter.
 Parallelism Using Multiple I

❑ Try 1: When you call thread_create()

▪ A new thread is created
▪ It begins executing a specified func
▪ It runs in parallel (or interleaved) w
▪ Both threads share the same:
✓ Memory
✓ variables (unless protected)

❖ Unfortunately, this seemingly st

produce the correct answer because
statement that increments the value o
 Parallelism Using Multiple I
❑ Try 1:
➢ A race condition exists when the result of an ex
more events.
➢ In this case, the problem arises because the sta
implemented on modern machines as a series of
▪ Load count into a register
▪ Increment count
▪ Store count back into memory

➢ When two threads execute the count3s_thread()

code, these instructions might be interleaved.
➢ The result of the interleaved executions is that
count is 1 rather than 2.
➢ Many other interleavings are possible, some
yielding correct results and others yielding
incorrect results
➢ The fundamental problem: Increment of count is
not an atomic operation, that is, it is
interruptible.
 Parallelism Using Multiple I
❑ Try 2:
❑ We can solve the previous problem by using a m
❑ A mutex is an object that has two states—lock
lock() and unlock ().
❑ The implementation of these methods ensures
mutex, it checks to see if it is locked or unlocke
is in an unlocked state before locking it.
❑ By using a mutex to protect code that we wish
as a critical section—we guarantee that only one

❑ Mutual exclusion and atomicity are related

transformation.
❑ Mutual exclusion: A piece of code executes wi
can execute that code at any time.
❑ Atomicity: The term atomicity comes from t
operations is atomic if either they all execute or
see the results of a partial execution.
 Parallelism Using Multiple I
❑ Try 2:
➢ For the Count 3s problem, we simply lock a m
unlock the mutex after incrementing count.
 Parallelism Using Multiple I
❑ Try 2:
➢With one thread, execution time is more than f
code, so the overhead of using the mutexes is dra
➢ When we use two threads, each running on its
worse than with just one thread.
 Parallelism Using Multiple I
❑ Try 3: Instead of
accessing a critical section
every time count must be
incremented, we can
instead accumulate the
local contribution to the
over all count in a private
variable, private_count,
and only access the critical
section for updating count
once per thread.
 Parallelism Using Multiple I
❑ Try 3:
➢ In exchange for a tiny
amount of extra memory, our
resulting program now
executes considerably faster.

➢ Still there is a performance

degradation problem which is
difficult to identify by simply
inspecting the source code. It
is related to the underlying
hardware behavior.
 Parallelism Using Multiple I
❑ Try 3:
➢ Our hardware uses a protocol to maintain
that both processors “see” the same memo
➢ If processor 0 modifies a value at a giv
will invalidate any cached copy of tha
processor 1’s L1 cache, thereby prevent
accessing a stale value of the data.
➢ This cache coherence protocol becomes
repeatedly modifying the same data, beca
between the two caches.
 Parallelism Using Multiple I
❑ Try 4:
➢ The unit of cache coherence is known as a cach
size is 64 bytes.
➢ Although the threads on processors P0 and
private_count [0] or private_count[1], the unde
64 bytes cache line.
➢ A modification of any part of a cache
line is equivalent to a modification of the
entire line, so this shared cache line
bounces between the caches as
private_count [0] and private_count[1]
are repeatedly updated.
➢ This phenomenon in which logically
distinct data shares a physical cache line
is known as false sharing.
 Parallelism Using Multiple I
❑ Try 4:
➢ To eliminate false sharing,
we can pad our array of
private counters so that
each resides on a distinct
cache line.

➢ With this padding, this

solution removes both the
overhead and contention of
using mutexes, and we
have largely achieved
success.
 Parallelism Using Multiple I
❑ Try 4:
➢ Our parallel solution running
on one thread is almost as fast
as the serial execution, the
execution time of the parallel
program is close to twice as
fast when there are two
threads, and it is almost four
times as fast when there are
four threads.
➢ With eight threads no
considerable improvement
due to certain hardware
behavior.
❑ POSIX (Portable Operating System Interface): POSIX is
systems.
❖ It provides:
▪ File operations (open, read, write)
▪ Process control (fork, exec)
▪ Threading via POSIX threads (pthreads)
❖ Why it's an interface?
▪ POSIX defines:
o Function names
o Expected behavior
❑ OpenMP (Open Multi-Processing): OpenMP is an interface
❖ It provides:
▪ Compiler directives (like #pragma omp parallel)
▪ Runtime library functions
▪ Environment variables
❖ Why it's an interface?
▪ It defines:
o How you express parallelism
❑MPI (Message Passing Interface): MPI is an inte
computing.
❖ It provides:
▪ Functions for communication between processes
▪ Send/receive messages across machines or nodes
❖ Why it's an interface?
▪ MPI defines:
o Function calls like MPI_Send, MPI_Recv

❑ They’re called interfaces because they define how

how the work is actually done internally.
❑ Think of them as agreed-upon “contracts” between
❑ POSIX is an interface between applications and th
❑ OpenMP is an interface between the code and the
❑ MPI is an interface between parallel processes acr
 Introduction to O
❑ OpenMP (Open Multi-Processing) is an A
parallel programming in languages like C,
❑ It allows developers to write programs
simultaneously using a simple set of compil
environment variables.
❑ History:
o 1997: OpenMP was first introduced by the OpenMP
including companies like Intel, IBM, and others.
o Late 1990s–2000s: Early versions focused on basic p
o 2005+ (OpenMP 2.5 → 3.0): Added task-based paral
o 2013 (OpenMP 4.0): Introduced support for accelerat
o 2018–2021 (OpenMP 5.x): Improved memory m
performance portability.

❑ OpenMP has evolved to remain relevant alo

heterogeneous systems.
 Introduction to O
❑ OpenMP is widely supported across pl

Languages
Compilers
✓C ✓ GCC (GNU
✓C++ Compiler Collection)
✓ Clang/LLVM
Pla
✓Fortran ✓ Intel oneAPI ✓ Lin
compilers ✓ Win
✓ Microsoft Visual ✓ ma
C++ (partial support) (lim
by
 Why Use Open
❑ Easy to learn (directive-based)
❑ Portable across platforms
❑ Scales with available CPU cores
❑ Reduces development time compared to ma

Application
❑ Scientific Computing: Simulations (physics, ch
methods and matrix computations
❑ Engineering: Finite element analysis (FEA) ; Com
❑ Data Processing: Large-scale data analysis; Paralle
❑ Machine Learning & AI: Speeding up training and
❑ Image & Signal Processing: Video encoding/decod
 What OpenMP
❑ At its core, OpenMP helps you paralle
that can run concurrently. Instead of m
add directives like:
#pragma omp <spe
❑ The compiler and runtime handle thre
and workload distribution.
❑ An OpenMP-compliant compiler will
generate appropriate multithreaded cod
❑ Compilers that don’t accept OpenMP
yielding standard sequential execution.
 OpenMP Prag
❑ OpenMP provides several directives (pra
split across threads.
1. parallel — Create Threads: This is the ba
threads. Example
#pragma omp parallel [clause...] #pragma
{ {
// parallel code printf("
} }

➢ The master thread creates multiple worker th

➢ Each thread executes the same code blo
Multiple Data).
➢ At the end, threads join back
Important Clauses:
▪ num_threads(n) → specify number of threads
▪ private(var) → each thread gets its own copy
▪ shared(var) → all threads share the variable
 OpenMP Prag
2. parallel for — Parallelize Loops: Distr
threads in a team. Examp
#pragm
#pragma omp parallel for [clause...] for (int
for (initialization; condition; increment) {} print
}

➢ Loop iterations are divided among thread

➢ Each iteration must be independent (no d
Scheduling Types:
▪ static → equal chunks (fast, low overhead
▪ dynamic → assigned at runtime (better lo
▪ guided → decreasing chunk size over tim
For example,
#pragma omp parallel for s
 OpenMP Prag
3. reduction — Combine Results Safely: H
multiple threads update a shared variable
reduction(operator:variable)
➢ Each thread gets a private copy of the va
➢ Performs computation independently
➢ All results are combined at the end
Example:
Supported Operators: int sum = 0
▪ Arithmetic: +, *, -
#pragma om
▪ Logical: &&, || for (int i =
▪ Bitwise: &, |, ^ sum += i
▪ Others: min, max }

❑ Without reduction → race condition

 OpenMP Prag
4. sections — Task Parallelism: Divides w
sections, each executed by a separate thr
#pragma omp parallel sections Example:
{ #pragma om
#pragma omp section {
{ /* task 1 */ } #pragma
printf("C
#pragma omp section
{ /* task 2 */ } #pragma
} printf("C
}

➢ Each section is assigned to one thread.

➢ Good for different tasks, not loop splittin
➢ Number of sections ≠ number of threads
➢ Threads may remain idle if sections are f
 OpenMP Prag
5. single : Ensures only one thread execu

#pragma omp single

{
printf("Executed once\n");
}

Use Case:
▪ Initialization
▪ File I/O
▪ Printing results

❖ master : Ensures only thread 0 executes a b

 OpenMP Prag
6. critical — Mutual Exclusion: Only one
at a time.
#pragma omp critical
{
sum += value;
}

Use Case:
▪ Protect shared resources
▪ Avoid race conditions

Drawback: Slows down performance (ser

 OpenMP Prag
7. atomic : A lighter alternative to critical f

#pragma omp atomic

sum++;

Use Case:
▪ Faster
▪ Limited to simple expressions

8. barrier: Synchronizes all threads.

#pragma omp barrier

❖ All threads must reach the barrier before

 OpenMP Prag
❑ Data Scoping Clauses control how v
regions:
Clause Meaning
private Each thread has
shared One shared varia
firstprivate Private copy init
lastprivate Keeps value from

Example:
#pragma omp parallel private(x) shared
 OpenMP Prag
❑ Exercise: Determine the output of the
❑ a → shared
▪ One single shared variable i
▪ All threads update the same a i
▪ Race condition (no synchronization) i
❑ b → firstprivate #
▪ Each thread gets its own copy of b
▪ Initialized to 2 f
▪ Changes are local only
▪ Final b outside loop remains 2
❑ c → private + lastprivate
▪ Each thread has its own c
▪ During loop: private values used
▪ After loop: value from logically last iteration (i = 3) is
copied back
Inside Loop Output: Outside Loop Output: }
02 13 p
3
1 3 Or 0 2 Or Many others 2
p
24 3 5 p
<undefined value>
35 24
 OpenMP Exam
❑ Example: Summation
#pragma omp parallel for: #include <o
➢ Two directives combined: #include <st
▪ parallel → creates a team of threads
▪ for → divides loop iterations among those int main() {
threads int sum =
reduction(+:sum):
➢ If multiple threads do: sum += i; they may #pragma
overwrite each other → incorrect result. for (int i =
➢ What reduction does: sum +=
▪ Each thread gets its own private copy of }
sum
▪ Each thread computes partial results printf("Su
▪ At the end → all partial sums are combined return 0;
using + }
Exam
schedule(static): controls how loop iterations are Threa
assigned to threads. Threa
▪ Iterations are divided equally at compile/start time. Lo
▪ Each thread gets a fixed chunks. Be
 OpenMP Exam
❑ Example: Counting 3s in an array
int count3s(int array[], int length)
{
int i, count, count_p;
count = 0;
#pragma omp parallel shared(array, count, length) private(count_p)
{
count_p = 0;
#pragma omp for private(i)
for (i = 0; i < length; i++)
{
if (array[i] == 3)
{
count_p++;
}
}
 OpenMP Exam
❑ Example: Counting 3s in an array

➢ #pragma omp parallel shared(array, count, length)

▪ Creates multiple threads
▪ array, length, count → shared
▪ count_p → private per thread

▪ Local Counter: count_p = 0 → Each thread ini

conditions during counting.
➢ #pragma omp parallel for private(i) :
▪ Divides loop iterations among threads
▪ Each thread processes part of the array.
▪ i → private per thread

➢ #pragma omp critical:

▪ Ensures only one thread updates count at a time
▪ Avoids race condition
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
visited[N] = {false}
queue Q ✓
✓
visited[source] = true
enqueue(Q, source)
✓

while (Q not empty) {

u = dequeue(Q) M
B
for each v in adj[u] {
q
if (visited[v] == false) {
visited[v] = true F
enqueue(Q, v)
}
n
} b
}
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
S ❑
/ \
A B
/ \ / \
C D E F

BFS Order: S → A, B → C, D, E, F
❑
❑ A queue in BFS ensures level order
traversal, meaning:
✓ All nodes at distance 1 from the source ❑
are processed before distance 2
✓ All nodes at distance 2 are processed
before distance 3, and so on
❑ The queue enforces this rule: Don’t move to the next lev
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
❖ Instead of thinking, Process ONE node →
❖ Think: Process ALL nodes at current leve
❖ Rewriting the sequential BFS (level-wise):
Queue (Sequential
Aspect Frontier (Parallel BF
BFS)
Structure FIFO (first-in-first-out) Unordered set/list
Processing
One node at a time Many nodes at once
style
Dynamic (while queue
Control flow Level-by-level (bulk proces
not empty)
Ordering Strict order maintained Order doesn’t matter within
Synchronizat
Minimal Required
ion
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
❖ Nodes in the same frontier:
✓ Are independent
✓ No ordering dependency
✓ Can be processed in parallel

for (i = 0; i < [Link]; i++) {

u = frontier[i]

for each v in adj[u] {

if (visited[v] == false) {
// synchronization needed here
}
}
}
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm

for (i = 0; i < [Link]; i++) {

❖ Multip
▪ Di
u = frontier[i]
▪ Try
for each v in adj[u] { o
if (visited[v] == false) { o
// synchronization needed here
}
} ✓ That’s
}
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
❖ Problem Setup:
// Graph: adjacency list
adj[N]

// BFS data
visited[N] = {false
frontier[]
next_frontier[]
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
❖ Try 1: Every time a thread finds a new node → it
visited[source] = true
2
#pragma omp parallel for
1 frontier = {source}
for (i = 0; i < [Link]; i+
while (frontier not empty) {
u = frontier[i]
next_size = 0
for each v in adj[u] {

} if (visited[v] == false) {
3 }
}
#pragma omp critical
} {
} if (visited[v] == fal
visited[v] = true
frontier = next_frontier next_frontier[ne
} next_size++
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
❖ Try 2: Avoid full lock; Use atomic to safely grab
visited[source] = true
2
#pragma omp parallel for
1 frontier = {source}
for (i = 0; i < [Link]; i++)
while (frontier not empty) { u = frontier[i]
for each v in adj[u] {
next_size = 0
if (visited[v] == false) {
// try to mark visited saf
bool was_visited
❑ Better but still contention #pragma omp atomic ca
on: {
o visited[v] was_visited = visite
o next_size visited[v] = true
❖ Locking reduced, but }
didn’t eliminate contention if (was_visited == false
int pos
 OpenMP Exam
❑ Example: Classic BFS Traversal Algorithm
❖ Try 3: Use local buffers + critical outside; Eac
results once per thread (not per edge)
3
for each v in adj[u] {
1 visited[source] = true
frontier = {source} if (visited[v] == false
// try to mark visited
while (frontier not empty) { bool was_visited
#pragma omp atom
next_size = 0 {
was_visited =
2 }
visited[v] = tr

#pragma omp parallel if (was_visited ==

{ local_buffer[local_
local_buffer[] // thread-local local_size++
local_size = 0 }
#pragma omp for }
for (i = 0; i < [Link]; i++) { }
u = frontier[i] }
 OpenMP Exam
❑ Example: Classic DFS Traversal Algorithm
❖ DFS goes as deep as possible before backtra
visited[N] = {false}
Creates a dependency c
DFS(u)
{
visited[u] = true ❖DFS is inherently les
print(u) traversal depends on
for each v in adj[u] ❖ But there is scope fo
{
if (visited[v] == false) ❖ Suppose, node 1 co
{
DFS(v) does DFS(2), then
}
} conceptually, Subtre
} independent after dis
 OpenMP Exam
❑ Example: Classic DFS Traversal Algorithm
❖ Let’s create a task-based model for:
➢ recursive tasks
visited[N] = {f
➢ dynamic work creation
➢ controlled synchronization ParallelDFS(u)
{
# visited[u] =
print(u)
Inside the main() function, do:
for each v in
{
#pragma omp parallel bool was_
{
#pragma omp single #pragma o
{ {
ParallelDFS(source) was_vi
} visited[
} }
 OpenMP Exam
❑ Example: Classic DFS Traversal Algorithm
❖ Why to use #pragma omp single ?
➢ Without this, ALL threads would call Parall
disaster.
❖ Why task is needed?
➢ Tasks allow that thread creates work dynamicall
➢ DFS recursion structure is dynamic, so: parallel
❖ Why atomic capture is needed?
#pragma omp atomic capture
{
was_visited = visited[v]
visited[v] = true
}

➢ It ensures only ONE thread owns a shared or co

 OpenMP Exam
❑ Example: Classic DFS Traversal Algorithm
❖ Consider the following graph/tree:
1
/ | \ ❖ Suppose, adjacency order is: 2 →
2 3 4 ❖ Sequential node visit order: 1 →
/ \ \ ❖ Only ONE active execution path
5 6 7
❑ Parallel:
▪ Step 1: Start at node 1
o Thread T1 executes: ParallelDFS(1) and it sees childr
o Tasks are created.
▪ Step 2: Suppose we have 3 threads. Runtime thread distrib
time snapshot 1: Thread Work/Task
T1 DFS(2)
T2 DFS(3)
T3 DFS(4)
 OpenMP Exam
❑ Example: Classic DFS Traversal Algorithm
❖ Consider the following graph/tree:
1 ❖ Now, subtrees are explored i
/ | \ ❖ No thread waits for DFS ord
2 3 4 ❖ At time snapshot 2:
/ \ \ o T1 is exploring subtree o
5 6 7 2 → {5,6}
✓ T1 creates new tasks
o T2 is exploring subtree o
quickly.
o T3 exploring subtree of 4
4 → {7}
✓ T3 creates: DFS(7).
▪ Step 3: Now T2 became idle. So, runtime may
Dynamic Work Stealin
 OpenMP Exam
❑ Example: Classic DFS Traversal Algorithm
❖ Consider the following graph/tree:
1 ❖ The traversal order is now N
/ | \ ❖ Possible outputs: 1 2 3 4 5 6
2 3 4 ❖ Key difference: Sequential
/ \ \ but Parallel DFS guarantees
5 6 7 order.

❑ Parallel DFS is often harder to optimize because

▪ recursion depth varies
▪ task creation overhead exists
▪ branch sizes are unpredictable
❑ Sometimes, parallel DFS becomes slower than s
trees.
 OpenMP Exam
❑ Example: Classic Bubble Sort Algorithm [S
❖ Repeatedly:
▪ compare adjacent elements
▪ swap if out of order
❖ Largest element “bubbles” to the end each p
❖ Bubble Sort is naturally sequential because
next comparison immediately.
❖ If someone writes: #pragma omp parallel for
for (j = 0; j < n-1; j++)
{
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}

❖ It will lead to a disaster due to a race condit

corrupted sorting.
 OpenMP Exam
❑ Example: Classic Bubble Sort Algorithm [P
❖ Parallelize NON-overlapping comparison
❖ Odd-Even Transposition: Works in two pha
❖ Create adjacent pairs of elements from the O
Index: 0 1 2 3 4
EVEN 5 2 4 3 7

ODD 2 5 3 4 6

EVEN 2 3 5 4 6

ODD 2 3 4 5 6

EVEN 2 3 4 5 6

ODD 2 3 4 5 6
 OpenMP Exam
❑ Example: Classic Bubble Sort Algorithm [P
1
for (phase = 0; phase < n; phase++) 2
{
if (phase % 2 == 0) else
{ {
// even phase // odd phase
#pragma omp parallel for #pragma omp parallel f
for (i = 0; i < n-1; i += 2) for (i = 1; i < n-1; i +=
{ {
if (A[i] > A[i+1]) if (A[i] > A[i+1])
{ {
swap(A[i], A[i+1]) swap(A[i], A[i+1]
} }
} }
} }
}
 OpenMP Exam
❑ Example: Quick Sort Algorithm [Paradigm
➢In quickso
QuickSort(A, low, high) Left s
{ Right
if (low < high) ➢For exam
{ pivot = 5
p = Partition(A, low, high)
where th
QuickSort(A, low, p-1) independe
QuickSort(A, p+1, high) parallelism
} ➢ Sequentia
} THEN so
thinks sor
 OpenMP Exam
❑ Example: Quick Sort Algorithm [Paradigm
1 ➢ Partition
ParallelQuickSort(A, low, high) regions.
{ ➢ Independe
if (low < high) ➢ Threads p
{
p = Partition(A, low, high)
➢ Much less

#pragma omp task

#
ParallelQuickSort(A, low, p-1) Inside the main()

#pragma omp par

#pragma omp task {
ParallelQuickSort(A, p+1, high) #pragma omp s
{
#pragma omp taskwait ParallelQuic
} }
} }
 REFERENC

Principles of Parallel Programming by Ca