CSE 160 Homework Assignment #5
 Bucket Sorting

Due: Tuesday 5/27 IN CLASS

In this assignment you'll  explore bucket sort, and compare  performance with your best sort from assignment #4.  

You will  code your algorithm scratch, however, you should be able to use some of the utility code from Assignment #4.  Be sure and use the SPRNG library for generating random numbers.  An example of how to build an application that utilizes SPRNG is found in  valkyrie:~/../public/examples/spring_ex.  There is also a version of Odd-Even sort that uses SPRNG in the directory ~/../public/examples/oesort_new.  The  Makefile in that includes an arch.valkyrie file defining appropriate command line flags for the compiler, including some that are specific to SPRNG.  (Be sure not to use the old "arch" file, which lacks the options specific to SPRNG)

SPRNG operates from a single global seed, and it uses a sensible strategy for picking a seed based on the system clock. If you're interested in learning more, please see the SPRNG web page at http://sprng.cs.fsu.edu/Version1.0/index.html (We are using version 1.0).

For this assignment you'll need the MPI routine MPI_Alltoall. For more information click Here.

 

Note: ;Be sure and clear runaway processes.  There will be a 2% penalty assessed each time a set of runaway processes is found in your name!

The Assignment

As a general principle, obtain performance results in the following manner.  Repeat a run at least 4 times for each combination of  input and number of processors P (input includes the random number seed). Take the minimum time, but also note any outliers.  Repeat for at least 10 different seeds. Finally take the average of the minima over all the different  random number seeds, but note any variations.

  1. Implement bucket sort. You may use quicksort(3) for your local sort (Although quicksort is not a stable sort, we won't be concerned with stability).
  2. Run on  4 and 8 processors and determine an appropriate scaling of the input size so that the sort completes in about 5 to 10 seconds.  Compare the performance of your code against the best sort you implemented in assignment #4, that is run both sort algorithms on the same size input. 
  3. Bucket sort requires 3 phases:  the initial local sort,  global communication to route data to the correct destination, a final merge sort. .Come up with a strategy for separately accounting for the three phases, and collect performance data for your chosen problem size. 
  4. Now, increase and decrease N by powers of two until see a noticeable change in some aspect of performance. Discuss your findings.
  5. Devise  a pathological input that causes all the sorted keys to end up on one processor. A simple way of doing this is to restrict the random input to fall in the range of
     232/P -1. Be sure to keep the input size small enough that you don't run out of memory, and run on 4 processors only. Record the running time for at least 5 different random inputs, preferably 10.  Repeat part (3) (you need not repeat part 4).
  6. Repeat part (3) for a perfectly sorted input as well as a reverse sorted input.
     

Things you should turn in

Document your work in a well-written report which discusses your findings carefully. Your report should present a clear evaluation of the performance, including bottlenecks of the implementation, and describe any special coding or tuned parameters. Be sure to include the plots of any performance data described above, along with any plotted data in in tabular form.

Your report should cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.

Provide sample output demonstrating correct operation of your code, i.e. for N=16. Be sure and attach this output, along with your code listings and plots. Include any plotted data in tabular form as well. There is no need to include any listings for files that were provided by us but not modified by you. Provide hard copy in class.

Electronic turnin instructions

You should also transmit the report electronically.

Use tar or zip to bundle up your writeup, plots, and source code. Email the file to cs160x1@valkyrie.ucsd.edu. Your archive file should create a directory with your login ID (if working in teams choose just one and stick with it throughout the quarter)

The directory should contain a README file listing the partners, as well as a subdirectory called "src" with the source code and your makefile. (Remove all .o files and executables.)

If your report contains multiple files (e.g. plots), then include a "report" subdirectory as well. Place all files associated with the report in this directory.

If you like, include an html file called index.html from which to navigate through your submission with links to the README file and to the remainder of your submission.

Copyright © 2003 Scott B. Baden. Last modified: 05/15/03 07:01 PM