An Over-partitioning Scheme for Parallel Sorting on Clusters with Processors Running at different Speeds

In this work we introduce a new algorithm for in-core parallel sorting integer keys which is based on the over- partitioning scheme introduced by Li and Sevcik (1). The algorithm is devoted to clusters with processors running at different speeds i.e. correlated by a multiplicative constant factor. We compare experimentally this approach with an- other one related to the Parallel Sorting by Regular Sam- pling (2) that we have augmented to deal with the case of clusters with processors at different speeds. The metric used for the comparison is the sublist expansion metric that mea- sures the load balancing of the algorithm. What is impor- tant in our work is the load balance factor, not (yet) the ex- ecution time. It is clear that improved load balance leads to improved execution time. The results we have obtained demonstrate that load balancing for the case of computers with heterogeneous processing capacity is more challeng- ing than for the homogeneous case.