Direct bulk-synchronous parallel algorithms

Alexandrosv Gerbessiotis, Leslieg Valiant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations


We describe a methodology for constructing parallel algorithms that are transportable among parallel computers having different numbers of processors, different bandwidths of interprocessor communication and different periodicity of global synchronisation. We do this for the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of a parallel machine into three numerical parametersp, g, andL, corresponding to processors, bandwidth, and periodicity respectively. The model differentiates memory that is local to a processor from that which is not, but, for the sake of universality, does not differentiate network proximity. The advantages of this model in supporting shared memory or PRAM style programming have been treated elsewhere. Here we emphasise the viability of an alternative direct style of programming where, for the sake of efficiency the programmer retains control of memory allocation. We show that optimality to within a multiplicative factor close to one can be achieved for the problems of Gauss-Jordan elimination and sorting, by transportable algorithms that can be applied for a wide range of values of the parametersp, g, andL. We also give some simulation results for PRAMs on the BSP to identify the level of slack at which corresponding efficiencies can be approached by shared memory simulations, provided the bandwidth parametergis good enough.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsOtto Nurmi, Esko Ukkonen
PublisherSpringer Verlag
Number of pages18
ISBN (Print)9783540557067
StatePublished - 1992
Externally publishedYes
Event3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 - Helsinki, Finland
Duration: Jul 8 1992Jul 10 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume621 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Direct bulk-synchronous parallel algorithms'. Together they form a unique fingerprint.

Cite this