Chapter 5 - OpenMP

Question 1

What is OpenMP?

Answer 1

API for shared memory MIMD programming

Open Multi-Processing

View a system using OpenMP as a collective of autonomous cores, all having access to the same memory.

Question 2

What are some differences between omp and pthreads?

Answer 2

Both are standard APIs for shared-memory programming.

Pthread needs the programmer to explicitly define the behaviour of threads. In omp the programmer can just let the program know that a specefic block of code will be executed by threads. The compiler and run-time system defines the specifics of the thread use.

Pthread is a library, but OMP needs compiler support in addition

Pthread pros: lower level, gives opportunity to program virtually any possible thread behaviour

Pthread Cons: Need to specify every detail of thread behaviour - more difficult to implement

Pros OMP: Simpler to implement - runtime and compiler takes care of the details.

Cons OMP: Some lower level thread behaviour may be more difficult to implement

Question 3

What is a directives-based shared-memory API?

Answer 3

There are special preprocessor instructions know as pragmas.

Question 4

What are pragmas?

Answer 4

Added to a system to allow behaviour that aren’t part of the basic C specifications.

Not all compilers support pragmas, and will ignore them.

compilator discovers these during its initial scan. If it understands the text, their functionality is implemented, if not, they are ignored.

Question 5

How are omp pragmas defined ?

Answer 5

pragma omp

Question 6

What is the header file of omp?

Answer 6

include <omp.h></omp.h>

Question 7

List omp directives and what they do

Answer 7

pragma omp parallel

Specifies that the structured block of code that follows, should be executed by multiple threads. Number of threads started is determined by run-time system (typically one thread per core, but algorithm for deciding this is quite complicated).

parallel directive + num_threads clause to specify number of threads. System can’t guarantee that n_threads will be started, because of system limits, but most of the time it will.

Directive that tells the compiler that we need a mechanism to ensure the following block of code is accessed mutually exclusive by threads - only one thread at a time

Parallel for directive forks a team to execute the following block. This structured block must be a for-loop.

Only master thread reaches within this block

Question 8

What is a clause in omp?

Answer 8

Just some text that modifies a directive

Question 9

What is a team in omp?

Answer 9

The collection of threads executing the directive(parallel) block

original thread + (n-1) new threads

Question 10

What happens when #pragma omp parallel is used?

Answer 10

From the start, the program is running a single thread.

When the directive is reached, the original thread continues execution. Then n-1 additional threads are started.

Each thread executes the following block of code in parallel.

When this block is completed, there is an implicit barrier. A thread that has completed the block will wait for all other threads in the team to complete. The children will then terminate and the parent continues executing the following code.

Question 11

Define these terms in omp:

master, parent, child

Answer 11

master: first thread of execution, thread 0

parent: thread that encountered parallel directive and started a team of threads. This is often the master thread.

child: Each thread started by parent

Question 12

What data does a child thread have access to

Answer 12

ID: rank, omp_get_thread_num();

number of threads in team: omp_get_num_threads();

Stack, and therefor local variables

Question 13

How are critical sections handled in omp to avoid condition variables?

Answer 13

pragma omp critical

Following code block is accessed by one block at the time.

Question 14

What is varible-scope in omp?

Answer 14

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

Shared scope: Accessible by all threads
Private scope: Accessible by a single thread

Question 15

What is the default scope of variables declared outside a parallel block, and within?

Answer 15

Outside: Global

Within: Private

Question 16

What is a reduction variable in openmp?

Answer 16

A reduction operator is a binary operation (e.g. add, mul)

A reduction is a computation that repeatedly applies the same reduction operator to sequence of data to get a single result.

A reduction variable is where all the intermediate results of the operation are stored.

Question 17

How can reduction be used in omp?

Answer 17

pragma omp parallel reduction(+: global_result)

Add reduction clause to parallel directive

This specifies that the global_result is the reduction variable.

What happens is that omp creates private variables for each thread, and run-time stores each thread’s result in this variable. Omp then creates a critical sections and adds all the private variables together.

The private values are initialized to the identity value of the operator:
+ : 0
- : 0
* : 1
&& : 1
…and so on

Question 18

When is it beneficial to use reduction?

Answer 18

When a function call happens within a critical section, it will be serialized. But using reduction avoids this serialization.

Question 19

How are for-loops parallelized using the parallel for-directive

Answer 19

Iterations are divided between the threads. The default partitioning of the iterations is done by the system, where in normal parallel directive, the work is partitioned by the threads themselves.

In for loops, a normal partitioning is giving the first m/n_threads iterations to thread 0, and the the next m/n_thread to 1, and so on.

Compiler does not check for dependences between the iterations. This can cause error during execution, programmer needs to take care of this.

Question 20

What are the default scope of loop variables in a parallel for directive?

Answer 20

private

Question 21

What types of for loops can be parallelized?

Answer 21

Only loops with canonical form

Not while, do-while

Only for-loops where the number of iterations can be determined from the loop statement itself (i: i<n: i++) and prior to execution of loop

Loops that are infinite, or that has conditional breaks in them cannot

Question 22

What is a canonical form of a loop?

Answer 22

Loops where number of iterations can be determined prior to the execution of the loop.

Question 23

What is a loop-carried dependence?

Answer 23

A dependence between loop iterations where a value is calculated in one iteration, and the result is used in a subsequent iteration.

Question 24

What is the private clause?

Answer 24

pragma omp parallel for private(var_name)

Creates a copy of the global variable var_name and gives it a private scope

Question 25

What is the default clause?

Answer 25

pragma omp for default(none) reduction(+: global_sum) private(x, factor) shared(n)

Default(none) requires us to explicitly define the scope of variables used in the block, that was defined outside it.

Question 26

What does the for directive do, and why is it useful?

Answer 26

pragma omp for

Does not fork any new threads, but uses already-forked threads in the coming for-loop block.

If threads are created earlier in the program, and then used in the for loop, it saves overhead by not creating new threads for the for loop.

… code …

for(…){}

Question 27

What does the schedule clause do?

Answer 27

pragma omp parallel for schedule(<type> [, <chunksize>])</chunksize></type>

Clause specifies how iterations are to be assigned to threads in a for or parallel for directive.

chunksize: A number of iterations executed consecutively in a serial loop. Only used in static, dynamic and guided

Types:
static: Iterations assigned before loop is executed

dynamic/guided: Iterations assigned while loop is running. After a thread completes, it can request more iterations

auto: compiler/run-time decides schedule, good guess when elements have more equal workload

runtime: Schedule determined at run-time by environment variable

Question 28

What is the static schedule type?

Answer 28

Chunks of chunksize iterations to each thread in a round-robin fashion

Example:
12 iterations, 3 threads

(static, 2):

thread 1: [0, 1], [6, 7]
thread 2: [2, 3], [8, 9]
thread 3: [4, 5], [10, 11]

Question 29

What is the default schedule type often?

Answer 29

schedule(static, iterations/num_threads)

Question 30

When should you use the different scheduling types?

Answer 30

Static: When each iterations takes roughly the same time to execute

Dynamic: Iterations takes different times to compute

Guided: Improves balance between loads when later iterations are more compute heavy

Question 31

What is the dynamic schedule?

Answer 31

Iterations broken into chunksized chunks.

Each thread execute a chunk, and then requests a new one.

First-come, first-served assignment of chunks

A bit more overhead of dynamically assigning chunks. Larger chunk size helps with this

Question 32

What is the guided schedule?

Answer 32

Similar to dynamic.

But as chunks are completed, the chunk size decreases.

If no chunksize is specified, the chunksize will eventually decrease down to 1. If specified, decreases to chunksize.
Last chunk may be less.

Question 33

What is the runtime schedule?

Answer 33

Uses environment variable OMP_SCHEDULE.

This var can take any of the static, dyn., or guided values.

You can modify this variable to try out the performance of different scheduling types.

Question 34

How does omp use barriers?

Answer 34

pragma omp barrier

Question 35

What is the atomic directive?

Answer 35

pragma omp atomic

omp assumes the computers architecture has some range of atomic operations.

Only used at critical sections consisting of a single C assignment statement of the following form:

var <op>= <expression>;
var++;
\++var;
var--;
--var;</expression></op>

Expression must not reference <op></op>

A thread will complete the expression before any other threads starts executing it.

A critical section only performing a load-modify-store can benefit from this, as a lot of hardware is optimized for atomic load-stores.

Question 36

What does the critical(name) directive do?

Answer 36

Two blocks protected by critical directives with different names, can execute in parallel.

Question 37

How are locks used in omp?

Answer 37

Pseudo code:

initialize lock (one thread)

// Multiple threads
attempt to lock - block until ready
critical section
unlock

Destroy lock (one thread)

2 types: simple- and nested locks

Question 38

What are simple locks?

Answer 38

Can only be set once before it is unset

Question 39

What are nested locks?

Answer 39

Can be set multiple times by same thread before unset

Question 40

What is the omp task directive?

Answer 40

pragma omp task

default scope for variables in tasks is private.

Specifies units of computations.

When the program reaches this, a new task is generated by the omp run-time, that will be scheduled for execution, not necessarily immediately.

Tasks must be launched within a parallel block, but this is generally done by only one thread in the team.

Question 41

What is a common structure of task-programs?

Answer 41

pragma omp parallel ; creates a team of threads

#pragms omp single ; instruct run-time to only launch 1 thread
{
#pragma omp task
}

If single is not used, all of the threads would launch multiple times

Question 42

What is the taskwait directive?

Answer 42

pragma omp task shared(j)

Operates as a barrier for tasks.

Makes a task wait for all its sub-tasks to complete

j = 1 + 2

result = j + 1

Question 43

Howcan we create conditional tasks?

Answer 43

pragma omp task shared(i) if (n > 20)

i = func(n)

if i weren’t set to shared, it would have private scope

Question 44

Why does omp not use signals (condition variables)

Answer 44

OpenMP threads aren’t supposed to be sleeping, and critical sections should be held short as they use busy waiting

Question 45

What are worksharing directives?

Answer 45

Directives that can split a given workload between threads for you.

Have an implicit barrier at the end

Question 46

What is functional decomposition?

Answer 46

When work is split by the function of its sub-tasks

e.g. pipelining

Question 47

What is data decomposition?

Answer 47

Split work by input/output of its sub-tasks

Every threads does the same thing

Question 48

What are sections?

Answer 48

pragma omp section

Each section only run by one thread

Question 49

What does the clause nowait do?

Answer 49

Skip the barrier at the end of worksharing directives

Question 50

What does the clause firstprivate(var) do?

Answer 50

If var was shared, and you are privitizing it, its initial state is given to all the private copies

Question 51

What does lastprivate(var) do?

Answer 51

When threaded region finishes, one of the private copies are stored back into the shared copy

Question 52

What are the trade offs between small and big units of work when scheduling iterations in omp for?

Answer 52

Big:
- less scheduling to do
- limit on how big blocks can be
- if an entire iteration space is one block - there is no parallelisation

small:
- more disruptions in memory access pattern, more units to distribute
- greater flexibility to assign work to unemployed threads

Question 53

What is the blocksize attribute in schedule()

Answer 53

The minimal number of iterations handed to a thread

Question 54

What is the master/worker pattern?

Answer 54

Way to implement worksharing in queued systems

Keep active thread pool of available worker threads

Keep a queue of finite work packages

assign next package in the queue every time a threads becomes available

Question 55

What is nested parallelism?

Answer 55

One work-package spawns more wor-packages that should be distributed amongst threads

Question 56

What is task-based programming?

Answer 56

Alternative way for parallel programming. Generates dependency graphs

take block of work and dispatch it for background execution

record which blocks depend on the others

Assign blocks to the team of threads in anorder that matches their dependencies

Question 57

What does the omp task directive do?

Answer 57

pragma omp task

Creates arbitrary dependency graphs

Block context queued internally, to be executed at first opportunity

Wait for task:
#pragma omp taskwait

Question 58

How can you task-ify functions?

Answer 58

pragma omp task

void some_func(int arg1, int arg2)
{
// function body
}

Every call to this will create background tasks

Question 59

What does #pragma omp taskloop do?

Answer 59

Automates making a task out of every iteration in a loop