OpenMP: What is it?

OpenMP: An API for
Portable Shared
Memory Programming
Alfred Park
February 26, 2003

! A standard developed under the review of many

major software and hardware developers,
government, and academia! Facilitates simple development of programs totake advantage of SMP architectures" SMP: Symmetric multi-processing, access time tomemory is approx. equal for all processors (usually 216 processors)" Shared Memory: memory local to all processors in an
SMP domain" Distributed Memory: remote memory access (nonlocal memory) – NUMA (clusters, grids)

OpenMP: What is it?

Fork-Join Parallelism! OpenMP API is comprised of:! Master-Worker Team thread pattern" Compiler directives
Parallel Loop

" Library routines" Environment variables! OpenMP language support:

Master" Fortran, C, C++! Compilers supporting OpenMP:" Intel Compilers, Portland Group (PGI), IBM, Compaq" Omni, OdinMP can be used with gcc“Fork”“Join”

Parallel Computation

Behind the Scene

Syntax! Thread communication through shared variables! Compiler directives:(shared memory)! Threads can be “carried through” from one
parallel “region” to the next
" Important! Need to amortize thread fork cost andminimize thread joins! Number of threads can be dynamically altered" C/C++! #pragma

omp directive [clause, …]" Fortran! !$OMP

directive [clause, …]! C$OMP directive [clause, …]! *$OMP directive [clause, …]

during runtime! Support for nested parallelism exists in somecompilers! We will focus on C syntax

Parallel Regions

Sample Output! Fundamental OpenMP construct:! From an 8-processor machine:" #pragma

omp parallel#pragma omp parallel{printf( “hello world from thread %d of%d\n”, omp_get_thread_num(),omp_get_num_threads() );}hello world from thread 0 of 8
hello world from thread 2 of 8
hello world from thread 3 of 8
hello world from thread 7 of 8
hello world from thread 6 of 8
hello world from thread 1 of 8
hello world from thread 4 of 8
hello world from thread 5 of 8

Another Example

Work-sharing Constructs! #pragma

double xyz[5000][3];printf( “entering parallel region\n” );#pragma omp parallel{
int tid;
tid = omp_get_thread_num();
compute_edges( tid, xyz );}printf( “parallel computation completed\n” );Master onlyThread Forks
Thread PrivateSpaceomp for" Each thread receives a portion of work toaccomplish – data parallelism! #pragma

omp section" Each section executed by a different thread –Implicit barrier,Thread join
Master only

Note: xyz is shared between all threads!

Data Parallelism Example

functional parallelism! #pragma

omp single" Serialize a section of code, only one thread

executes code block (good for I/O)

Work-sharing Scheduling! schedule(staticint a[10000], b[10000], c[10000];#pragma omp parallel#pragma omp forfor (i = 0; i < 10000; i++) {a[i] = b[i] + c[i];}No specified schedule, each thread gets a chunk of thefor loop to process
Implicit barrier at the end of the for loop, can be disabledwith the nowait clause[,chunk])" Threads get a chunk of data to iterate over! schedule(dynamic[,chunk])" Threads grab chunk iterations off work queue until all

work is exhausted! schedule(guided[,chunk])" Threads grab large chunk sizes and decreases tospecified chunk size as the computation progresses! schedule(runtime)" Use the schedule defined at runtime by theOMP_SCHEDULE environment variableFunctional Parallelism#pragma omp parallel#pragma omp sections nowait{
thread1_work();#pragma omp section
thread2_work();#pragma omp section
thread3_work();#pragma omp sectionfor (i = 0; i < 10000; i++) {quick_transform(xyz);}}Probably a good idea to equally distribute work between
sections!

Combining Work-sharing Constructs
int a[10000], b[10000], c[10000];#pragma omp parallel forfor (i = 0; i < 10000; i++) {a[i] = b[i] + c[i];}Good for single parallel loops or nested loops
Can combine parallel with sections as wellIf we had multiple for loops and did the above directive
for each one, we would have a non-optimal solution. Why?

Data Scope and Protection

Data Scope Storage Attributes! Shared memory programming! private(var," OpenMP usually defaults to shared data

! Variables declared outside of parallel

regions are implicitly carried into threads
as shared by default! Variables declared within parallel regions
are private by default! Functions called within a parallel region or
section have their own private stack space…)" Uninitialized, thread local instance of the variable! shared" Explicitly share variables across all threads! firstprivate" Initialize local instance of the variable from masterthread! lastprivate" Upon the end of the last iteration, value of the variable

is copied back out to the master thread

Data Scope Storage Attributes

ExampleInitialize x to zero! threadprivate

int x;" Global data (local file scope in C/C++ or common

blocks in Fortran) is private to each thread andpersistent throughout lifetime of program! default" For the corresponding parallel directive, variables will

be default to either the specified private or sharedscope! copyinx = 0;#pragma omp parallel for firstprivate(x)Copy value of xfor (i = 0; i < 10000; i++) {from masterx = x + i;}printf( “x is %d\n”, x );Print out value of x

Oops! The value x is undefined!

" Initialize value of threadprivate variables to the value

reported by the master thread

Need lastprivate(x) to copy value back out to master

Global Reduction

Synchronization! It is often necessary to accumulate (or! As with any parallel programming

perform some other operation) on a single
variable for all threads and return a single
value at the end of the computation! OpenMP provides a reduction directive" reduction(op:list)! op must not be overloaded! op can be +, *, -, /, &, ^, |, &&, ||" Binary bitwise operations allowed as wellinterface, there is always potential for:" Deadlocks" Race conditions! OpenMP provides synchronization

directives

Synchronization Constructs

Synchronization Constructs! critical! flush" Creates critical section, only one thread can enter at atime! atomic" Special version of critical, for atomic ops (e.g.

updating a single memory location)! barrier" Synchronization point for all threads in parallel region! ordered" Synchronization point forcing program to provide a

consistent view of memory! single" Mentioned in work-sharing construct, not a realsynchronization construct! master" Not really a synchronization construct – only themaster thread executes code block, all other threads
skip it (no implied barriers or flushes)" Forces sequential execution of the following block

Environment Variables

OpenMP Library Routines! OMP_NUM_THREADS! Always prefixed with omp_

" Sets max number of threads to use! OMP_SCHEDULE" Scheduling algorithm for “parallel for” regions! OMP_DYNAMIC" Dynamic adjustment of threads for parallel regions(TRUE, FALSE)! OMP_NESTED" Enables or disables nested parallelism (TRUE,FALSE)! Too many to list here, see references slidefor sites with an OpenMP API listingAn OpenMP Example

Extending OpenMP! Simple Monte-Carlo approximation for the! OpenMP can be used in conjunction withvolume of a sphere" x2 + y2 + z2 = 4; x, y, z >= 0

! Embarrassingly Parallel (EP) class, should

achieve good speedup: close to linear withmany iterations

distributed memory message passing! Message Passing Interface (MPI) can be used tomanage computations between shared memorymachines" For example, data sets in different files! Each SMP reads their own data file
! Performs computation on data set, returns an array ofreductions! MPI could reduce each component of the array from all SMP

machines and return a single globally reduced array

References! OpenMP: http://www.openmp.org/! Introduction to OpenMP:

http://www.llnl.gov/computing/tutorials/wor
kshops/workshop/openMP/MAIN.html! SC’99 OpenMP Tutorial:
http://www.openmp.org/presentations/inde
x.cgi?sc99_tutorial