On a scheme for parallel sorting on heterogeneous clusters ?
We discuss parallel sorting algorithms and their implementations suitable for cluster architectures in order to optimize cluster resources. We focus on the time spent in computation and the load balancing properties when processors are running at different speeds, i.e. correlated by a multiplicative constant factor (our weak definition of heterogeneous platform). One scheme is under study: parallel sorting by sampling (either regular sampling technique introduced by Shi and Schaeffer [J. Parallel Distrib. Comput. 14 (4) (1992) 361] or the over-partitioning scheme introduced by Li and Sevcik [Parallel sorting by over-partitioning, in: Proceedings of the Sixth Annual Symposium on Parallel Algorithms and Architectures, ACM Press, New York, June 1994]). What is important in the paper is mainly the load balance factor and not necessary the execution time. It is clear that improved load balance leads to improved execution time. The results presented in the paper demonstrate that load balancing for the case of computers with heterogeneous processing capacity is more challenging than for the homogeneous case. The survey, through the sorting case study, allow us to identify some algorithmic issues and software challenges to master heterogeneous cluster platforms in order to better utilize them: data decomposition techniques, scheduling and load balancing methods.
performance evaluation and modeling of parallel integer sorting algorithms sorting by regular sampling and by over-partitioning data distribution load balancing strategies bsp programming