In this assignment you'll enhance the bucket sort program implemented in assignment 5 to improve the quality of the splitters. The resultant program will implement sample sort, which was discussed in class.
As with Assignment #5, ve sure and use the SPRNG library for generating random numbers. If you like, experiment with the parallel print facility (PPF) which was discussed in class. Be sure to include the appropriate arch.valkyrie_ppf file in your makefile, since it requires some loader and command line flags to use the PPF library (Described in the slides for Lecture 17). Example code is found in ~/../public/lib/PPF.
As always, be sure and delete runaway processes promptly. A 2% penalty will be assessed each time a set of runaway processes is found in your name!
Your goal is to come up with a splitter selection strategy that ensures that the sorted result will be spread uniformly across processors even in a worst case scenario. For your worst case input, you may use the -w flag, or, come up with your own input.
Your program should output the # keys residing on each processor at the end of the sort, as well as the number of keys that each processor sends out during the distribution phase.
Run on at least 4 processors to collect these tallies and compare with bucket sort from assignment #5.
Document your work in a well-written report which discusses your findings carefully. Your report should present a clear evaluation of your splitter selection strategy, including any bottlenecks of the implementation. Describe any special coding or tuning. Time the cost of splitter selection. Is it a performance bottleneck on 8 or 16 processors? Be sure to include any plotted data in in tabular form. However, you need not report speedup results.
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, including the splitter selection and the above mentioned tallies. Attach this output to your report, along with your code listings and plots. Turn in hard copy in class. Also transmit the report electronically using the same procedure used for Assignment 5.
Copyright © 2003 Scott B. Baden. Last modified: 05/28/03 06:52 PM