Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism
S. Marr, S. Verhaegen, B. De Fraine, T. D'Hondt, and W. De Meuter. Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications, page 130-137. IEEE Computer Society, (September 2010)Best Student Paper AwardAcceptance Rate: 19,1% (58/304).
DOI: 10.1109/HPCC.2010.30
Abstract
This paper presents an algorithm and a data structure for scalable dynamic synchronization in
fine-grained parallelism. The algorithm supports the full generality of phasers with
dynamic, two-phase, and point-to-point synchronization. It retains the scalability of
classical tree barriers, but provides unbounded dynamicity by employing a tailor-made
insertion tree data structure.
It is the first completely documented implementation strategy for a scalable phaser
synchronization construct. Our evaluation shows that it can be used
as a drop-in replacement for classic barriers without harming performance, despite its additional
complexity and potential for performance optimizations.
Furthermore, our approach overcomes performance and scalability limitations
which have been present in other phaser proposals.
%0 Conference Paper
%1 InsertionTreePhasers
%A Marr, Stefan
%A Verhaegen, Stijn
%A De Fraine, Bruno
%A D'Hondt, Theo
%A De Meuter, Wolfgang
%B Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications
%D 2010
%I IEEE Computer Society
%K Barrier MeMyPublication Phasers X10 algorithm benchmarks clocks evaluation habanero insertionTree myown tree
%P 130-137
%R 10.1109/HPCC.2010.30
%T Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism
%U http://www.stefan-marr.de/2010/07/insertion-tree-phasers-efficient-and-scalable-barrier-synchronization-for-fine-grained-parallelism/
%X This paper presents an algorithm and a data structure for scalable dynamic synchronization in
fine-grained parallelism. The algorithm supports the full generality of phasers with
dynamic, two-phase, and point-to-point synchronization. It retains the scalability of
classical tree barriers, but provides unbounded dynamicity by employing a tailor-made
insertion tree data structure.
It is the first completely documented implementation strategy for a scalable phaser
synchronization construct. Our evaluation shows that it can be used
as a drop-in replacement for classic barriers without harming performance, despite its additional
complexity and potential for performance optimizations.
Furthermore, our approach overcomes performance and scalability limitations
which have been present in other phaser proposals.
%@ 978-0-7695-4214-0
@inproceedings{InsertionTreePhasers,
abstract = {This paper presents an algorithm and a data structure for scalable dynamic synchronization in
fine-grained parallelism. The algorithm supports the full generality of phasers with
dynamic, two-phase, and point-to-point synchronization. It retains the scalability of
classical tree barriers, but provides unbounded dynamicity by employing a tailor-made
insertion tree data structure.
It is the first completely documented implementation strategy for a scalable phaser
synchronization construct. Our evaluation shows that it can be used
as a drop-in replacement for classic barriers without harming performance, despite its additional
complexity and potential for performance optimizations.
Furthermore, our approach overcomes performance and scalability limitations
which have been present in other phaser proposals.},
added-at = {2010-09-22T15:13:52.000+0200},
author = {Marr, Stefan and Verhaegen, Stijn and De Fraine, Bruno and D'Hondt, Theo and De Meuter, Wolfgang},
biburl = {https://www.bibsonomy.org/bibtex/2e0e488ee39b6fcbeedb6f7d221df958a/gron},
blog = {http://stefan-marr.de/2010/07/insertion-tree-phasers-efficient-and-scalable-barrier-synchronization-for-fine-grained-parallelism/},
booktitle = {Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications},
doi = {10.1109/HPCC.2010.30},
interhash = {db46bfb816422a5055237a1b387e3dfe},
intrahash = {e0e488ee39b6fcbeedb6f7d221df958a},
isbn = {978-0-7695-4214-0},
keywords = {Barrier MeMyPublication Phasers X10 algorithm benchmarks clocks evaluation habanero insertionTree myown tree},
month = {September},
note = {Best Student Paper AwardAcceptance Rate: 19,1% (58/304)},
pages = {130-137},
pdf = {http://www.stefan-marr.de/downloads/hpcc2010-marr-etal-insertion-tree-phasers.pdf},
publisher = {IEEE Computer Society},
series = {HPCC'10},
timestamp = {2018-08-26T13:46:09.000+0200},
title = {Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism},
url = {http://www.stefan-marr.de/2010/07/insertion-tree-phasers-efficient-and-scalable-barrier-synchronization-for-fine-grained-parallelism/},
year = 2010
}