Improving parallel execution time of sorting on heterogeneous clusters

  • C. Cerin Université de Picardie Jules-Verne
  • M. Koskas LaMFA/CNRS UMR 6140 / Université de Picardie Jules-Verne
  • H. Fkaier École Supérieure des Sciences et des Techniques de Tunis
  • M. Jemni École Supérieure des Sciences et des Techniques de Tunis

Resumo


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.
Palavras-chave: Sorting, Clustering algorithms, Load management, Concurrent computing, Analytical models, Partitioning algorithms, Parallel algorithms, Parallel processing, Computer architecture, High performance computing, in-core parallel sorting algorithms, heterogeneous computing, complexity of parallel algorithms
Publicado
27/10/2004
Como Citar

Selecione um Formato
CERIN, C.; KOSKAS, M.; FKAIER, H.; JEMNI, M.. Improving parallel execution time of sorting on heterogeneous clusters. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 16. , 2004, Foz do Iguaçu/PR. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2004 . p. 180-187.