159.735 - Assignment 2

To be submitted by 8th May 2009

The aim of this assignment is to implement a parallel version of the bucket sort routine covered in the lectures using MPI collective communication routines.

The master process takes as user input (from the command line) the size of the array of data numbers to sort and then creates an array and populates it with a set of random numbers.

The master then needs to partition this array and use an appropriate collective communication routine to send each partition to the correct slave process. Each slave will maintain a set of its own buckets covering the full range of possible numbers and will implement the bucket sort routine on its own set of numbers.

After this, the appropriate collective communication routine will then need to be called to send each small bucket to the large bucket on the corresponding process. Finally, the large buckets need to be sorted, and the contents gathered into the master process.

Your master program should implement a test on the array to check that the numbers are sorted. Do not print the entire array.

Run your code on 2, 4 and 8 processors and compare the scalability of your program for different problem sizes. Marks will be awarded for comments, analysis, correctness and completeness of output. This assignment is worth 10 marks, which will contribute 10% of your

overall grade.

Getting started: Copy the program “bucket.c” from the directory /opt/examples on iimacluster. This contains the sequential implementation of bucket sort. Your task is to write the parallel implementation.

Marks will be awarded for correct programs that perform as little communication as possible and run as fast as possible on many processors. The iimscluster machine has 8 processors but your code should also be able to run on larger machines.

This is an individual assignment, marks will be deducted for plagiarism and late submissions.

Programs that do not compile and run without modification will lose marks.

You should submit your program source code electronically from the paper web site.

M Johnson 2009