Newer
Older
# MergeSort benchmark
## Description
Merge Sort is a recursive sorting algorithm based on comparisions.
## Versions
We have several implementations of this benchmark:
* **01.mergesort_seq:** sequential version of this benchmark.
* **02.mergesort_outline_task:** Parallel version of the benchmark using the *task* construct on functions and the *taskwait* construct to synchronize between tasks.
* **03.mergesort_inline_task:** Parallel version of the benchmark using the *task* construct on code statements and the *taskwait* construct to synchronize between tasks.
* **04.mergesort_outline_task_dep:** Parallel version of the benchmark using the *task* construct on functions and fine-grained dependences to synchronize between tasks.
* **05.mergesort_task_loop_dep:** Version based on the previous one that also parallelize the copy of temporary arrays with a *loop*.
* **06.mergesort_task_loop_wait:** Version based on the previous one but uses the *wait* clause to wait for the *loop*.
## Execution instructions
./mergesort N BLOCK_SIZE
where:
1. N is the number of elements to be sorted. Mandatory for all versions of this benchmark.
2. BLOCK_SIZE is used to determine the threshold when the task becomes *final*. If the array size is less or equal than BLOCK_SIZE, the *task* will become final, so no more task will be created inside it. Mandatory for all versions of this benchmark.
## References
https://en.wikipedia.org/wiki/Merge_sort