![](\"figures/par_arch.png\")
"]},{"cell_type":"markdown","metadata":{},"source":["![](\"figures/numa.png\")
"]},{"cell_type":"markdown","metadata":{},"source":["![](\"figures/procs_history.png\")
"]},{"cell_type":"markdown","metadata":{},"source":["![](\"figures/openmp_logo.png\"){kind=logo}
"]},{"cell_type":"markdown","metadata":{},"source":["![](\"figures/forkjoin.png\")
"]},{"cell_type":"markdown","metadata":{},"source":["A\n","slightly more complex hello world example in OpenMP
"]},{"cell_type":"markdown","metadata":{},"source":["Just a simple hello world with multiple threads:
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
start with serial execution
\n","open a parallel region where:
\n","- \n","
- each thread reads its identifier and the total number of threads\n","using, respectively, the
omp_get_thread_num()and\n","omp_get_num_threads()\n"," - prints a message \n","
\n","- each thread reads its identifier and the total number of threads\n","using, respectively, the
Parallel region: how many\n","threads?
"]},{"cell_type":"markdown","metadata":{},"source":["How many threads do we have in the parallel regions of a code? The\n","number of threads depends on:
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
Evaluation of the
ifclause (one or many) \n","Setting of the
num_threadsclause \n","Use of the
omp_set_num_threads()library\n","function \n","Setting of the
OMP_NUM_THREADSenvironment\n","variable \n","Implementation default - usually the number of CPUs on a node,\n","though it could be dynamic
\n","
Parallel region: how many\n","threads?
"]},{"cell_type":"markdown","metadata":{},"source":["Complete example
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeHello world with a bug
"]},{"cell_type":"markdown","metadata":{},"source":["Here is a minor variant of the hello world program…with a bug
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeData sharing 1/2
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
Most variables are shared by default
\n","Global variables include:
\n","- \n","
- Fortran: COMMON blocks, SAVE and MODULE variables \n","
- C: File scope variables, static \n","
\n","Private variables include:
\n","- \n","
- Loop index variables (in !$OMP DO) constructs \n","
- Stack variables in subroutines called from parallel regions \n","
\n","Fortran: Automatic variables within a statement block
\n","The OpenMP Data Scope Attribute Clauses are used to explicitly\n","define how variables should be scoped. They include:
\n","- \n","
private\n","firstprivate\n","shared\n","default\n","reduction\n","
\n","
Data sharing 2/2
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
private(list): a new object of the same type is\n","created for each thread (uninitialized!) \n","firstprivate(list): Listed variables are initialized\n","according to the value of their original objects prior to entry into the\n","parallel or work-sharing construct. \n","lastprivate(list): The value copied back into the\n","original variable object is obtained from the last (sequentially)\n","iteration or section of the enclosing construct. \n","shared(list): only one object exists in memory and\n","all the threads access it \n","default(shared|private|none): sets the default\n","scoping \n","reduction(operator:list): performs a reduction on\n","the variables that appear in its list. \n","
Hello world bugfix
"]},{"cell_type":"markdown","metadata":{},"source":["Let's fix the bug: by declaring iam private, each thread\n","will have its own copy of this variable
Work distribution and\n","sharing
"]},{"cell_type":"markdown","metadata":{},"source":["Dependencies
"]},{"cell_type":"markdown","metadata":{},"source":["Dependencies
"]},{"cell_type":"markdown","metadata":{},"source":["The interest of parallel programming is not to execute the same\n","workload multiple times but to distribute the workload to the available\n","processes so that execution time can be reduced. This implies that\n","multiple instructions will be executed concurrently\n","(or, equivalently, in parallel).
"]},{"cell_type":"markdown","metadata":{},"source":["Two successive statements S1 and S2 can be executed concurrently if\n","they are independent. According to the\n","Bernstein conditions there exist three types of\n","dependencies:
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
Read-After-Write or true\n","dependency or flow dependency: if\n","
Input(S2)overlaps withOutput(S1)\n","Write-After-Read or\n","anti-dependency: if
Output(S2)overlaps\n","withInput(S1)\n","Write-After-Write or output\n","dependency: if
Output(S2)overlaps with\n","Output(S1)\n","
Dependencies
"]},{"cell_type":"markdown","metadata":{},"source":["Example. Are these two statements independent?
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeWhat kind of dependency is there? RAW. Here is a more convoluted\n","example
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeExample. Are these two statements independent?
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeWhat kind of dependency is there? WAR. Note that WAR dependencies can\n","be sometimes removed!
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeNow the second and third statement have become independent. Here is a\n","more convoluted example
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeExample. Are these two statements independent?
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeWhat kind of dependency is there? WAW. Here is a more convoluted\n","example
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeThe master directive identifies a code block which is\n","only executed by the master thread
Single
"]},{"cell_type":"markdown","metadata":{},"source":["The single directive identifies a code block which is\n","only executed by one (any) thread
Single vs master
"]},{"cell_type":"markdown","metadata":{},"source":["One obvious difference between single and\n","master is that with master only the thread\n","with id 0 can execute the code block. This has a risk: you have to make\n","sure that the master thread passes by that code block otherwise it will\n","never be executed.
Can you spot any other difference from executing the two code blocks\n","above? There is an implied barrier at the end of the\n","single block. It can be removed using the\n","nowait clause
Parallel loops
"]},{"cell_type":"markdown","metadata":{},"source":["Parallel
"]},{"cell_type":"markdown","metadata":{},"source":["In the code below, all the iterations in the loop are\n","independent. This means that they can be executed\n","concurrently. However the code below is wrong because\n","it does not produce the same result as in sequential
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeOpenMP provides a construct that automatically parallelizes loops by\n","executing chunks of iterations concurrently. Note that the loop index\n","i is implicitly private.
The schedule clause in the for construct\n","specifies how the iterations of the loop are assigned to threads:
- \n","
static: loop iterations are divided into pieces of\n","size chunk and then statically assigned to threads in a round-robin\n","fashion \n","dynamic: loop iterations are divided into pieces of\n","size chunk, and dynamically scheduled among the threads; when a thread\n","finishes one chunk, it is dynamically assigned another \n","guided: for a chunk size of 1, the size of each\n","chunk is proportional to the number of unassigned iterations divided by\n","the number of threads, decreasing to 1. For a chunk size with value k\n","(greater than 1), the size of each chunk is determined in the same way\n","with the restriction that the chunks do not contain fewer than k\n","iterations \n","runtime: The scheduling decision is deferred until\n","runtime by the environment variable OMP SCHEDULE \n","
Schedule
"]},{"cell_type":"markdown","metadata":{},"source":["Let's see how schedule works:
Collapse
"]},{"cell_type":"markdown","metadata":{},"source":["The collapse clause allows for combining multiple loops\n","into a single one and for parallelizing its iterations. The number of\n","loops to collapse can be provided as an option
Threads synchronization
"]},{"cell_type":"markdown","metadata":{},"source":["Barriers
"]},{"cell_type":"markdown","metadata":{},"source":["Barrier
"]},{"cell_type":"markdown","metadata":{},"source":["A barrier is simply a waiting point: all threads must wait for all\n","the others to reach a barrier point before moving on. Example
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeBarrier
"]},{"cell_type":"markdown","metadata":{},"source":["Improper use of barriers can cause deadlocks: if not\n","all threads pass by the barrier, those who do will be waiting\n","forever…
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeCritical sections
"]},{"cell_type":"markdown","metadata":{},"source":["Critical
"]},{"cell_type":"markdown","metadata":{},"source":["The critical directive identifies a code block which is\n","executed in mutual exclusion by all threads, i.e., one\n","at a time.
Critical scope
"]},{"cell_type":"markdown","metadata":{},"source":["Critical sections can have names. The name argument is used to\n","identify the critical construct. For any critical construct for which\n","name is not specified, the effect is as if an identical (unspecified)\n","name was specified. It is not possible to have two or more threads in\n","different critical regions that have the same name!
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeAtomic instructions
"]},{"cell_type":"markdown","metadata":{},"source":["Atomic
"]},{"cell_type":"markdown","metadata":{},"source":["The atomic construct ensures that a specific storage location is\n","accessed atomically so that possible simultaneous reads and writes by\n","multiple threads do not result in indeterminate values. Five types of\n","atomic constructs exist: read, write,\n","update, capture and compare
- \n","
read: atomically read a memory location, i.e.,\n","xcan not change while being read \n","
Atomic
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
write: atomically write a memory location \n","update: atomically update (i.e. read-modify-write) a\n","memory location \n","
So what's the interest of atomic? take this example: we could\n","certainly use critical to protect the update of\n","x[] but this would prevent calls to\n","compute_one to be executed concurrently. With\n","atomic only the update of x[] is\n","serialized.
- \n","
capture: atomically update a memory location and\n","capture its initial or final value \n","
Atomic
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
compare: atomically and conditionally update a memory\n","location \n","
Reductions
"]},{"cell_type":"markdown","metadata":{},"source":["Assume this simple code that computes the sum of all the elements of\n","an array
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includesum. We could actually use a critical section or\n","an atomic update but we would loose all performance."]},{"cell_type":"markdown","metadata":{},"source":["Reductions
"]},{"cell_type":"markdown","metadata":{},"source":["Reductions allow us to take advantage of\n","associativity and commutativity of some operators (+ in this case):
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeReductions
"]},{"cell_type":"markdown","metadata":{},"source":["For the C language, predefined reduction operators are\n","(note that : in the table below is actually a | )
| Operator | \n","Initializer | \n","Combiner | \n","
|---|---|---|
| + | \n","omppriv=0 | \n","ompout += ompin | \n","
| * | \n","omppriv=1 | \n","ompout *= ompin | \n","
| ~ | \n","omppriv=~0 | \n","ompout ~= ompin | \n","
| : | \n","omppriv=0 | \n","ompout := ompin | \n","
| ^ | \n","omppriv=0 | \n","ompout ^= ompin | \n","
| && | \n","omppriv=1 | \n","ompout = ompin &&\n","ompout | \n","
| :: | \n","omppriv=0 | \n","ompout = ompin :: ompout | \n","
| max | \n","omppriv=minval | \n","ompout = max(ompin,ompout) | \n","
| min | \n","omppriv=maxval | \n","ompout = min(ompin,ompout) | \n","
Tasks
"]},{"cell_type":"markdown","metadata":{},"source":["Task
"]},{"cell_type":"markdown","metadata":{},"source":["The OpenMP task construct simply identifies a block of\n","code which is ready to be executed and whose execution is\n","deferred. Once the task is created, it can be executed\n","by any thread, at any time. This means that we can not\n","make any assumptions on when a task is executed and by which thread and\n","in which order all the created tasks are executed.
Why do we need the master construct in the code\n","above?
Task data
"]},{"cell_type":"markdown","metadata":{},"source":["A slightly more complex example, with a bug:
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeWhat went wrong?
"]},{"cell_type":"markdown","metadata":{},"source":["Task data
"]},{"cell_type":"markdown","metadata":{},"source":["The value of shared variables accessed within a task might change\n","between the creation of the task and its actual execution. Some clauses\n","can be used to define the scope of variables within tasks:
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
shared(x)means that when the task is executed x is\n","the same variable (the same memory location) as when the task was\n","created \n","firstprivate(x)means that x is private to the task,\n","i.e., when the task is created, a brand new variable x is created as\n","well and its value is set to be the same as the value of x in the\n","enclosing context at the moment when the task is created. This new copy\n","is destroyed when the task is finished \n","private(x)means that x is private to the task,\n","i.e., when the task is created, a brand new variable x is created as\n","well. This new copy is destroyed when the task is finished \n","
If a variable is private in the parallel region it is\n","implicitly firstprivate in the included tasks
Task data
"]},{"cell_type":"markdown","metadata":{},"source":["A slightly more complex example, with a bugfix:
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeTask if
"]},{"cell_type":"markdown","metadata":{},"source":["Creating and handling tasks has a cost. Therefore, it is not always\n","worth creating a task, for example, if the task has only little work to\n","do. The if clause can be used to choose whether to create a\n","task or immediately run the code block
Taskwait
"]},{"cell_type":"markdown","metadata":{},"source":["So how can we be sure that some tasks are actually executed? The\n","taskwait directive ensures that all the previously\n","submitted tasks have been executed. Note that this does not include\n","descendants, i.e., tasks that have been generated by other tasks.
Task dependencies
"]},{"cell_type":"markdown","metadata":{},"source":["It is possible to define an execution order by specifying task\n","dependencies. This is done through the\n","depend clause and the Bernstein conditions:
- \n","
The
independence-type. The generated task will be a\n","dependent task of all previously generated sibling tasks that reference\n","at least one of the list items in anoutor\n","inoutdependence-type list. \n","The
outandinoutdependence-types. The\n","generated task will be a dependent task of all previously generated\n","sibling tasks that reference at least one of the list items in an\n","in,out, orinoutdependence-type\n","list. \n","
Task dependencies
"]},{"cell_type":"markdown","metadata":{},"source":["Example:
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeCan you draw the dependency graph?
"]},{"cell_type":"markdown","metadata":{},"source":["Task priorities
"]},{"cell_type":"markdown","metadata":{},"source":["Assuming only two threads are available and all functions take one\n","second, the following two schedulings are possible.
"]},{"cell_type":"markdown","metadata":{},"source":["![](\"figures/sched.png\")
"]},{"cell_type":"markdown","metadata":{},"source":["Task priorities
"]},{"cell_type":"markdown","metadata":{},"source":["The priority clause can be used to give the OpenMP\n","scheduler a hint on the importance of a task
Task dependencies and\n","pointers
"]},{"cell_type":"markdown","metadata":{},"source":["When using pointers to specify dependencies, you should dereference\n","it to make sure the dependence is inferred from the pointed data rather\n","than the pointer variable.
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeLocks
"]},{"cell_type":"markdown","metadata":{},"source":["Locks
"]},{"cell_type":"markdown","metadata":{},"source":["A lock is a data of type omp_lock_t which can be used to\n","prevent simultaneous access to shared resources according to the\n","schema
- \n","
acquire (or set or lock) the lock
\n","access data
\n","release (on unset or unlock) the lock
\n","
Acquisition of the lock is exclusive in the sense that only one\n","threads can hold the lock at a given time. A lock can be in one of the\n","following states:
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
uninitialized: the lock is not active and cannot\n","be acquired/released by any thread;
\n","unlocked: the lock has been initialized and can\n","be acquired by any thread;
\n","locked: the lock has been acquired by one thread\n","and cannot be acquired by any other thread until the owner releases\n","it.
\n","
Locks
"]},{"cell_type":"markdown","metadata":{},"source":["Transitions through states can be achieved with the following\n","routines
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
omp_init_lock: initializes a lock \n","omp_destroy_lock: uninitializes a lock \n","omp_set_lock: waits until a lock is available, and\n","then sets it \n","omp_unset_lock: unsets a lock \n","omp_test_lock: tests a lock, and sets it if it is\n","available \n","
Locks
"]},{"cell_type":"markdown","metadata":{},"source":["Example
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeLocks
"]},{"cell_type":"markdown","metadata":{},"source":["Example with test lock
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeMistakes to avoid
"]},{"cell_type":"markdown","metadata":{},"source":["Add useless loops
"]},{"cell_type":"markdown","metadata":{},"source":["Do not create a new loop just for the purpose of parallelizing it
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#includeUse tasks with caution
"]},{"cell_type":"markdown","metadata":{},"source":["![](\"figures/rambo.jpg\")
"]},{"cell_type":"markdown","metadata":{},"source":["Tasks have a relatively high overhead and should be\n","used with caution.
"]},{"cell_type":"markdown","metadata":{},"source":["- \n","
- creating a task for a few operations is probably a very bad\n","idea \n","
- try to combine as many operations as possible into a single task as\n","long as this does not reduce parallelism \n","
Minimize critical sections
"]},{"cell_type":"markdown","metadata":{},"source":["Critical sections serialize the work of processes.
"]},{"cell_type":"code","execution_count":null,"metadata":{},"outputs":[],"source":["//%cflags:-fopenmp\n","#include- \n","
- separate what really needs to be in the critical section from what\n","can be done in parallel \n","
- sometimes atomic instructions can be used instead of critical \n","
Don't forget the parallel\n","section
"]},{"cell_type":"markdown","metadata":{},"source":["Stupid to say but there is no parallelism if you don't put a parallel\n","section somewhere. Just don't forget.
"]},{"cell_type":"markdown","metadata":{},"source":["Conversely, if you can merge multiple parallel sections into a single\n","one, it might be good to do so in order to reduce overhead
"]},{"cell_type":"markdown","metadata":{},"source":["