assignments/archive/sorting/soln/README

   1 sorting
   2 =======
   3
   4 Various sorting algorithms.
   5
   6 Manifest
   7 --------
   8
   9 ===========  ===============================================
  10 README       This file.
  11 Makefile     Automate building and cleanup.
  12 data.py      Generate random data for the 'data' file.
  13 scaling.py   Script to generate time-scaling data.
  14 main.c       Command line framework for a sorting algorithm.
  15 sort.h       Header declaring sort function syntax.
  16 bubble.c     Bubble sort implementation of sort.h.
  17 quicksort.c  Quicksort implementation of sort.h.
  18 ===========  ===============================================
  19
  20 Build
  21 -----
  22
  23 Just run
  24
  25     $ make
  26
  27 which also builds a random data file 'data'.  To build with the DEBUG
  28 macro defined (to enable some stderr printouts in main.c), run
  29
  30     $ make CFLAGS=-DDEBUG
  31
  32 To get timing information, compile with
  33
  34     $ make CFLAGS=-DDEBUG_TIMING
  35
  36 Although the chunk-merge portion of the sort is generally much quicker
  37 than the chunk sorting itself, it is less clear what the fastest
  38 chunk-merge algorithm is.  Set the MERGE_TYPE macro to test other
  39 algorithms, for example:
  40
  41     $ make clean && make "CFLAGS=-DDEBUG_TIMING"
  42     $ ./data.py 100000 | mpiexec -n 3 ./parallel-quicksort >/dev/null
  43     sorted 100000 elements in 20.9942 seconds and merged in 0.0027411 seconds
  44     $ make clean && make "CFLAGS=-DDEBUG_TIMING -DMERGE_TYPE=1"
  45     $ ./data.py 100000 | mpiexec -n 3 ./parallel-quicksort >/dev/null
  46     sorted 100000 elements in 21.3503 seconds and merged in 1.07004 seconds
  47
  48 Remove auto-generated files with
  49
  50     $ make clean
  51
  52 Usage
  53 -----
  54
  55 Start the Message Passing Daemons with
  56
  57     $ mpdboot -n 4 -f mpd.hosts
  58
  59 which spawns a daemon (`mpd`) on the first four hosts in `mpd.hosts`.
  60 Then run your program (e.g. `simplest_message`) with.
  61
  62     $ mpiexec -n 4 ./simplest_message
  63
  64 When you're done, clean up the daemons with
  65
  66     $ mpdallexit
  67
  68 Examples for each of the executables in this package:
  69
  70     $ mpiexec -n 4 ./parallel-quicksort data
  71     $ mpiexec -n 4 ./parallel-bubble data
  72
  73 Timing
  74 ------
  75
  76 Time 8191 data points on 4 xphy nodes with
  77
  78     $ mpdboot -n 4 -f <(seq 1 4 | sed 's/^/xphy/')
  79     $ time mpiexec -n 4 ./parallel-bubble data > /dev/null
  80     $ time mpiexec -n 4 ./parallel-quicksort data > /dev/null
  81     $ mpdallexit
  82
  83 quicksort takes 0.210 s and bubble takes 0.302 s.
  84
  85 TODO: `make scaling` doesn't work yet.
  86 You can generate scaling graphs for all executables built by the
  87 Makefile with
  88
  89     $ make scaling
  90
  91 which generates `*-scaling.dat` and `*-scaling.png` for each
  92 executable.