A version of parallel sorting library based on the following paper

"Histogram Sort with Sampling", SPAA 2019
Vipul Harsh, Laxmikant Kale, Edgar Solomonik



Contents in this directory

- sortinglib - directory that contains the sorting library in Charm++.

- testsorting.C - an example charm program that uses the sorting library


Compiling

- Download charm++ from http://charmplusplus.org/download/ or by typing
  "git clone http://charm.cs.illinois.edu/gerrit/charm.git" 

- Build and install charm++. A possible installation command for 64 bit linux could be 
  ./build charm++ netlrts-linux-x86_64 smp --with-production -j8.
  "smp" argument can be skipped if not building a shared memory version.
  For installation instructions, see: https://charm.cs.illinois.edu/manuals/html/charm++/A.html

- Once charm++ is built, set the variable CHARMDIR in Makefile.in to the full path of the 
  build directory of charm++. The name of the build directory depends on the build used 
  for charm++. If you used the build command mentioned above, the name of the directory would 
  be "netlrts-darwin-x86_64-smp".

- Execute make from the top level HSS directory


Running locally

- "./charmrun +p16 ++ppn 4 ./bin/testsorting 500000 42 100 GAUSS" will run parallel sorting 
  on 16 PEs with 4 PEs per node (all PEs in a node share the same memory); so total of 4 nodes.
  500000 is the number of keys per PE, 42 is a random seed and 100 is the estimated max probe
  size used for initial memory allocations as an optimization (This only needs to be an estimate.
  If underestimated, the program would automatically allocate a higher amount of memory). Specifying
  GAUSS will generate random keys according to a Gaussian distribution. See testsorting.C for 
  other distributions.


Running on a cluster

- You might have to build charm++ according to the architecture of the cluster. See 
  https://charm.cs.illinois.edu/manuals/html/charm++/A.html for instructions.

- On some clusters, mpiexec could be used to launch the charm processes. E.g. 
  ./charmrun ./bin/testsorting +p16384 ++ppn 16 100000 1 100000 GAUSS ++mpiexec
  For running instructions, see: https://charm.cs.illinois.edu/manuals/html/charm++/C.html 

Contact

- [email protected]

- For Charm++ related queries- [email protected]

Acknowledgements

- Nikhil Jain for providing the interface for the sorting library.