Improving parallel execution time of sorting on heterogeneous clusters

Author

Cérin, Christophe ; Koskas, Michel ; Fkaier, Hazem ; Jemni, Mohamed

Author_Institution

LaRIA, Univ. de Picardie Jules Verne, Amiens, France

fYear

2004

fDate

27-29 Oct. 2004

Firstpage

180

Lastpage

187

Abstract

The aim of the paper is to introduce techniques in order to optimize the parallel execution time of sorting on heterogeneous platforms (processors speeds are related by a constant factor). We develop a constant time technique for mastering processor load balancing and execution time in an heterogeneous environment. We develop an analytical model for the parallel execution time, sustained by preliminary experimental results in the case of a 2-processors systems. The computation of the solution is independent of the problem size. Consequently, there is no overhead regarding the sorting problem.

Keywords

computational complexity; multiprocessing systems; parallel algorithms; resource allocation; sorting; workstation clusters; 2-processors systems; constant time technique; heterogeneous clusters; in-core parallel sorting algorithms; load balancing; parallel algorithm complexity; parallel execution time; Analytical models; Clustering algorithms; Computer architecture; Concurrent computing; High performance computing; Load management; Parallel algorithms; Parallel processing; Partitioning algorithms; Sorting; complexity of parallel algorithms; heterogeneous computing; in-core parallel sorting algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Architecture and High Performance Computing, 2004. SBAC-PAD 2004. 16th Symposium on

ISSN

1550-6533

Print_ISBN

0-7695-2240-8

Type

conf

DOI

10.1109/SBAC-PAD.2004.21

Filename

1364752