Module 4

Shared-memory programming
with OpenMP
Presented By:
Dr. Murali G
Professor & Head
SJB Institute of Technology, Bangalore
Contents
• openmp pragmas and directives,
• The trapezoidal rule,
• Scope of variables,
• The reduction clause, loop carried dependency, scheduling, producers
and consumers,
• Caches, cache coherence and false sharing in openmp, tasking,
tasking, thread safety.
 4.1 openmp pragmas and directives,
• OpenMP (Open Multi-Processing) is an API that supports multi-platform shared-memory
multiprocessing programming. It allows developers to write parallel code using compiler directives
(pragmas), library routines, and environment variables — mainly for C/C++ and Fortran.

• In C/C++, OpenMP directives are written using #pragma statements.

Basic Syntax:

• #pragma omp directive-name [clause [clause] ...]

#pragma omp parallel
{ printf("Hello from thread %d\n", omp_get_thread_num()); }
• This code runs the printf statement in parallel across multiple threads.
 Common OpenMP Directives (Pragmas)
• Here’s a summary of the most common and important OpenMP
directives used in parallel programming:
Creates a parallel region — a block of code executed by multiple threads.

#pragma omp parallel

{
printf("Thread %d says hello\n", omp_get_thread_num());
}

2. #pragma omp for / #pragma omp parallel for

Used to split loop iterations among threads.

#pragma omp parallel for

for (int i = 0; i < 10; i++) {
printf("Iteration %d by thread %d\n", i,
omp_get_thread_num());
}
 4.2 The trapezoidal rule
• Let’s take a look at a somewhat more useful (and more complicated) example: the
trapezoidal rule for estimating the area under a curve. Recall from Section 3.2 that
if y = f (x) is a reasonably nice function, and a<b are real numbers, then we can
estimate the area between the graph of f (x), the vertical lines x = a and x = b, and
the x-axis by dividing the interval [a,b] into n subintervals and approximating the
area over each subinterval by the area of a trapezoid. See Fig. 5.3.
• Also recall that if each subinterval has the same length and if we define
h =(b − a)/n, xi = a + ih, i = 0, 1,...,n, then our approximation will be
• Thus we can implement a serial algorithm using the following code:
 5.3 Scope of variables
• In serial programming, the scope of a variable consists of those parts of a program in which the
variable can be used. For example, a variable declared at the beginning of a C function has
“function-wide” scope, that is, it can only be accessed in the body of the function.

• On the other hand, a variable declared at the beginning of a .c file but outside any function has
“file-wide” scope, that is, any function in the file in which the variable is declared can access the
variable.

• In OpenMP, the scope of a variable refers to the set of threads that can access the variable in a
parallel block.
• A variable that can be accessed by all the threads in the team has shared scope, while a variable
that can only be accessed by a single thread has private scope.
 cont..
The variables that are declared in the main function (a, b, n, global_result, and thread_count) are
all accessible to all the threads in the team started by the parallel directive.

Hence, the default scope for variables declared before a parallel block is shared. In fact, we’ve
made implicit use of this: each thread in the team gets the values of a, b, and n from the call to
Trap. Since this call takes place in the parallel block, it’s essential that each thread has access to a,
b, and n when their values are copied into the corresponding formal arguments. Furthermore, in the
Trap function, although global_result_p is a private variable, it refers to the variable global_result
which was declared in main before the parallel directive, and the value of global_result is used to
store the result that’s printed out after the parallel block. Thus in the code
 cont..
• The variables that have been declared before a parallel directive have shared
scope among the threads in the team, while variables declared in the block (e.g.,
local variables in functions) have private scope.

• Furthermore, the value of a shared variable at the beginning of the parallel block
is the same as the value before the block, and, after completion of the parallel
block, the value of the variable is the value at the end of the block.
 5.4 The reduction clause
• If we developed a serial implementation of the trapezoidal rule, we’d probably use a slightly different
function prototype. Rather than

we would probably define

double Trap ( double a , double b , int n ) ;
and our function call would be

global_result = Trap ( a , b , n ) ;
This is somewhat easier to understand and probably more attractive to all but the most fanatical believers in
pointers. We resorted to the pointer version, because we needed to add each thread’s local calculation to get
global_result. However, we might prefer the following function prototype:
double Local_trap ( double a , double b , int n ) ;
 cont..
• With this prototype, the body of Local_trap would be the same as the Trap function , except that there
would be no critical section. Rather, each thread would return its part of the calculation, the final value of
its my_result variable. If we made this change, we might try modifying our parallel block so that it looks
like this:

Can you see a problem with this code? It should give the correct result. However, since we’ve specified that the critical
section is the call to Local_trap can only be executed by one thread at a time, and, effectively, we’re forcing the
threads to execute the trapezoidal rule sequentially. If we check the run-time of this version, it may actually be slower
with multiple threads than one thread.
global_result += Local_trap ( double a , double b , int n ) ;
 cont..
• We can avoid this problem by declaring a private variable inside the parallel block and moving the critical
section after the function call:

Now the call to Local_trap is outside the critical section, and the threads can execute their calls simultaneously.

• OpenMP provides a cleaner alternative that also avoids serializing execution of Local_trap: we can specify that
global_result is a reduction variable.
• A reduction operator is an associative binary operation (such as addition or multiplication), and a reduction is a
computation that repeatedly applies the same reduction operator to a sequence of operands to get a single result.
 cont..
• Furthermore, all of the intermediate results of the operation should be stored in the same variable: the
reduction variable. For example, if A is an array of n ints, the computation
int
sum = 0;
for ( i = 0; i < n ; i ++)
sum += A [ i ] ;

is a reduction in which the reduction operator is addition.

In OpenMP it may be possible to specify that the result of a reduction is a reduction variable. To do this, a reduction
clause can be added to a parallel directive. In our example, we can modify the code as follows:
 cont..
• The code specifies that global_result is a reduction variable, and the plus sign (“+”) indicates that the reduction
operator is addition.

• OpenMP creates a private variable for each thread, and the run-time system stores each thread’s result in this private
variable.

• OpenMP also creates a critical section, and the values stored in the private variables are added in this critical section.
Thus the calls to Local_trap can take place in parallel. The syntax of the reduction clause is

reduction ( < operator >: <variable list >)

In C, operator can be any one of the operators +, ∗, −, &, |, ^, &&, || . You may wonder whether the use of subtraction is
problematic, though, since subtraction isn’t associative or commutative. For example, the serial code
result = 0;
for ( i = 1; i <= 4; i ++)
result −= i ;
 cont..
• stores the value −10 in result. However, if we split the iterations among two threads, with thread 0
subtracting 1 and 2 and thread 1 subtracting 3 and 4, then thread 0 will compute −3 and thread 1 will
compute −7. This results in an incorrect calculation, −3 − (−7) = 4. Luckily, the OpenMP standard states that
partial results of a subtraction reduction are added to form the final value, so the reduction will work as
intended.

• It should also be noted that if a reduction variable is a float or a double, the results may differ slightly when
different numbers of threads are used. This is due to the fact that floating point arithmetic isn’t associative.
For example, if a, b, and c are floats, then (a + b) + c may not be exactly equal to a + (b + c).

• When a variable is included in a reduction clause, the variable itself is shared. However, a private variable
is created for each thread in the team. In the parallel block each time a thread executes a statement
involving the variable, it uses the private variable. When the parallel block ends, the values in the private
variables are combined into the shared variable. Thus our latest version of the code
cont..
 5.5 Finding loop-carried dependences
• Perhaps the first thing to observe is that when we’re attempting to use a parallel for directive, we only need to
worry about loop-carried dependences. We don’t need to worry about more general data dependences. For
example, in the loop

• there is a data dependence between Lines 2 and 3. However, there is no problem with the parallelization

• since the computation of x[i] and its subsequent use will always be assigned to the ame thread.
 5.7 Scheduling loops
• When we first encountered the parallel for directive, we saw that the exact
assignment of loop iterations to threads is system dependent. However most OpenMP
implementations use roughly a block partitioning: if there are n iterations in the serial
loop, then in the parallel loop the first n/thread_count are assigned to thread 0, the
next n/thread_count are assigned to thread 1, and so on. It’s not difficult to think of
situations in which this assignment of iterations to threads would be less than optimal.
For example, suppose we want to parallelize the loop
sum = 0.0;
for ( i = 0; i <= n ; i ++)
sum += f ( i ) ;
 cont...
• Also suppose that the time required by the call to f is proportional to the size of the
argument i. Then a block partitioning of the iterations will assign much more work to
thread thread_count − 1 than it will assign to thread 0.

• A better assignment of work to threads might be obtained with a cyclic partitioning

of the iterations among the threads. In a cyclic partitioning, the iterations are
assigned, one at a time, in a “round-robin” fashion to the threads. Suppose t =
thread_count. Then a cyclic partitioning will assign the iterations as follows:
 cont...

To get a feel for how drastically this can affect performance, we wrote a program in which we defined
double f ( int i ) {
int j ,
start = i ∗( i +1)/2 ,
finish = start + i ;
double return_val = 0.0;
for ( j = start ; j <= finish ; j ++) {
return_val += sin ( j ) ; }
return
return_val ; } / ∗ f ∗ /
 cont...
• The call f (i) calls the sin function i times, and, for example, the time to execute f (2i) requires
approximately twice as much time as the time to execute f (i).

• When we ran the program with n = 10,000 and one thread, the run-time was 3.67 seconds.
When we ran the program with two threads and the default assignment—iterations 0–5000 on
thread 0 and iterations 5001–10,000 on thread 1—the run-time was 2.76 seconds. This is a
speedup of only 1.33. However, when we ran the program with two threads and a cyclic
assignment, the run-time was decreased to 1.84 seconds.

• This is a speedup of 1.99 over the one-thread run and a speedup of 1.5 over the
two_x0002_thread block partition!
• In OpenMP, assigning iterations to threads is called scheduling, and the schedule clause can be
used to assign iterations in either a parallel for or a for directive.
 5.7.1 The schedule clause
• In our example, we already know how to obtain the default schedule: we just add a
parallel for directive with a reduction clause:
sum = 0.0;
# pragma omp p a r a l l e l for num_threads( thread_count ) \ reduction (+: sum )
for ( i = 0; i <= n ; i ++)
sum += f ( i ) ;
• To get a cyclic schedule, we can add a schedule clause to the parallel for directive:
sum = 0.0;
# pragma omp p a r a l l e l for num_threads( thread_count ) \ reduction (+: sum )
schedule ( static ,1)
• for ( i = 0; i <= n ; i ++)
• sum += f ( i ) ;
 cont..
• In general, the schedule clause has the form

schedule ( < type > [, <chunksize >])

The type can be any one of the following:

• 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, so
after a thread completes its current set of iterations, it can request more from the run-time
system.

• auto. The compiler and/or the run-time system determine the schedule.

• runtime. The schedule is determined at run-time based on an environment variable (more on

this later).
Figure: Scheduling visualization for the static,
dynamic, and guided schedule types with 4
threads and 32 iterations.
The first static schedule uses the default chunksize,
whereas the second uses a chunksize of 2. The
exact distribution of work across threads will vary
between different executions of the program for the
dynamic and guided schedule types, so this
visualization shows one of many possible
scheduling outcomes.
 5.7.2 The static schedule type
• For a static schedule, the system assigns chunks of chunksize iterations to each thread in a round-robin
fashion. As an example, suppose we have 12 iterations, 0,1,...,11, and three threads. Then if schedule
(static , 1) is used, in the parallel for or for directive, we’ve already seen that the iterations will be
assigned as Thread 0 : 0,3,6,9
Thread 1 : 1,4,7,10
Thread 2 : 2,5,8,11
If schedule (static , 2) is used, then the iterations will be assigned as
Thread 0 : 0,1,6,7
Thread 1 : 2,3,8,9
Thread 2 : 4,5,10,11
If schedule(static , 4)is used, the iterations will be assigned as
Thread 0 : 0,1,2,3
Thread 1 : 4,5,6,7
Thread 2 : 8,9,10,11
The default schedule is defined by your particular implementation of OpenMP, but in most cases it is equivalent to the clause
schedule(static , total_iterations / thread_count)
 Cont..
• It is also worth noting that the chunksize can be omitted. If omitted, the chunksize is
approximately total_iterations / thread_count.

• The static schedule is a good choice when each loop iteration takes roughly the same amount of
time to compute.
 5.7.3 The dynamic and guided schedule types
• In a dynamic schedule, 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.

• The primary difference between static and dynamic schedules is that the dynamic schedule assigns ranges to
threads on a first-come, first-served basis. This can be advantageous if loop iterations do not take a uniform
amount of time to compute (some algorithms are more compute-intensive in later iterations, for instance).

• The guided schedule is similar to dynamic in that each thread also executes a chunk and requests another one
when it’s finished. However, in a guided schedule, as chunks are completed, the size of the new chunks
decreases.
 Cont..
• For example, on one of our systems, if we
run the trapezoidal rule program with the
parallel for directive and a schedule
(guided) clause, then when n=10,000 and
thread_count=2, the iterations are
assigned as shown in Table5.4. We see that
the size of the chunk is approxi mately the
number of iterations remaining divided
by the number of threads. The first chunk
has size 9999/2≈5000, since there are 9999
un assigned [Link] second chunk
has size 4999/2≈2500, and so on.
 cont..
• In a guided schedule, 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.

• The guided schedule can improve the balance of load across threads when later iterations
are more compute_x0002_intensive.
 5.7.4 The runtime schedule type
• To understand schedule(runtime), we need to digress for a moment and talk about
environment variables. As the name suggests, environment variables are named values
that can be accessed by a running program. That is, they’re available in the program’s
environment. Some commonly used environment variables are PATH, HOME, and
SHELL.

• The PATH variable specifies which directories the shell should search when it’s looking
for an executable and is usually defined in both Unix and Windows.

• The HOME variable specifies the location of the user’s home directory, and

• The SHELL variable specifies the location of the executable for the user’s shell.
 cont..
• In Unix like systems, you can use the shell’s command line. In Windows systems, you can use the command line in an integrated
development environment. As an example, if we’re using the bash shell (one of the most common Unix shells), we can examine
the value of an environment variable by typing:

$ echo $PATH

• and we can use the export command to set the value of an environment variable:

$ export TEST_VAR ="hello"

• These commands also work on ksh, sh, and zsh. For details about how to examine and set environment variables for your
particular system, check the man pages for your shell, or consult with your system administrator or local expert.

• When schedule(runtime) is specified, 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. $ export OMP_SCHEDULE ="static ,1"
 5.8 Producers and consumers
• look at a parallel problem that isn’t amenable to parallelization using a parallel for or for directive.

5.8.1 Queues
Recall that a queue is a list abstract datatype in which new elements are inserted at the “rear” of the queue
and elements are removed from the “front” of the queue. A queue can thus be viewed as an abstraction of a line
of customers waiting to pay for their groceries in a supermarket.

The elements of the list are the customers. New customers go to the end or “rear” of the line, and the next
customer to check out is the customer standing at the “front” of the line. When a new entry is added to the rear
of a queue, we sometimes say that the entry has been “enqueued,” and when an entry is removed from the front
of a queue, we sometimes say that the entry has been “dequeued.”
 cont..
• Queues occur frequently in computer science. For example, if we have a number of processes, each of which
wants to store some data on a hard drive, then a natural way to ensure that only one process writes to the disk at
a time is to have the processes form a queue, that is, the first process that wants to write gets access to the
drive first, the second process gets access to the drive next, and so on.

• A queue is also a natural data structure to use in many multithreaded applications. For example, suppose we
have several “producer” threads and several “consumer” threads.

• The producer threads might “produce” requests for data from a server—for example, current stock prices—
while the consumer threads might “consume” the request by finding or generating the requested data—the
current stock prices. The producer threads could enqueue the requested prices, and the consumer threads
could dequeue them. In this example, the process wouldn’t be completed until the consumer threads had given
the requested data to the producer threads.
• 5.8.2 Message-passing
• Another natural application would be implementing message-passing on a shared memory system.
Each thread could have a shared-message queue, and when one thread wanted 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.

• Let’s implement a relatively simple message-passing program, in which each thread generates
random integer “messages” and random destinations for the messages. After creating the message,
the thread enqueues the message in the appropriate message queue.

• After sending a message, a thread checks its queue to see if it has received a message. If it has, it
dequeues the first message in its queue and prints it out. Each thread alternates between sending and
trying to receive messages.
 cont..
• Pseudocode for each thread might look something like this:
for ( sent_msgs = 0; sent_msgs < send_max ; sent_msgs ++) {
Send_msg ();
Try_receive ();
}
while ( ! Done ())
Try_receive ();
5.8.3 Sending messages:
Note that accessing a message queue to enqueue a message is probably a critical section. Although we
haven’t looked into the details of the implementation of the message queue, it seems likely that we’ll want to
have a variable that keeps track of the rear of the queue.
5.8.4 Receiving messages:
The synchronization issues for receiving a message are a little different. Only the owner of the queue (that is,
the destination thread) will dequeue from a given message queue. As long as we dequeue one message at a
time, if there are at least two messages in the queue, a call to Dequeue can’t possibly conflict with any calls to
Enqueue. So if we keep track of the size of the queue, we can avoid any synchronization (for example, critical
directives), as long as there are at least two messages.

Now you may be thinking, “What about the variable storing the size of the queue?” This would be a problem if
we simply store the size of the queue. However, if we store two variables, enqueued and dequeued, then the
number of messages in the queue is

queue_size = enqueued − dequeued

and the only thread that will update dequeued is the owner of the queue.