Case study: integer sort from CORAL benchmarks

​https://asc.llnl.gov/CORAL-benchmarks/#intsort

The benchmark exercises OpenMP threads, MPI-IO, Posix IO, and all-to-all communications with both small and large message sizes. The majority of the time is spent in IO.

It has three major phases:

1. Hash all elements to N bins, where N = # of nodes. Note the benchmark uses 1 MPI rank per node. By the end of this phase, each bin contains all elements falling within a sub range. For example, the first bin contains numbers ranging from 0 to T/N. Each bin is then stored as a “bin file”. In this phase, each rank performs three steps:

1. Read a part (proportional to the DRAM size) of the input file (each rank reads a different part)
2. Hash this part locally according to the bins defined above.
3. Exchange elements among MPI ranks (all-to-all communication) to send them to the MPI rank that owns the corresponding bin.
4. Each rank writes the received elements to its “bin file”.

2. Sort each "bin file" individually in each node. (Note: we assume the numbers are uniformly distributed so there is little concern for load balancing). No MPI communications. Each MPI rank treats its bin file as a collection of chunks, each chunk is of page_size (page_size is recommended to be no smaller than the page size of the file system).

1. Sort chunks in parallel (with OpenMP)
2. Merge every M chunks, repeat until there is only 1 chunk left. This chunk is the sorted bin file.

Note: M = DRAM_size/page_size, so the number of merging stages is log_M_(T/N/page_size)

3. Concatenate all sorted bin files together into a single file.