Accession Number : ADA193466

Title :   Comparing Barrier Algorithms.

Descriptive Note : Interim rept.,

Corporate Author : COLORADO UNIV AT BOULDER COMPUTER SYSTEMS DESIGN GROUP

Personal Author(s) : Arenstorf, Norbert S ; Jordan, Harry F

PDF Url : ADA193466

Report Date : Jun 1987

Pagination or Media Count : 38

Abstract : A barrier is a method for synchronizing a large number of concurrent computer processes. This paper will develop and consider the relative performance of a variety of different barrier algorithms. After considering some basic synchronization mechanisms, a collection of barrier algorithms with either linear or logarithmic depth will be presented. A graphical model is described that profiles the execution of the barriers and other parallel programming constructs. This model shows how the interaction between the barrier algorithms and the work that they synchronize can impact their performance. One result is that logarithmic tree structured barriers show good performance synchronizing fixed length work; while linear self-scheduled barriers show better performance when synchronizing fixed length work with an imbedded critical section. The linear barriers are better able to exploit the process skew associated with critical sections. Timing experiments, performed on an eighteen processor Flex/32 shared memory multiprocessor, that support these conclusions are detailed.

Descriptors :   *ALGORITHMS, *SYNCHRONIZATION(ELECTRONICS), *COMPUTER PROGRAMMING, BARRIERS, COMPUTER PROGRAMMING, DEPTH, GRAPHICS, LOGARITHM FUNCTIONS, PARALLEL PROCESSING, TIME, TREES, MATHEMATICAL MODELS

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE