Lab 2 OMP Tasks: Merge Sort

If needed be remind yourself what merge sort is with these fun animations

1. Time sequential code

   1. Start by running the sequential version on a quiet state capital machine (Albany to Trenton in the list)
      Run it a few times, and get a median run time for this.
   2. 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.

2. Make it parallel

   1. Copy the sequential Merge_sort.c code into Merge_sort_parallel.c.
   2. Use OMP task parallelism to parallelize Merge_sort_parallel.c (leave Merge_sort.c alone for reference).
   3. Use an OMP parallel pragma to spawn threads in the main program. This is similar to the nfib(n) example given in the tasks lecture.
   4. Spawn two new tasks, one for each recursive mergesort call.
   5. Adjust your Makefile. Make sure that you use -O3 flag to compile all the files
   6. 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.

3. First parallel version: no pruning

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

4. Second parallel version: pruning

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

5. Third parallel version: spawning only one task

   1. Change your code to spawn only one task for one of the recursive calls, and let the other recursive call be done by the parent task.
   2. Call this code Merge_sortS.
   3. Experiment with it.
   4. What are your observations?

6. Fourth parallel version

   For the sake of completeness, it would be useful to gather data for the version where½ you spawn only one task, and do no pruning.

7. Summarize your observations to take to the discussion on OMP Tasks. You must complete the lab well in advance to leave enough time for discussions with your group.