For this project, you should use MPI as well as OpenMP. You are free to choose how to combine the two for performance, but you should at least have as many MPI ranks as the number of physical nodes used in benchmarking.
computer science
Description
1 Distributed Memory Histogramming Sort
For this project, you should use MPI as well as OpenMP. You are free to choose how to combine the two for performance, but you should at least have as many MPI ranks as the number of physical nodes used in benchmarking. You will start with data consisting of unsigned 64-bit integers, whose type is defined as dist sort t, that is distributed non-uniformly across MPI ranks. You can find the function prototypes in solution.h, and corresponding function bodies in solution.cpp. You may also want to refer to main sort.cpp, where the overall execution flow of the program is defined.
You will first balance data by redistributing it across processes without worrying about sorted-ness, and then sort it
in parallel using all MPI ranks with a repeated histogramming algorithm. At the end, each MPI rank should hold data
that is locally sorted, and any data on rank i should be smaller than the smallest data item on rank i+1 (i.e. data should
be globally sorted). The entire set of data items, including any duplications, must remain the same
1.1 Rebalancing Data
Your first task is to balance data across all the ranks without worrying about sorted-ness. This should be implemented
in the rebalance() function. The first two parameters are the original data array (randomly generated) and the number
of elements in the array. The last two parameters are pointers to the array that will contain the rebalanced data and the
number of elements that will be in the rebalanced array. This function should be implemented such that all ranks have
roughly the same number of data elements, where each data element originates from one of the imbalanced arrays (the
total dataset should remain the same).
