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.

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 this code. (leave Merge_sort alone for reference)
    3. Spawn two new tasks, one for each recursive mergesort call.
    4. Adjust your Makefile. Make sure that you use -O3 flag to compile all the files
    5. 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 recirsive 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. 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 in Piazza.