NONCOMMITTAL BARRIER SYNCHRONIZATION

Barrier synchronization is a fundamental operation in parallel computa tion. In many contexts, at the point a process enters a barrier it kno ws 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 ba rrier. This paper treats the alternative case, when a process cannot e nter a barrier with the assurance that it has already performed all ne cessary pre-synchronization computation. The problem arises when the n umber of pre-synchronization messages to be received by a process is u nknown, for example, in any computation that is largely driven by an u npredictable exchange of messages. We describe a O(log(2) P) time barr ier algorithm for such problems, study its performance on a large-scal e parallel system, and consider extensions to general associative redu ctions, as well as associative parallel prefix computations.