Summary: The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in O(p) (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.
The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in \(\mathcal{O}(p)\) (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.
A few words about this article
This article is the result of two semi-independent reflexions on the same topic, federated by Christophe Cerin (the alert reader will recognise three different kinds of writing style in this "heterogeneous" article). I had the privilege of going to Taiwan to present the paper.
The documents
Citing this document
This article was published in the proceedings of the GPC 2006 conference, which took place in Taichung, Taiwan.
@InProceedings{cdr06,
author = {Christophe C\'erin and Jean-Christophe Dubacq and Jean-Louis Roch},
title = {Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters},
booktitle = {Advances in Grid and Pervasive Computing},
pages = {175--186},
year = {2006},
editor = {Yeh-Ching Chung and Jos{\'e} E. Moreira},
volume = {3947},
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer},
isbn = {3-540-33809-8}
}