Lab session 2

Parallel sections

In this exercise we will study a new OpenMP construct called parallel sections. It can be added to your code using two pragmas : omp parallel sections and omp parallel section

1. Download quicksort.c, compile it and execute it.
   1. Run it for increasing array size and measure the execution time.
   2. What do you observe ?
   3. Explain this (strange) behaviour
2. Infer that some professors should not be trusted.
3. Modify the quicksort method so that recursive calls are done in parallel using the parallel sections. How many threads are created when sorting ? (use ps -L on Linux, ps -M on Mac, top -H or htop).
4. OpenMP supports nested parallelism. Active it using the omp_set_nested method. How many threads are created ?
5. What happens if you force the number of threads to 1 ?
6. Compare the execution time of the sequential and parallel versions for different sizes of array.

The OpenMP version is slower because of the cost of creating threads and also entering/exiting parallel sections.

1. Add a dry run on a small array to force the creation of threads by OpenMP.
2. Modify your code so that the omp parallel sections pragma is only used once.
3. Compare the new execution time to the previous versions.

Parallel prefix

In this exercise you have to implement the parallel prefix computation as seen during lectures. The program will start from a source array of size n and will build the intermediate arrays to compute b such that

b[k] = source[0] + source[1] + ... + source[k]

You can use the following base for the implementation.