Barrier synchronization over multistage interconnection networks

The paper identifies two barrier synchronization techniques that are appropriate for nonuniform memory architectures. The first of these two, the dissemination barrier, is based on a progressive skip-ring of flags. The second, called the reflected-tree barrier, is based on software combining trees. The dissemination barrier is optimal in terms of the number of barrier stages required by the algorithm. The reflected-tree barrier, however, is optimal in the number of remote network operations required for algorithm completion. These two are compared by means of probabilistic simulations up to 4096 nodes and actual execution results up to 90 nodes on a BBN GP-1000. These results show that the reflected-tree barrier is significantly better on 30 nodes or more