Optimistic Barrier Synchronization.
Abstract
Barrier synchronization is a fundamental operation in parallel computation. In many contexts, at the point a processor enters a barrier it knows that is has already processed all work required of it prior to the synchronization. This paper treats the alternative case, when a processor cannot enter a barrier with the assurance that it has already performed all necessary pre-synchronization computation. The proble marises when the number of pre-synchronization messages to be received by a processor is unknown, for example, in a parallel discrete simulation or any other computation that is largely driven by an unpredictable exchange of messages. We describe an optimistic O(log2P) 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1992
- Accession Number
- ADA255122
Entities
People
- David M. Nicol