Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters
<|reference_start|>Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters: 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.<|reference_end|>
@article{cérin2006methods,
    title={Methods for Partitioning Data to Improve Parallel Execution Time for
  Sorting on Heterogeneous Clusters},
    author={Christophe C'erin (LIPN), Jean-Christophe Dubacq (LIPN), Jean-Louis
  Roch (INRIA Rh^one-Alpes / ID-IMAG), the SafeScale Collaboration},
    journal={Advances in Grid and Pervasive Computing (2006) 175-186},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607041},
    primaryClass={cs.DC cs.PF}
}