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
- Download quicksort.c, compile it and execute it.
- Run it for increasing array size and measure the execution time.
- What do you observe ?
- Explain this (strange) behaviour
- Infer that some professors should not be trusted.
- 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).
- OpenMP supports nested parallelism. Active it using the omp_set_nested method. How many threads are created ?
- What happens if you force the number of threads to 1 ?
- 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.
- Add a dry run on a small array to force the creation of threads by OpenMP.
- Modify your code so that the
omp parallel sections pragma is only used once. - Compare the new execution time to the previous versions.
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.