PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms

Assefaw Hadish Gebremedhin 1 Jens Gustedt 2 Mohamed Essaïdi 3 Isabelle Guérin Lassous 4 Jan Arne Telle 5
1 ODU - Old Dominion University [Norfolk]
2 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 SMASH - Simulation, modeling and analysis of heterogeneous systems
CRISAM - Inria Sophia Antipolis - Méditerranée , Université de Provence - Aix-Marseille 1
4 ARES - Architectures of networks of services
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
5 UIB - University of Bergen
Abstract : We present a new parallel computation model called the Parallel Resource-Optimal computation model. PRO is a framework being proposed to enable the design of efficient and scalable parallel algorithms in an architecture-independent manner, and to simplify the \emph{analysis} of such algorithms. A focus on three key features distinguishes PRO from existing parallel computation models. First, the design and analysis of a parallel algorithm in the PRO model is performed relative to the time and space complexity of a specific sequential algorithm. Second, a PRO algorithm is required to be both time- and space-optimal relative to the reference sequential algorithm. Third, the quality of a PRO algorithm is measured by the maximum number of processors that can be employed while optimality is maintained. Inspired by the Bulk Synchronous Parallel model, an algorithm in the PRO model is organized as a sequence of \emph{supersteps}. Each superstep consists of distinct computation and communication phases, but the supersteps are not required to be separated by synchronization barriers. Both computation and communication costs are accounted for in the runtime analysis of a PRO algorithm. Experimental results on parallel algorithms designed using the PRO model---and implemented using its accompanying programming environment SSCRAP---demonstrate that the model indeed delivers efficient and scalable implementations on a wide range of platforms.
Keywords : Parallel computers Parallel computation models Parallel algorithms Complexity analysis
Type de document :
Article dans une revue
Nordic Journal of Computing, Publishing Association Nordic Journal of Computing, 2006, 13 (4), pp.215-239
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00000899
Contributeur : Jens Gustedt <>
Soumis le : jeudi 5 octobre 2006 - 12:04:34
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 12:12:49

Fichier

main.pdf

Identifiants

  • HAL Id : inria-00000899, version 2

Collections

INRIA | INSA-LYON | UNIV-AMU | LORIA | UNIV-LORRAINE

Citation

Assefaw Hadish Gebremedhin, Jens Gustedt, Mohamed Essaïdi, Isabelle Guérin Lassous, Jan Arne Telle. PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms. Nordic Journal of Computing, Publishing Association Nordic Journal of Computing, 2006, 13 (4), pp.215-239. 〈inria-00000899v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

186

Contact


archive-ouverte@inria.fr