Contention-Free Combining Tree Barriers for Shared-Memory Multiprocessors

In a previous article," ' Gupta and Hill introduced an ucluptiw fmnbittit~g tree algorithm for busy-wait barrier synchronization on shared-memory multipro-cessors. The intent of the algorithm was to achieve a barrier in logarithmic time when processes arrive simultaneously, and in constant time after the last arrival when arrival times are skewed. A fuzzy' " version of the algorithm allows a process to perform useful work between the point at which it notifies other pro-cesses of its arrival and the point at which it waits for all other processes to arrive. Unfortunately, adaptive combining tree barriers as originally devised perform a large amount of work at each node of the tree, including the acquisi-tion and release of locks. They also perform an unbounded number of accesses to nonlocal locations, inducing large amounts of memory and interconnect contention. We present new adaptive combining tree barriers that eliminate these problems. We compare the performance of the new algorithms to that of other fast barriers on a 64-node BBN Butterfly 1 multiprocessor, a 35-node BBN TC2000. and a 126-node KSR 1. The results reveal scenarios in which ou