File DistributedSort.h
↰ Parent directory (ADS/distributed)
The sort of the items spread over the processes of MPI, beyond the book, compiled only with ADS_WITH_MPI (the CMake option of the same name, OFF by default) and an implementation of MPI (Open MPI or MPICH): each of the P processes of a communicator holds a vector of items, and after sort( comm , A , less ) each holds a sorted vector, those of the ranks 0 , … , P - 1 in this order being the sorted items of all; the vectors change their sizes.
Definition (ADS/distributed/DistributedSort.h)
Detailed Description
The items are copied as bytes (trivially copyable). An executor [see File Executor.h] may be given as well, and then the work inside each process runs on its threads (MPI between the nodes, threads within each, the hybrid scheme of the clusters of today).
The sort is the parallel sort by regular sampling of Shi and Schaeffer, in one round of communication: each process sorts its n_i items (by sort() of Namespace ADS, or its parallel version on the executor), takes P - 1 samples at the ranks :math:` lfloor ( j + 1 ) n_i / P rfloor , and all the :math: P ( P - 1 ) ` samples, gathered by MPI_Allgather and sorted, give the P - 1 splitters at the ranks :math:` ( j + 1 ) ( P - 1 ) ; each process cuts its sorted items at the splitters by binary searches (the items equal to a run of k equal splitters are cut into k + 1 parts of the same size, so that a key repeated many times is spread over as many processes as it fills), sends each piece to its process by one MPI_Alltoallv (after an MPI_Alltoall of the counts), and merges the P sorted pieces it receives by multiwayMerge() [see :ref:`file_ADS_priority_MultiwayMerge.h and File ParallelMerge.h]. With the same number of items in each process, no process receives more than :math:` 2 n / P ` items (the bound of regular sampling, for distinct keys); the work is :math:` O( ( n / P ) log n ) ` per process, the volume of communication :math:` O( n / P + P^2 ) ` per process in 3 collective operations, i.e., :math:` O( alpha P + beta n / P ) ` time for latency :math:` alpha ` and time :math:` beta ` per byte with a direct all-to-all. Beyond some thousands of processes the :math:` P^2 ` samples and the :math:` P ` messages of each process dominate, and the multi-level sorts of Axtmann, Bingmann, Sanders and Schulz (which group the processes and exchange in :math:` O( log P ) ` levels) take over.
The contracts [see File Contract.h]: T is trivially copyable; less is a strict weak order, the same in every process; every process of comm calls sort() (a collective operation); the local result is sorted (an audit). H. Shi, J. Schaeffer, Parallel sorting by regular sampling, Journal of Parallel and Distributed Computing 14(4), 361-372, 1992, doi:10.1016/0743-7315(92)90075-X
Axtmann, T. Bingmann, P. Sanders, C. Schulz, Practical massively parallel sorting, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 13-23, 2015, doi:10.1145/2755573.2755595
- Donato Meoli
Dipartimento di Informatica Universita’ di Pisa
by Donato Meoli