Parallel Sorting Algorithms with Sampling Techniques on Clusters with Processors Running at Different Speeds

摘要

In this paper we use the notion of quantile to implement Parallel Sorting by Regular Sampling (PSRS) on homogeneous clusters and we introduce a new algorithm for in-core parallel sorting integer keys which is based on the sampling technique. The algorithm is devoted to clusters with processors running at different speeds correlated by a multiplicative constant factor. This is a weak definition of non-homogeneous clusters but a first attempt (to our knowledge) in this direction.