%0 Journal Article %1 debra1988algorithms %A Hensgen, Debra %A Finkel, Raphael %A Manber, Udi %D 1988 %J International Journal of Parallel Programming %K Algorithms Barrier Dissemination Evaluation Tournament implementation %N 1 %P 1--17 %T Two Algorithms for Barrier Synchronization %U http://dx.doi.org/10.1007/BF01379320 %V 17 %X We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to Brooks. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brook's communication pattern with an information dissemination algorithm described by Han and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brook's original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of then processes meeting at the barrier must be assigned identifiersi such that 0=in. ER -

@article{debra1988algorithms, abstract = {We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to Brooks. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brook's communication pattern with an information dissemination algorithm described by Han and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brook's original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of then processes meeting at the barrier must be assigned identifiersi such that 0=in. ER -}, added-at = {2010-01-11T16:43:01.000+0100}, author = {Hensgen, Debra and Finkel, Raphael and Manber, Udi}, biburl = {https://www.bibsonomy.org/bibtex/2d66d344183f47511f5d79f24604353d7/gron}, description = {SpringerLink - Journal Article}, interhash = {9bdc9ac6deb0a7ccf3c18235e283d257}, intrahash = {d66d344183f47511f5d79f24604353d7}, journal = {International Journal of Parallel Programming}, keywords = {Algorithms Barrier Dissemination Evaluation Tournament implementation}, month = {February}, number = 1, pages = {1--17}, timestamp = {2010-01-11T16:43:01.000+0100}, title = {Two Algorithms for Barrier Synchronization}, url = {http://dx.doi.org/10.1007/BF01379320}, volume = 17, year = 1988 }