Lab 3 OMP Tasks: Merge Sort

Study the OMP tasks lecture. see the steps in the nfib code discussed in that lecture. Download and untar the provided tasks.tar file. This is the starting point for your experiments.

Time sequential code

Start by running the sequential version on a quiet veggie machine. Run it a few times, and get a median run time for this. You can test your code by running it with a small input size, e.g., Merge_sort_debug 100. For all timing experiments run your codes with the default (no explicit size on the command line) size of 100,000,000.

Make it parallel

Now, copy the sequential Merge_sort.c code into Merge_sort_parallel.c to make this code parallel, using OMP task parallelism. Spawn two new tasks, one for each recursive mergesort call. Adjust your Makefile.

Keep in mind: the pragma parallel should only be executed once. Also, don't merge the left and right halves of the array until they are sorted, i.e. you need a taskwait.

First parallel version: no pruning

Do not prune the task tree yet. Call this code Merge_sortNP (for not pruned). Run the parallel code for 1, 2, 3, 4, 5, 6, 7, 8 threads. See how the run times compare to the sequential version. Why do you think you are getting the results you are? Think about how many tasks are spawned. Bring this to the discussion on this topic (later).

Second parallel version: pruning

Now prune your code by only spawning sufficiently large tasks. Call this code Merge_sortP. Run the parallel code for 1, 2, 3, 4, 5, 6, 7, 8 threads. Experiment with tasks sizes and create a speedup curve for your preferred task size. See how the run times compare to the sequential and unpruned versions. Think about how many tasks are spawned now. Bring your observations to the discussion on this topic.

Third parallel version: spawning only one task

Now change your code to spawn only one task for one of the recirsive calls, and let the other recursive call be done by the parent task. Call this code Merge_sortS. Experiment with it. What are your observations? Summarize your observations to take to the discussion on OMP Tasks.