Please submit a single pdfand a single tgz named uid.{pdf,tgz} respectively. Let the uid start with a lowercase u followed by 7 digits. Submit/upload via canvas.
How would you modify the bitonic sort algorithm if the number of input keys are arbitrary. For example, assume that as input you get \(n=\)rank keys per process. While you are not required to maintain the same number of keys per process for all stages of the bitonic sort, you should not explicitly balance the distribution of the sort before sorting. In other words, any load balancing must happen as part of the bitonic sort. Hint: While merging two bitonic sequences of unequal lengths, what needs to be done to ensure that the resulting sequences are bitonic and satisfy the low \(\le\) high requirement.
Programming Implement an MPI parallel bitonic sort algorithm. You can assume that the number of input keys per process will be the same. The number of processes can be arbitrary. Write a driver routine called sort that takes one argument, the size of array to be sorted (initialized to random integers). On the write-up, give pseudocode for your algorithm, and report wall clock time/core/n results for \(n/p\) = 1,10,100,1000,1M elements using 16 MPI tasks per node for as large a number of nodes as possible. At least try for 1,2,3,4 nodes. Report weak and strong scaling results.