Introduction to OpenMP
The goal of this lab is to start experimenting with OpenMP. Before starting, download this tarball.
Initialization of a team of threads
The directive #pragma omp parallel indicates that the statement or block of instructions following this directive must be executed by a team of threads. The statement or block affected by this directive is called parallel section.
- Modify hello.c program by adding a directive #pragma omp parallel to the line 3.
- Compile and run the program as follows:
gcc -o hello hello.c ./hello
- Recompile using the -fopenmp option to gcc this time. Run it several times. How many threads are used ? Compare this number with the number of logical cores of your computer. When is printed the message Bye! ?
- The OMP_NUM_THREADS environment variable allows to manage the number of threads to
be used by default. Run the program thanks to the command:
OMP_NUM_THREADS=13 ./hello
- The omp_get_thread_num function returns the identifier of the calling thread. It requires adding the OpenMP header file: #include <omp.h>. Modify the two calls to printf in order to also display the calling thread identifier. Compile and run several times the program by varying the threads number. Does the scheduling remain the same ?
- Let also print the message Bye ! by each thread by including both printings within a single parallel section. Run with a dozen of threads.
- The #pragma omp barrier directive allows to a team of threads to wait for each other at a precise line in the program. Insert this directive between the two printf calls. Compile and run the program.
Critical section
The #pragma omp critical directive implies that each thread executes alone the statement or the statement block that follows. The code protected by the critical directive is executed in mutual exclusion. Use this directive in order to avoid interleaving printing (note : remove the barrier added at the previous exercice).
Shared vs private variable
In the sharing.c program, k and i variables are declared in the main function.
The variable k is declared before the call to the parallel directive, this variable will be shared between threads: any thread in the next parallel section will be able to consult/modify this variable at will.
The variable i is declared inside the parallel section and is private to the thread: each thread will have its own copy and will not be able to modify the others.
- Compile and run the sharing.c program. You can observe that the value of k is sometimes equal to 100 000 times the number of used threads, sometimes the k++ incrementations does not seem to be executed and the final value of k changes for an un to another. Manipulate a shared variable without any care leads to an incoherent result.
- Insert a critical section in line 9 so as not to lose any incrementation. Compile and test.
For loop distribution
We aim to parallelize the following code where the calls to compute(i) are known as independant.
For that purpose, we will distribute the loop iterations among the different threads making them computed only one time. The following OpenMP code automatically makes it:
Loop index distribution policies
The #pragma omp for directive indicates that the loop indexes have to be distributed among the threads and the schedule clause precises the distribution policy to use. Four different main policies are available:
- schedule(static) divides equally indexes by the number of threads and distributes these blocks of consecutives indexes to the threads;
- schedule(static, k) cyclically distributes iterations by blocks of k indexes;
- schedule(dynamic, k) distributes iterations on demand by blocks of k indexes;
- schedule(guided, k) for those who are curious.
Study the different policies thanks to the for-loop.c program:
- After adding the #pragma omp parallel for directive in line 4, compile and run the program with 4 threads several times.
- Modify the program with different distribution policies. Use the following command:
to visualize easily the work of each thread.OMP_NUM_THREADS=4 ./boucle-for | sort -n -k 3
We have seen that it is necessary to protect access to shared variables. This can be done using critical sections but also using atomic instructions. An atomic section is a critical section reduced to a single instruction. We will compare the cost of different protection techniques on the following code:
Replace the TODO in the sum.c program with the following techniques:
- section #pragma omp parallel for where the shared variable sum is accessed in a critical section;
- section #pragma omp parallel for where the shared variable sum is accessed in a atomic section #pragma omp atomic;
- use of a local variable my_sum in which each thread accumulates values on its own during the loop, then adds its contribution to sum all at once;
- reduction #pragma omp parallel for reduction (+:sum): the compiler transforms the program to introduce a local variable in order to minimize the time spent in the critical section.
easypap
EasyPAP
We are now going to look at programs that manipulate images, which are 2 dimensional arrays containing pixels.
To facilitate development, we're going to use an environment called EasyPAP, which allows you to display images, launch calculations and interactively visualize image changes at each iteration.
To retrieve EasyPAP, connect to the starfighter cluster, and clone the git repository:
Documentation is available here: https://gforgeron.gitlab.io/easypap/
If successful, you should observe an animated image when typing:
Getting started
The kernel/c/spin.c file contains several variants of the spin kernel. Let begin by modifying (temporarily) the sequential variant in order to understand how the image is browsed.
Apply the next modification (Figure 1, line 7) in the code of spin_compute_seq function.
Recompile, run the kernel and verify the effect of the modification:
Now let's study the tiled variant (Figure 2), that virtually subdivides the image in tiles of size TILE_W × TILE_H pixels.
The do_TILE(int x, int y, int w, int h) function takes in charge the computation of pixels in the rectangle defined by the parameters. This function is basically a switch whose default branch is the spin_do_TILE_default function.
Apply the modification shown in Figure 2, line 7 in the code of the spin_compute_tiled function. Recompile and verify the effect on the display:
Vary the tile size choosing values in power of two thanks to the --tile-size (or -ts) option. For instance, launch:
You can also define rectangular tiles with options --tile-width and --tile-height:
The option --monitoring (or -m) opens monitoring windows that show the activity of each threads and the area on which they compute:
Take a moment to contemplate... then remove the line 7.
First step with OpenMP
The next step is to write parallel versions of the kernel spin using OpenMP.
To do this, copy the function spin_compute_tiled to a new variant called spin_compute_omp.
Apply the modifications shown, recompile and test your newly parallel version:
What do you observe? Try different tile size.
You can also modify the threads number used by OpenMP thanks to the OMP_NUM_THREADS environment variable. For instance:
Work distribution visualization
You are now in a position to experiment different for loop index scheduling strategies by observing the distribution of pixels per CPU on the tile monitoring window.
For example, you can add the clause schedule(static, 1), recompile, and view the change by restarting:
To play with all scheduling strategies without necessarily recompile the code between each run, you can use the schedule(runtime) inline clause, which allows you to specify the strategy to be used via the environment variable OMP_SCHEDULE. So, once the code has been recompiled, you can run sequentially:
OMP_SCHEDULE=static,1 srun --x11 --account=csc_5001 --partition=starfighter --qos=normal --time=00:10:00 --cpus-per-task=8 ./run -k spin -v omp -m -ts 1
OMP_SCHEDULE=dynamic srun --x11 --account=csc_5001 --partition=starfighter --qos=normal --time=00:10:00 --cpus-per-task=8 ./run -k spin -v omp -m -ts 1
Speedup
To determine the speedup achieved, i.e. the gain obtained by from a sequential to a multithreaded version, we first precisely measure the time obtained by each version by disabling display (option --no-display or -n). For example:
In this example, the speedup is 6203/841 ≈ 7.375. Calculate your own.
Column parallelization
Move your #pragma omp parallel for just before the for (int x) loop and recompile. Observe that the work repartition is now done by column:
To find out whether this version is more efficient than parallelization by line, perform a comparable time measurement (in number of iterations) with previous experiments.
For a fair comparison, put a #pragma omp parallel before the loop for (int y) and use only #pragma omp for in front of the loop for (int x) loop. For instance, test:
Do the results vary if a cyclic distribution is used? Test:
Collapse
Duplicate the spin_compute_omp function to create a function spin_compute_omp_tiled. Modify the code by adding the clause
Duplicate the spin_compute_omp function to create a function spin_compute_omp_tiled.
Modify the code by adding the clause collapse(2) to the OpenMP for directive. The collapse(n) clause allows to distribute n-tuples of indices rather than one-dimensional indexes by collapsing n nested loops.
Observe the influence of this clause on tile distribution by varying the the distribution policy.
