Due date: Thursday, October 29, 2020.

In this homework we'll implement the bubble sort function with the pipeline model and with the library MPI. Please consult the PowerPoint slides on Canvas for the implementation details.

Download the following files containing a program that generates an array containing random values in a range and computes their sum using multiple processes.
sum_array_mpi.cc
Makefile

Compile the program with the command make and run it with the command make run, or

mpirun -np xx sumpi
where xx is the number of processes you want to run it with.

Modify this program to sort the randomly generated array with the parallel bubble sort. At the end, to synchronize the output, each worker process will have to send the sorted part of the array that they have to the master process, so that the master can output the bigger sorted array, otherwise we won't know if it's really sorted. The master will need to allocate the array with a bigger size to be able to receive the results form all the workers. Use pointer arithmetic in the recv message to receive the partial arrays in the right place in the bigger array.

Measure the fill, the latency, and the drain of the pipeline, and mention. The fill can be measured by the last process by computing the difference between when it enters the worker function and when it has received the data in the first iteration before doing the first loop. The drain can be measured by the last process also, as the time difference between the beginning and the end of the last np-1 iterations. The latency can be measured as the total execution time minus the fill and the drain, multiplied by the number of processes and divided by the size of the array minus the number of processes minus 2.

Upload: to Canvas, Assignments, Homework 8, all the files that you modify, add, create (including the Makefile if you've changed it), and the performance measurements.