%0 Journal Article %1 michael1994contentionfree %A Scott, Michael %A Mellor-Crummey, John %D 1994 %J International Journal of Parallel Programming %K Algorithms Barrier Fuzzy Optimization Tree synchronization %N 4 %P 449--481 %T Fast, Contention-Free Combining Tree Barriers for Shared-Memory Multiprocessors %U http://dx.doi.org/10.1007/BF02577741 %V 22 %X Abstract  In a previous article,(1) Gupta and Hill introduced anadaptive combining tree algorithm for busy-wait barrier synchronization on shared-memory multiprocessors. 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 arrivaltimes are skewed. Afuzzy(2) version of the algorithm allows a process to perform useful work between the point at which it notifies other processes ofits arrival and the point at which it waits for all other processes to arrive. Unfortunately, adaptive combining tree barriersas originally devised perform a large amount of work at each node of the tree, including the acquisition and release of locks.They also perform an unbounded number of accesses to nonlocal locations, inducing large amounts of memory and interconnectcontention. We present new adaptive combining tree barriers that eliminate these problems. We compare the performance of thenew algorithms to that of other fast barriers on a 64-node BBN Butterfly 1 multiprocessor, a 35-node BBN TC2000, and a 126-nodeKSR 1. The results reveal scenarios in which our algorithms outperform all known alternatives, and suggest that both adaptationand the combination of fuzziness with tree-style synchronization will be of increasing importance on future generations ofshared-memory multiprocessors.

@article{michael1994contentionfree, abstract = {Abstract  In a previous article,(1) Gupta and Hill introduced anadaptive combining tree algorithm for busy-wait barrier synchronization on shared-memory multiprocessors. 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 arrivaltimes are skewed. Afuzzy(2) version of the algorithm allows a process to perform useful work between the point at which it notifies other processes ofits arrival and the point at which it waits for all other processes to arrive. Unfortunately, adaptive combining tree barriersas originally devised perform a large amount of work at each node of the tree, including the acquisition and release of locks.They also perform an unbounded number of accesses to nonlocal locations, inducing large amounts of memory and interconnectcontention. We present new adaptive combining tree barriers that eliminate these problems. We compare the performance of thenew algorithms to that of other fast barriers on a 64-node BBN Butterfly 1 multiprocessor, a 35-node BBN TC2000, and a 126-nodeKSR 1. The results reveal scenarios in which our algorithms outperform all known alternatives, and suggest that both adaptationand the combination of fuzziness with tree-style synchronization will be of increasing importance on future generations ofshared-memory multiprocessors.}, added-at = {2010-01-20T19:56:21.000+0100}, author = {Scott, Michael and Mellor-Crummey, John}, biburl = {https://www.bibsonomy.org/bibtex/2a78310133cdfce5560bbfa8a236d10b8/gron}, description = {SpringerLink - Journal Article}, interhash = {44f5012de6a13367cc07a00b9a225bff}, intrahash = {a78310133cdfce5560bbfa8a236d10b8}, journal = {International Journal of Parallel Programming}, keywords = {Algorithms Barrier Fuzzy Optimization Tree synchronization}, month = {August}, number = 4, pages = {449--481}, timestamp = {2010-01-20T19:56:21.000+0100}, title = {Fast, Contention-Free Combining Tree Barriers for Shared-Memory Multiprocessors}, url = {http://dx.doi.org/10.1007/BF02577741}, volume = 22, year = 1994 }