Jean-Christophe Dubacq

To content | To menu | To search

Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters

10 Jan 2008 10:48

By jcdubacq

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 on the content of 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.

Attached to this post, you will find the slides that I used for the presentation.

Citing this publication

This article was published in the proceedings of the GPC 2006 conference, that took place in Taichung, Taiwan, this year.

@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}
}

Attachments