Comparing Barrier Algorithms.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1987
- Accession Number
- ADA193466
Entities
People
- Harry F. Jordan
- Norbert S. Arenstorf
Organizations
- University of Colorado Boulder