Efficient techniques for fast nested barrier synchronization
Vara Ramakrishnan, Isaac D. Scherson, Raghu Subramanian · 1995
Two hardware barrier synchronization schemes are presented which can support deep levels of control nesting in data parallel programs.Hardware barriers are usually an order of magnitude faster than software implementations.Since large data parallel programs often have several levels of nested barriers, these schemes provide significant speedups in the execution of such programs on MIMD computers.The first scheme performs code transformations and uses two single-bit-trees to implement unlimited levels of nested barriers.However, this scheme increases the code size.The second scheme uses a more expensive integer-tree to support an exponential number of nested barriers without increasing the code size.Using hardware already available on commercial MIMD computers, this scheme can support more than four billion levels of nesting.