Module-4

Shared Memory Programming

with OpenMP

Copyright © 2010, Elsevier Inc. All rights Reserved 1

 # Chapter Subtitle
Roadmap
 Writing programs that use OpenMP.
 Using OpenMP to parallelize many serial for
loops with only small changes to the source
code.
 Task parallelism.
 Explicit thread synchronization.
 Standard problems in shared-memory
programming.

Copyright © 2010, Elsevier Inc. All rights Reserved 2

OpenMP
 An API for shared-memory parallel
programming.
 MP = multiprocessing
 Designed for systems in which each thread
or process can potentially have access to
all available memory.
 System is viewed as a collection of cores
or CPU’s, all of which have access to main
memory.

Copyright © 2010, Elsevier Inc. All rights Reserved 3

A shared memory system

Copyright © 2010, Elsevier Inc. All rights Reserved 4

Pragmas
 Special preprocessor instructions.
 Typically added to a system to allow
behaviors that aren’t part of the basic C
specification.
 Compilers that don’t support the pragmas
ignore them.
#pragma

Copyright © 2010, Elsevier Inc. All rights Reserved 5

Copyright © 2010, Elsevier Inc. All rights Reserved 6
 gcc −g −Wall −fopenmp −o omp_hello omp_hello . c

. / omp_hello 4
compiling
running with 4 threads

Hello from thread 0 of 4 possible Hello from thread 3 of 4

Hello from thread 1 of 4 outcomes
Hello from thread 1 of 4
Hello from thread 2 of 4
Hello from thread 2 of 4
Hello from thread 3 of 4 Hello from thread 1 of 4 Hello from thread 0 of 4
Hello from thread 2 of 4
Hello from thread 0 of 4
Hello from thread 3 of 4

Copyright © 2010, Elsevier Inc. All rights Reserved 7

gcc -g -Wall -fopenmp -o omp_hello omp_hello.c is
used to compile a C program named omp_hello.c

 Flag Breakdown
 -g : Includes debugging information in the executable, which is useful for
debugging with tools like gdb.

 -Wall : Enables most compiler warnings to help catch potential errors and
bad practices during compilation.

 -fopenmp : Enables OpenMP support, allowing the compiler to interpret

OpenMP directives (e.g., #pragma omp parallel) and link the required
OpenMP runtime library.

 -o omp_hello : Specifies the output executable name as omp_hello, rather

than the default [Link].

 omp_hello.c : Indicates the source file to compile, in this case the file
containing the parallel C application.

Copyright © 2010, Elsevier Inc. All rights Reserved 8

OpenMp pragmas
 # pragma omp parallel

 Most basic parallel directive.

 The number of threads that run
the following structured block of code
is determined by the run-time system.

Copyright © 2010, Elsevier Inc. All rights Reserved 9

A process forking and joining
two threads

Copyright © 2010, Elsevier Inc. All rights Reserved 10

clause
 Text that modifies a directive.
 The num_threads clause can be added to
a parallel directive.
 It allows the programmer to specify the
number of threads that should execute the
following block.

# pragma omp parallel num_threads ( thread_count )

Copyright © 2010, Elsevier Inc. All rights Reserved 11

Of note…
 There may be system-defined limitations on the
number of threads that a program can start.
 The OpenMP standard doesn’t guarantee that
this will actually start thread_count threads.
 Most current systems can start hundreds or even
thousands of threads.
 Unless we’re trying to start a lot of threads, we
will almost always get the desired number of
threads.

Copyright © 2010, Elsevier Inc. All rights Reserved 12

Some terminology
 In OpenMP parlance the collection of
threads executing the parallel block — the
original thread and the new threads — is
called a team, the original thread is called
the master, and the additional threads are
called slaves.

Copyright © 2010, Elsevier Inc. All rights Reserved 13

Copyright © 2010, Elsevier Inc. All rights Reserved 14
In case the compiler doesn’t
support OpenMP

# include <omp.h>

#ifdef _OPENMP
# include <omp.h>
#endif

Copyright © 2010, Elsevier Inc. All rights Reserved 15

In case the compiler doesn’t
support OpenMP

# ifdef _OPENMP
int my_rank = omp_get_thread_num ( );
int thread_count = omp_get_num_threads ( );
#else
int my_rank = 0;
int thread_count = 1;
# endif

Copyright © 2010, Elsevier Inc. All rights Reserved 16

THE TRAPEZOIDAL RULE

Copyright © 2010, Elsevier Inc. All rights Reserved 17

 The trapezoidal rule is a numerical
integration technique used to estimate the
area under a curve by dividing the interval
into equal parts and approximating each
part as a trapezoid.

Copyright © 2010, Elsevier Inc. All rights Reserved 18

The trapezoidal rule

Copyright © 2010, Elsevier Inc. All rights Reserved 19

Serial algorithm

Copyright © 2010, Elsevier Inc. All rights Reserved 20

21
A First OpenMP Version
1) We identified two types of tasks:
a) computation of the areas of individual
trapezoids, and
b) adding the areas of trapezoids.
2) There is no communication among the
tasks in the first collection, but each task
in the first collection communicates with
task 1b.

Copyright © 2010, Elsevier Inc. All rights Reserved 22

A First OpenMP Version
3) We assumed that there would be many
more trapezoids than cores.

 So we aggregated tasks by assigning a

contiguous block of trapezoids to each
thread (and a single thread to each core).

Copyright © 2010, Elsevier Inc. All rights Reserved 23

Assignment of trapezoids to threads

Copyright © 2010, Elsevier Inc. All rights Reserved 24

Copyright © 2010, Elsevier Inc. All rights Reserved 25
Unpredictable results when two (or more)
threads attempt to simultaneously execute:

global_result += my_result ;

Copyright © 2010, Elsevier Inc. All rights Reserved 26

Copyright © 2010, Elsevier Inc. All rights Reserved 27
Mutual exclusion

# pragma omp critical

global_result += my_result ;

only one thread can execute

the following structured block at a time

Copyright © 2010, Elsevier Inc. All rights Reserved 28

Copyright © 2010, Elsevier Inc. All rights Reserved 29
Copyright © 2010, Elsevier Inc. All rights Reserved 30
Copyright © 2010, Elsevier Inc. All rights Reserved 31
SCOPE OF VARIABLES

Copyright © 2010, Elsevier Inc. All rights Reserved 32

Scope
 In serial programming, the scope of a
variable consists of those parts of a
program in which the variable can be used.

 In OpenMP, the scope of a variable refers

to the set of threads that can access the
variable in a parallel block.

Copyright © 2010, Elsevier Inc. All rights Reserved 33

Scope in OpenMP
 A variable that can be accessed by all the
threads in the team has shared scope.

 A variable that can only be accessed by a

single thread has private scope.

 The default scope for variables

declared before a parallel block
is shared.
Copyright © 2010, Elsevier Inc. All rights Reserved 34
Copyright © 2010, Elsevier Inc. All rights Reserved 35
Copyright © 2010, Elsevier Inc. All rights Reserved 36
37
THE REDUCTION CLAUSE

Copyright © 2010, Elsevier Inc. All rights Reserved 38

We need this more complex version to add each
thread’s local calculation to get global_result.

Although we’d prefer this.

Copyright © 2010, Elsevier Inc. All rights Reserved 39

If we use this, there’s no critical section!

If we fix it like this…

… we force the threads to execute sequentially.

Copyright © 2010, Elsevier Inc. All rights Reserved 40

We can avoid this problem by declaring a private
variable inside the parallel block and moving
the critical section after the function call.

Copyright © 2010, Elsevier Inc. All rights Reserved 41

Reduction operators
 A reduction operator is a binary operation
(such as addition or multiplication).
 A reduction is a computation that
repeatedly applies the same reduction
operator to a sequence of operands in
order to get a single result.
 All of the intermediate results of the
operation should be stored in the same
variable: the reduction variable.

Copyright © 2010, Elsevier Inc. All rights Reserved 42

A reduction clause can be added to a parallel
directive.

+, *, -, &, |, ˆ, &&, ||

Copyright © 2010, Elsevier Inc. All rights Reserved 43

Copyright © 2010, Elsevier Inc. All rights Reserved 44
THE “PARALLEL FOR”
DIRECTIVE

Copyright © 2010, Elsevier Inc. All rights Reserved 45

Parallel for
 Forks a team of threads to execute the
following structured block.
 However, the structured block following the
parallel for directive must be a for loop.
 Furthermore, with the parallel for directive
the system parallelizes the for loop by
dividing the iterations of the loop among
the threads.

Copyright © 2010, Elsevier Inc. All rights Reserved 46

Copyright © 2010, Elsevier Inc. All rights Reserved 47
Legal forms for parallelizable for
statements

Copyright © 2010, Elsevier Inc. All rights Reserved 48

Caveats
 The variable index must have integer or
pointer type (e.g., it can’t be a float).

 The expressions start, end, and incr must

have a compatible type. For example, if
index is a pointer, then incr must have
integer type.

Copyright © 2010, Elsevier Inc. All rights Reserved 49

Caveats
 The expressions start, end, and incr must
not change during execution of the loop.

 During execution of the loop, the variable

index can only be modified by the
“increment expression” in the for
statement.

Copyright © 2010, Elsevier Inc. All rights Reserved 50

Data dependencies
fibo[ 0 ] = fibo[ 1 ] = 1;
for (i = 2; i < n; i++)
fibo[ i ] = fibo[ i – 1 ] + fibo[ i – 2 ];
note 2 threads

fibo[ 0 ] = fibo[ 1 ] = 1;
# pragma omp parallel for num_threads(2)
for (i = 2; i < n; i++)
fibo[ i ] = fibo[ i – 1 ] + fibo[ i – 2 ];

but sometimes
we get this
1 1 2 3 5 8 13 21 34 55
this is correct 1123580000

Copyright © 2010, Elsevier Inc. All rights Reserved 51

What happened?
1. OpenMP compilers don’t
check for dependences
among iterations in a loop
that’s being parallelized with
a parallel for directive.
2. A loop in which the results
of one or more iterations
depend on other iterations
cannot, in general, be
correctly parallelized by
OpenMP.

Copyright © 2010, Elsevier Inc. All rights Reserved 52

Estimating π

Copyright © 2010, Elsevier Inc. All rights Reserved 53

OpenMP solution #1

loop dependency

Copyright © 2010, Elsevier Inc. All rights Reserved 54

OpenMP solution #2

Insures factor has

private scope.

Copyright © 2010, Elsevier Inc. All rights Reserved 55

The default clause
 Lets the programmer specify the scope of
each variable in a block.

 With this clause the compiler will require

that we specify the scope of each variable
we use in the block and that has been
declared outside the block.

Copyright © 2010, Elsevier Inc. All rights Reserved 56

The default clause

Copyright © 2010, Elsevier Inc. All rights Reserved 57

MORE ABOUT LOOPS IN
OPENMP: SORTING

Copyright © 2010, Elsevier Inc. All rights Reserved 58

Bubble Sort

Copyright © 2010, Elsevier Inc. All rights Reserved 59

Serial Odd-Even Transposition Sort

Copyright © 2010, Elsevier Inc. All rights Reserved 60

Serial Odd-Even Transposition Sort

Copyright © 2010, Elsevier Inc. All rights Reserved 61

First OpenMP Odd-Even Sort

Copyright © 2010, Elsevier Inc. All rights Reserved 62

Second OpenMP Odd-Even Sort

Copyright © 2010, Elsevier Inc. All rights Reserved 63

Odd-even sort with two parallel for directives and two for directives.
(Times are in seconds.)

Copyright © 2010, Elsevier Inc. All rights Reserved 64

SCHEDULING LOOPS

Copyright © 2010, Elsevier Inc. All rights Reserved 65

 When parallelizing loops, assigning iterations
to threads (scheduling) has a big impact on
performance.
 Problem with Default Scheduling

Default: block partitioning (first n/thread_count

iterations → thread 0, next block → thread 1,
etc.)
Issue: if iterations take different amounts of
time, load imbalance occurs.
 Example: f(i) takes time proportional to i.
 Thread with higher i values (e.g., last thread) gets
more work → poor speedup.

Copyright © 2010, Elsevier Inc. All rights Reserved 66

We want to parallelize
this loop.

Assignment of work
using cyclic partitioning.

Copyright © 2010, Elsevier Inc. All rights Reserved 67

 Our definition of function f.

Copyright © 2010, Elsevier Inc. All rights Reserved 68

Results
 f(i) calls the sin function i times.
 Assume the time to execute f(2i) requires
approximately twice as much time as the
time to execute f(i).

 n = 10,000
 one thread
 run-time = 3.67 seconds.

Copyright © 2010, Elsevier Inc. All rights Reserved 69

Results
 n = 10,000
 two threads
 default assignment
 run-time = 2.76 seconds
 speedup = 1.33
 n = 10,000
 two threads
 cyclic assignment
 run-time = 1.84 seconds
 speedup = 1.99
Copyright © 2010, Elsevier Inc. All rights Reserved 70
The Schedule Clause
 Default schedule:

 Cyclic schedule:

Copyright © 2010, Elsevier Inc. All rights Reserved 71

schedule ( type , chunksize )
 Type can be:
 static: the iterations can be assigned to the
threads before the loop is executed.
 dynamic or guided: the iterations are assigned
to the threads while the loop is executing.
 auto: the compiler and/or the run-time system
determine the schedule.
 runtime: the schedule is determined at run-
time.
 The chunksize is a positive integer.
Copyright © 2010, Elsevier Inc. All rights Reserved 72
The Static Schedule Type
twelve iterations, 0, 1, . . . , 11, and three threads

Copyright © 2010, Elsevier Inc. All rights Reserved 73

The Static Schedule Type
twelve iterations, 0, 1, . . . , 11, and three threads

Copyright © 2010, Elsevier Inc. All rights Reserved 74

The Static Schedule Type
twelve iterations, 0, 1, . . . , 11, and three threads

Copyright © 2010, Elsevier Inc. All rights Reserved 75

The Dynamic Schedule Type
 The iterations are also broken up into chunks
of chunksize consecutive iterations.
 Each thread executes a chunk, and when a
thread finishes a chunk, it requests another
one from the run-time system.
 This continues until all the iterations are
completed.
 The chunksize can be omitted. When it is
omitted, a chunksize of 1 is used.

Copyright © 2010, Elsevier Inc. All rights Reserved 76

The Guided Schedule Type
 Each thread also executes a chunk, and when a
thread finishes a chunk, it requests another one.
 However, in a guided schedule, as chunks are
completed the size of the new chunks
decreases.
 If no chunksize is specified, the size of the
chunks decreases down to 1.
 If chunksize is specified, it decreases down to
chunksize, with the exception that the very last
chunk can be smaller than chunksize.

Copyright © 2010, Elsevier Inc. All rights Reserved 77

Assignment of trapezoidal rule iterations 1–9999 using
a guided schedule with two threads.

Copyright © 2010, Elsevier Inc. All rights Reserved 78

The Runtime Schedule Type
 The system uses the environment variable
OMP_SCHEDULE to determine at run-
time how to schedule the loop.
 The OMP_SCHEDULE environment
variable can take on any of the values that
can be used for a static, dynamic, or
guided schedule.

Copyright © 2010, Elsevier Inc. All rights Reserved 79

PRODUCERS AND
CONSUMERS

Copyright © 2010, Elsevier Inc. All rights Reserved 80

 A queue is a fundamental abstract data
type in computer science, analogous to a
line of people at a supermarket checkout:
entries (e.g., customers or requests) join at
the rear and are removed from the front.
 Enqueue: Adding an element to the rear.
 Dequeue: Removing an element from the
front.

Copyright © 2010, Elsevier Inc. All rights Reserved 81

Queues
 Can be viewed as an abstraction of a line of
customers waiting to pay for their groceries in a
supermarket.
 A natural data structure to use in many
multithreaded applications.
 For example, suppose we have several
“producer” threads and several “consumer”
threads.
 Producer threads might “produce” requests for data.
 Consumer threads might “consume” the request by
finding or generating the requested data.

Copyright © 2010, Elsevier Inc. All rights Reserved 82

Message-Passing
 Each thread could have a shared message
queue, and when one thread wants to
“send a message” to another thread, it
could enqueue the message in the
destination thread’s queue.
 A thread could receive a message by
dequeuing the message at the head of its
message queue.

Copyright © 2010, Elsevier Inc. All rights Reserved 83

 A shared-memory message-passing system
can be implemented using per-thread
queues, with threads alternating
between sending messages and
receiving them from their queue. Each
thread generates random integer messages,
chooses random destinations, and
enqueues messages in
the destination's queue; then it dequeues
received messages from its own queue and
processes (prints) them

Copyright © 2010, Elsevier Inc. All rights Reserved 84

 Message-Passing
for (sent_msgs = 0; sent_msgs < send_max; sent_msgs++) {
Send_msg(); // Generate and enqueue a message for a
random destination
Try_receive(); // Check and dequeue a message from own
queue, if any
}
while (!Done()) {
Try_receive(); // Continue receiving messages until all
threads have finished
}

Copyright © 2010, Elsevier Inc. All rights Reserved 85

Sending Messages

Copyright © 2010, Elsevier Inc. All rights Reserved 86

 Step-by-step
 Message creation
 Each thread generates a random message (mesg).
 It also chooses a random destination thread (dest).
 Critical Section
 #pragma omp critical ensures only one thread at a
time executes the Enqueue() operation.
 Prevents race conditions when multiple threads try to
update the rear pointer of the queue simultaneously.
 Enqueue Operation
 Enqueue(queue, dest, my_rank, mesg); inserts the
message into the destination thread’s message
queue.
 Safe insertion is guaranteed by the critical directive

Copyright © 2010, Elsevier Inc. All rights Reserved 87

 The #pragma omp critical directive is used
to prevent race conditions in shared data
structures (like queues) when multiple
threads are enqueueing messages.

Copyright © 2010, Elsevier Inc. All rights Reserved 88

Copyright © 2010, Elsevier Inc. All rights Reserved 89
Copyright © 2010, Elsevier Inc. All rights Reserved 90
Receiving Messages

Copyright © 2010, Elsevier Inc. All rights Reserved 91

 🔹 Sending (Enqueue)
 Multiple threads may enqueue into the same
queue → needs #pragma omp critical to
avoid rear pointer race condition.
 Without protection → messages can get lost.
 🔹 Receiving (Dequeue)
 Only the owner thread dequeues from its
queue → so no race condition between
threads on dequeue itself.
 But we must be careful with the queue size
variable.
Copyright © 2010, Elsevier Inc. All rights Reserved 92
Copyright © 2010, Elsevier Inc. All rights Reserved 93
 Termination Detection

queue_size = enqueued - dequeued;

if (queue_size == 0 && done_sending ==
thread_count)
return TRUE; // No messages left +
nobody will send more
else
return FALSE; // Either messages remain,
or some threads may still send

Copyright © 2010, Elsevier Inc. All rights Reserved 94

 Ensures no thread quits if others are still
capable of sending messages.
 Waits until all threads have finished
sending before checking emptiness.
 Prevents message loss due to late arrivals
after an empty queue check.

Copyright © 2010, Elsevier Inc. All rights Reserved 95

 Access to done_sending must be thread-safe
(atomic increment or protected by locks).
 Checking queue sizes
and done_sending should be done in a
manner that ensures memory consistency
across threads.
 This approach guarantees that threads only
terminate once all messages have been sent
and received, ensuring no messages are lost
in the message-passing program

Copyright © 2010, Elsevier Inc. All rights Reserved 96

Startup (1)
 When the program begins execution, a
single thread, the master thread, will get
command line arguments and allocate an
array of message queues: one for each
thread.
 This array needs to be shared among the
threads, since any thread can send to any
other thread, and hence any thread can
enqueue a message in any of the queues.

Copyright © 2010, Elsevier Inc. All rights Reserved 97

Startup (2)
 One or more threads may finish allocating
their queues before some other threads.
 We need an explicit barrier so that when a
thread encounters the barrier, it blocks
until all the threads in the team have
reached the barrier.
 After all the threads have reached the
barrier all the threads in the team can
proceed.

Copyright © 2010, Elsevier Inc. All rights Reserved 98

The Atomic Directive (1)
 Unlike the critical directive, it can only
protect critical sections that consist of a
single C assignment statement.

 Further, the statement must have one of

the following forms:

Copyright © 2010, Elsevier Inc. All rights Reserved 99

The Atomic Directive (2)
 Here <op> can be one of the binary operators

 Many processors provide a special load-

modify-store instruction.
 A critical section that only does a load-modify-
store can be protected much more efficiently
by using this special instruction rather than
the constructs that are used to protect more
general critical sections.

Copyright © 2010, Elsevier Inc. All rights Reserved 100

Critical Sections
 OpenMP provides the option of adding a
name to a critical directive:

 When we do this, two blocks protected

with critical directives with different names
can be executed simultaneously.
 However, the names are set during
compilation, and we want a different critical
section for each thread’s queue.
Copyright © 2010, Elsevier Inc. All rights Reserved 101
Locks
 A lock consists of a data structure and
functions that allow the programmer to
explicitly enforce mutual exclusion in a
critical section.

Copyright © 2010, Elsevier Inc. All rights Reserved 102

Locks

Copyright © 2010, Elsevier Inc. All rights Reserved 103

Using Locks in the Message-
Passing Program

Copyright © 2010, Elsevier Inc. All rights Reserved 104

Using Locks in the Message-
Passing Program

Copyright © 2010, Elsevier Inc. All rights Reserved 105

Some Caveats
1. You shouldn’t mix the different types of
mutual exclusion for a single critical
section.
2. There is no guarantee of fairness in
mutual exclusion constructs.
3. It can be dangerous to “nest” mutual
exclusion constructs.

Copyright © 2010, Elsevier Inc. All rights Reserved 106

Caches, Cache Coherence, and False Sharing

 CPUs execute arithmetic operations much

faster than they can access main memory.
 Fetching every operand directly from main
memory would make the CPU spend most
of its time waiting.
 To solve this, cache memory—small, fast
memory close to the processor—is used.
 The cache stores recently accessed data
so that future accesses are faster

Copyright © 2010, Elsevier Inc. All rights Reserved 107

Matrix-vector multiplication

Copyright © 2010, Elsevier Inc. All rights Reserved 108

Matrix-vector multiplication

Run-times and efficiencies

of matrix-vector multiplication
(times are in seconds)

Copyright © 2010, Elsevier Inc. All rights Reserved 109

Tasking
 Most OpenMP constructs (like parallel for) work
well when:
 The number of parallel tasks or loop iterations is fixed
or known in advance.
 However, some problems don’t have a fixed
amount of work, for example:
 A web server (new HTTP requests arrive
dynamically)
 Recursive algorithms (like Fibonacci, quicksort, or
graph traversals)
 Producer–consumer programs
 These dynamic or irregular workloads cannot
be parallelized efficiently with static for loops.
Copyright © 2010, Elsevier Inc. All rights Reserved 110
 To handle such cases, OpenMP 3.0
introduced “Tasks” — a way to define
independent units of work dynamically.
 #pragma omp task
 When a thread encounters this directive:
 It creates a new task that can be
executed by any available thread.
 The task may not execute immediately
(it’s queued by the OpenMP runtime).
Copyright © 2010, Elsevier Inc. All rights Reserved 111
 #pragma omp parallel
 #pragma omp single
 {
 // Only one thread launches tasks
 #pragma omp task
 {
 // Task 1 code
 }

 #pragma omp task

 {
 // Task 2 code
 }
 }

Copyright © 2010, Elsevier Inc. All rights Reserved 112

 parallel → creates a team of [Link]
→ ensures only one thread creates tasks
(to avoid duplication).Each #pragma omp
task block defines a unit of work.

Copyright © 2010, Elsevier Inc. All rights Reserved 113

 int fib(int n) {
 int i = 0, j = 0;

 if (n <= 1) {
 fibs[n] = n;
 return n;
 }

 #pragma omp task shared(i)

 i = fib(n - 1);

 #pragma omp task shared(j)

 j = fib(n - 2);

 #pragma omp taskwait

 fibs[n] = i + j;

 return fibs[n];
 }

Copyright © 2010, Elsevier Inc. All rights Reserved 114

 Concept of Thread-Safety
 A block of code is said to be thread-safe if
it can be safely executed by multiple
threads simultaneously without causing
incorrect results or data corruption.
 In shared-memory systems, multiple
threads often access shared data — if
such access is not properly controlled, it
can lead to race conditions and
unpredictable behavior.
Copyright © 2010, Elsevier Inc. All rights Reserved 115
 Consider a program that uses multiple threads to
tokenize lines of text (split text into words separated by
spaces, tabs, or newlines).
Each thread processes a different line using the C library
function strtok().
 char* strtok(char* string, const char* separators);
 The first call to strtok() uses the actual string.
 Subsequent calls pass NULL so that strtok() continues tokenizing the
same string .
 Internally, strtok() stores a cached pointer to
remember its position.

Copyright © 2010, Elsevier Inc. All rights Reserved 116

 Thread-Safety

Copyright © 2010, Elsevier Inc. All rights Reserved 117

Copyright © 2010, Elsevier Inc. All rights Reserved 118
Concept Description
Ability of code to run correctly when
Thread-Safety accessed by multiple threads
simultaneously
strtok() shares internal state and
Non-thread-safe Example
causes conflicts
strtok_r() uses independent state
Thread-safe Alternative
per thread
Assuming a program is correct just
Common Mistake because it produces correct output
once
Race conditions and nondeterministic
Cause of Errors
thread execution

Copyright © 2010, Elsevier Inc. All rights Reserved 119

Concluding Remarks (1)
 OpenMP is a standard for programming
shared-memory systems.
 OpenMP uses both special functions and
preprocessor directives called pragmas.
 OpenMP programs start multiple threads
rather than multiple processes.
 Many OpenMP directives can be modified
by clauses.

Copyright © 2010, Elsevier Inc. All rights Reserved 120

Concluding Remarks (2)
 A major problem in the development of
shared memory programs is the possibility
of race conditions.
 OpenMP provides several mechanisms for
insuring mutual exclusion in critical
sections.
 Critical directives
 Named critical directives
 Atomic directives
 Simple locks
Copyright © 2010, Elsevier Inc. All rights Reserved 121
Concluding Remarks (3)
 By default most systems use a block-
partitioning of the iterations in a
parallelized for loop.
 OpenMP offers a variety of scheduling
options.
 In OpenMP the scope of a variable is the
collection of threads to which the variable
is accessible.

Copyright © 2010, Elsevier Inc. All rights Reserved 122

Concluding Remarks (4)
 A reduction is a computation that
repeatedly applies the same reduction
operator to a sequence of operands in
order to get a single result.

Copyright © 2010, Elsevier Inc. All rights Reserved 123