ISSN:
1573-7640
Keywords:
Multiprocessor systems
;
barrier synchronization
;
synchronization overhead
;
parallelizing compilers
;
code reordering
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Parallel programs are commonly written using barriers to synchronize parallel processes. Upon reaching a barrier, a processor must stall until all participating processors reach the barrier. A software implementation of the barrier mechanism using shared variables has two major drawbacks. Firstly, the execution of the barrier may be slow since it requires execution of several instructions. Secondly, processors that are stalled waiting for other processors to reach the barrier cannot do any useful work. In this paper, the notion of thefuzzy barrier is presented, that avoids these drawbacks. The first problem is avoided by implementing the mechanism in hardware. The second problem is solved by extending the barrier concept to include a region of statements that can be executed by a processor while it awaits synchronization. The barrier regions are constructed by a compiler and consist of instructions such that a processor is ready to synchronize upon reaching the first instruction and must synchronize before exiting the region. When synchronization does occur, the processors could be executing at any point in their respective barrier regions. The larger the barrier region, the more likely it is that none of the processors will have to stall. Hardware fuzzy barriers have been implemented as part of a RISC-based multi-processor system. Results based on a software implementation of the fuzzy barrier on the Encore multiprocessor indicate that the synchronization overhead can be greatly reduced using the mechaism.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01407864
Permalink