On the versatility of parallel sorting by regular sampling
1993; Elsevier BV; Volume: 19; Issue: 10 Linguagem: Inglês
10.1016/0167-8191(93)90019-h
ISSN1872-7336
AutoresXiaobo Li, Paul Lu, Jonathan Schaeffer, J. Shillington, Pok Sze Wong, Hanmao Shi,
Tópico(s)Machine Learning and Algorithms
ResumoParallel sorting algorithms have already been proposed for a variety of multiple instruction streams, multiple data streams (MIMD) architectures. These algorithms often exploit the strengths of the particular machine to achieve high performance. In many cases, however, the existing algorithms cannot achieve comparable performance on other architectures. Parallel Sorting by Regular Sampling (PSRS) is an algorithm that is suitable for a diverse range of MIMD architectures. It has good load balancing properties, modest communication needs and good memory locality of reference. If there are no duplicate keys, PSRS guarantees to balance the work among the processors within a factor of two of optimal in theory, regardless of the data value distribution, and within a few percent of optimal in practice. This paper presents new theoretical and empirical results for PSRS. The theoretical analysis of PSRS is extended to include a lower bound and a tighter upper bound on the work done by a processor. The effect of duplicate keys is addressed analytically and shown that, in practice, it is not a concern. In addition, the issues of oversampling and undersampling the data are introduced and analyzed. Empirically, PSRS has been implemented on four diverse MIMD architectures and a network of workstations. On all of the machines, for both random and application-generated data sets, the algorithm achieves good results. PSRS is not necessarily the best parallel sorting algorithm for any specific machine. But PSRS will achieve good performance on a wide spectrum of machines before any strengths of the architecture are exploited.
Referência(s)