CSE 160 Homework Assignment #4
 High Performance Sorting

Due: Tuesday 5/13 IN CLASS

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).

A small error was also fixed in the code that determines the kind of input you are using. Currently the code prints ? when it uses random input, but the tag should be a 'R'

In this assignment you'll  explore high performance sorting on Valkyrie.  We are providing you with a working odd/even sort algorithm, which was discussed earlier in the class. You'll modify this code in order to explore various approaches to sorting along with the underlying performance tradeoffs. 

The code we are providing is found in  the public directory, which you may access from your home directory as valkyrie:~/../public/examples/oesort.  The  Makefile includes an "arch" file that defines appropriate command line flags for the compiler. You currently have arch.valkyrie which provides  the  appropriate settings needed for Valkyrie.

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!

Odd/Even sort

Recall the inefficient odd/even sort algorithm, which uses a red/black-like strategy to interleave updates to the sorted data.  This algorithm is a variant of bubble sort, and has a costly O(N²) running time in the worst case. The oesort code we've provided is designed with performance measurement in mind.  You may vary the number of iterations (sorting sweeps) and shut off communication. You may specify random input (and specify the random number seed in order to ensure reproducible input), perfectly sorted input (to assess best case behavior), or reverse sorted input (to assess worst case behavior). The oesort program takes various command line options  which are  explained in source file cmdLine.c:

 -n      <integer>       input size
 -i      <integer>       number of iterations
 -f      <integer>       termination check frequency 
 -s      <integer>       random number see
 -nocomm                 Shut off communication
 -w                      worst case (reverse sorted) input
 -b                      best case (perfectly sorted) input

Thus, the command line

   mpi-launch ... oesort -n 128 -i 5 -w

will run oesort on on a 128  element sorted input for 5 iterations.   (The -f option is a placeholder for an option you'll be implementing as part of the assignment.)

The oesort program permits you to set the random number seed with the -s flag. Be sure and use a fixed the seed until you are certain of any code modification you have made. Then, use different seeds. The program will  pick a seed for you if you  don't specify the -s flag, using the system clock.  The seed  will be printed out for you so that can use it in successive runs.

As a general principle, obtain performance results in he 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.

The output

The program exports the various options you have selected along with timings. The performance data consists of a few essential lines of output: wall clock time (T_P, as measured with MPI_WTime( )), grind time (Tgrind= wall clock time divided by the total number of points and number of sweeps), #iterations (sweeps).  Here is the result of a run:

run.py 2 0 1 oesort -n 2097152 -w -i 100

# points: 2097152
Maximum Iterations: 100
Check freq: 1
Worst case (reverse sorted) input
*** Result has FAILED the verification test!

Ran on 2 nodes for 2097152 iterations.
Wall clock time:  5.29669
Grind time:  2.52566e-08

        N     P    T_P        T_grind     Iter Freq  In P/F
@   2097152   2   5.29669   2.52566e-08    100    1   W  F

The program currently reports that the sorting procedure did not completely sort the output.  This output is a placeholder for a verification capability that you will write as part of the assignment.  Lastly there are 4 possible inputs: best case (perfectly sorted), worst case (reverse sorted), from a data  file, or random.

This output is also collected into a 1-liner beginning with the @ symbol as shown above.  This feature enables you to quickly extract performance data from log files containing the results of many runs.  The "In" field contains a 1 character code for the kind of input (B=best case, W=worst case, D=from a data file, R=random).  P/F designates whether or not the run passed or failed the verification  test.

To assist with debugging, the program outputs the result if the input list is not longer than 16 elements. However, the output may not be orderly in the sense that it appears to be non-causal (some output comes later than it is supposed to). If you have time, try and fix the problem and discuss the solution in your writeup.

The Assignment

This Assignment consists of 3 parts.

Part A

1. Run oesort on  small numbers of processors-- 1, 2, and 4-- and determine a appropriate problem scaling of problem size. That is, determine the growth in N needed to maintain a constant running time per sweep. Use random input, and scale the problem so that  the time per sweep time increases by no more than 10% over the range. (If you like, try running on more than 4 processors). Set the number of iterations (with the -i flag) so that the run finishes in a few seconds. Does the problem size grow linearly with the number of processors? Explain your findings.
    

2. Measure communication overhead on 4 processors. To do this, set up the input to be the best case input (perfectly sorted) using the -b flag, and shut off communication using the -nocomm  flag. Run with and without communication and note the difference. Start with the problem size you used in part (1), but report results with smaller values of N. (It's possible that the communication overhead for the value of N you picked in part 1 might be too big, in the sense that the overhead would be small to measure.) In particular, successively halve the value of N until communication overhead is at least 30%.
    
3. One desirable property of odd/even sort is the low running time for almost sorted lists (including sorted lists). However, the program provided to you will run dutifully for N sorting sweeps. Modify the program to terminate once the list has been sorted. Since the cost of performing this test is expensive, introduce an input parameter called -f that varies the rate at which the test is made. (There is a placeholder in cmdLine.c for this specific purpose).
    
4. Since odd/even sort is inefficient, it is not practical to measure the total running time required to sort the worst case input, corresponding to keys sorted in reverse order. However, come up with an estimate of the running time based on a shorter run. Use the -w flag to get the worst case input, and run for 5 seconds.

Part B: Odd-even transposition sort

1. Implement odd-even transposition sort. For the local sort, use the standard  qsort(3) routine provide on Valkyrie.  Retain the termination testing capability described in A3.
2. Repeat the measurements in Part A1 and A2, but run on at least 8 processors.
3. Repeat the measurements in part A4, but first see if you can complete the sort in a reasonable amount of time without having to set   the -i flag. Stop if the run continues for more than about 5 seconds. (And be sure and clear out any runaway processes. There will be a 2% penalty assessed each time a set of runaway processes is found in your name!.  If not, then reduce the input size until you can complete the run in about 5 seconds.
4. Discuss your findings. Compared with the original odd-even sort, does this approach improve scalability?

Part C: Shell sort

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.

Compiling and Running your MPI programs

Use the python script runrand.py when you are testing. But when you are collecting timing results, use a different script called run.py. This script permits you to choose specific procesors IDs. To help make your results repeatable, be sure and stick with a given set of nodes when running on a specific number of processors.

Operating environment

As always, refer to the document titled Getting Started with Valkyrie.

MPI documentation is found at at http://www.cse.ucsd.edu/users/baden/classes/cse260_fa02/testbeds.html#MPI. You can obtain man pages for the MPI calls used in the example programs described here:

• MPI _Init: Initialize the MPI environment. Call this prior to making any MPI calls.
• MPI_Finalize: Exit  the MPI environment. Call this function before exiting your program.
• MPI_Comm_size: Queries the total number of processes use in this program invocation.
• MPI_Comm_rank: Queries this process's unique identifier, an integer called the rank
• MPI _Send: Sends a blocking message from calling process to a destination process.
• MPI _Recv: Receives a message from another process, a return signifies that the message has been received.
• MP I_Wtime: Timer.
• MPI_Barrier: Blocks calling process until all processes have checked in (all processes must call this routine)

 Copyright © 2003 Scott B. Baden. Last modified: 05/02/03 01:32 PM