Noncommittal barrier synchronization

Research output: Contribution to journalArticlepeer-review

Abstract

Barrier synchronization is a fundamental operation in parallel computation. In many contexts, at the point a process enters a barrier it knows that it has already processed all work required of it prior to the synchronization. It then commits to the barrier, in the sense that the process blocks until every other process has also committed to the barrier. This paper treats the alternative case, when a process cannot enter a barrier with the assurance that it has already performed all necessary pre-synchronization computation. The problem arises when the number of pre-synchronization messages to be received by a process is unknown, for example, in any computation that is largely driven by an unpredictable exchange of messages. We describe a O(log2 P) time barrier algorithm for such problems, study its performance on a large-scale parallel system, and consider extensions to general associative reductions, as well as associative parallel prefix computations.

Original languageEnglish (US)
Pages (from-to)529-549
Number of pages21
JournalParallel Computing
Volume21
Issue number4
DOIs
StatePublished - Apr 1995
Externally publishedYes

Keywords

  • Optimistic computation
  • Parallel prefix
  • Parallel simulation
  • Synchronization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint

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

Cite this