Accession Number : ADA255122

Title :   Optimistic Barrier Synchronization.

Descriptive Note : Contractor rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Nicol, David M.

Report Date : JUL 1992

Pagination or Media Count : 23

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.

Descriptors :   *BARRIERS, *SYNCHRONIZATION(ELECTRONICS), ALGORITHMS, COMPUTATIONS, CONTRACTORS, EXCHANGE, NUMBERS, OPERATION, PAPER, REDUCTION, SCALE, SIMULATION, WORK, PARALLEL PROCESSING, OPTIMIZATION.

Subject Categories : Electrical and Electronic Equipment

Distribution Statement : APPROVED FOR PUBLIC RELEASE