Question

Explain how MPI could be used to speed up a sort a million (1,000,000) values. If you have 1000 processors available how fast would your solution be (big O notation). I do not need code for this -- an explanation of an algorithm and how it would work is sufficient.

Answer 1

MPI (Message passing interface) deals with parallel programming. Parallel programming speedsup the process by a huge amount specially when you have large amount of processors available with you. Incase of linear sorting (ie. without using MPI) the best available sorting algorithm gives us a Big O time complexity of O(n log(n)). This may result in high value of time consumption especially when the number of values are very large.

Just to give a perspective, to sort a million values, it will take O( 100000 log (1000000) ) which is approximately O (20million) which is a huge time. Using MPI using n processors optimal complexity of a parallel sorting algorithm is O[(n log(n))/p]= O(20000). So, you can see how this reduces the computations and makes the program efficient.

Now, how this algorithm works, It uses Divide list into unsorted sub-lists. This list is divided into many other sublists based on the total number of processors available. Then these sublists are sorted on each different processors. Then its is merged. As you can see the computations becomes very less. This is algorithm of parallel merge sort of many different processors.

MPI Init Read dataset & partitioning data by processors No. If id-Master Sending data to salves Receive data from master Master pat Salve part Salve 0 Salve n- Bubble Sort Bubble Sort Sending results to master Receive data from salves Merge Sort MPI Finalize

Hope this helps. Please rate a THUMBS UP and Best of Luck :)