Two algorithms for barrier synchronization

Debra Hensgen, Raphael Finkel, Udi Manber

Research output: Contribution to journalArticlepeer-review

144 Scopus citations

Abstract

We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to Brooks. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brook's communication pattern with an information dissemination algorithm described by Han and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brook's original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of the n processes meeting at the barrier must be assigned identifiers i such that 0≤i<n.

Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalInternational Journal of Parallel Programming
Volume17
Issue number1
DOIs
StatePublished - Feb 1988

Keywords

  • Barrier
  • broadcast
  • distributed
  • parallel
  • shared memory
  • synchronization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Fingerprint

Dive into the research topics of 'Two algorithms for barrier synchronization'. Together they form a unique fingerprint.

Cite this