Sorting has been one of the most challenging studied problems in different scientific researches. Although many techniques and algorithms have been proposed on the theory of having efficient parallel sorting implementation, however achieving desired performance on different types of the architectures with large number of processors is still a challenging issue. Maximizing parallelism level in applications can be achieved by minimizing overheads due to load imbalance and waiting time due to memory latencies. In this paper, we present a distributed sorting algorithm implemented in PGX.D, a fast distributed graph processing system, which outperforms the Spark's distributed sorting implementation by around 2x-3x by hiding communication latencies and minimizing unnecessary overheads. Furthermore, it shows that the proposed PGX.D sorting method handles dataset containing many duplicated data entries efficiently and always results in keeping balanced workloads for different input data distribution types.
In this section, we briefly discuss about the implementation of some of the existing sorting techniques and their challenges. Different parallel algorithms have been studied for many years to achieve an efficient distributed sorting method implemented on distributed machines. Keeping balanced load is usually difficult while implementing most of these algorithms when facing dataset containing many duplicated data entries, which usually results in having some machines holding larger amount of data than the others. Most of these techniques consist of two main steps: partitioning, and merging. The big challenge in the partitioning step is to maintain the load balancing on different distributed machines in addition to distribute data among them in a sorting order @cite_12 @cite_10 . Also, the big challenge in the merging step is decreasing latencies and keeping the desired scalability during all merging steps till the end. The performance of the merging step is usually scalable when having a small number of machines. However, while utilizing larger number of machines, the synchronizations reduce its parallel scalability. Moreover, most of these existing techniques require a significant communication bandwidth, which increases overheads and degrades the parallel performance @cite_2 .
@cite_10 @cite_12 @cite_2
2016240806 1694308253 2039764713
We study the problems of sorting and ranking n processors that have initial values (not necessarily distinct) in a distributed system. Sorting means that the initial values have to move around in the network and be assigned to the processors according to their distinct identities, while ranking means that the numbers 1, 2,..., n have to be assigned to the processors according to their initial values; ties between initial values can be broken in any chosen way. Assuming a tree network, and assuming that a message can contain an initial value, an identity, or a rank, we present an algorithm for the ranking problem that uses, in the worst case, at most n2 2+O(n) such messages. The algorithm is then extended to perform sorting, using in the worst case at most 3n2 4+O(n) messages. Both algorithms are using a total of O(n) space. The algorithms are extended to general networks. The expected behavior of these algorithms for three classes of trees is discussed. Assuming that the initial values, identities, and ranks can be compared only within themselves, lower bounds of n2 2 and 3n2 4 messages are proved for a worst case execution of any algorithm to solve the ranking and sorting problems, respectively. Merge sort is useful in sorting a great number of data progressively, especially when they can be partitioned and easily collected to a few processors. Merge sort can be parallelized, however, conventional algorithms using distributed memory computers have poor performance due to the successive reduction of the number of participating processors by a half, up to one in the last merging stage. This paper presents load-balanced parallel merge sort where all processors do the merging throughout the computation. Data are evenly distributed to all processors, and every processor is forced to work in all merging phases. An analysis shows the upper bound of the speedup of the merge time as (P- 1) log P where P is the number of processors. We have reached a speedup of 8.2 (upper bound is 10.5) on 32-processor Cray T3E in sorting of 4M 32-bit integers. A straight-line-topology local area network (LAN) to which a number of nodes are connected either in series or in parallel is considered. A file F is arbitrarily partitioned among these sites. The problem studied is that of rearranging the records of the file such that the keys of records at lower-ranking sites are all smaller than those at higher-ranking sites. Lower bounds on the worst-case communication complexity are given for both the series and parallel arrangements, and algorithms optimal for all networks and files are presented. >