Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism

Stefan Marr; Stijn Verhaegen; Bruno De Fraine; Theo D'Hondt; Wolfgang De Meuter

doi:10.1109/HPCC.2010.30

Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism

Stefan Marr, Stijn Verhaegen, Bruno De Fraine, Theo D'Hondt, Wolfgang De Meuter

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

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.

Original language	English
Title of host publication	Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications
Publisher	IEEE Computer Society 2012
Pages	130-137
Number of pages	8
ISBN (Print)	978-0-7695-4214-0
DOIs	https://doi.org/10.1109/HPCC.2010.30
Publication status	Published - 01 Sept 2010
Externally published	Yes

Publication series

Name	HPCC
Publisher	IEEE Computer Society

Fields of science

102 Computer Sciences

Access to Document

10.1109/HPCC.2010.30

http://www.stefan-marr.de/2010/07/insertion-tree-phasers-efficient-and-scalable-barrier-synchronization-for-fine-grained-parallelism/

Cite this

Marr, S., Verhaegen, S., De Fraine, B., D'Hondt, T., & De Meuter, W. (2010). Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism. In Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications (pp. 130-137). Article 5581443 (HPCC). IEEE Computer Society 2012. https://doi.org/10.1109/HPCC.2010.30

@inproceedings{9fdd3f5a16a2407aaef1d0860986473e,

title = "Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism",

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.",

keywords = "Barrier MeMyPublication Phasers X10 algorithm benchmarks clocks evaluation habanero insertionTree myown tree",

author = "Stefan Marr and Stijn Verhaegen and \{De Fraine\}, Bruno and Theo D'Hondt and \{De Meuter\}, Wolfgang",

note = "Best Student Paper AwardAcceptance Rate: 19,1\% (58/304)",

year = "2010",

month = sep,

day = "1",

doi = "10.1109/HPCC.2010.30",

language = "English",

isbn = "978-0-7695-4214-0",

series = "HPCC",

publisher = "IEEE Computer Society 2012",

pages = "130--137",

booktitle = "Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications",

}

Marr, S, Verhaegen, S, De Fraine, B, D'Hondt, T & De Meuter, W 2010, Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism. in Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications., 5581443, HPCC, IEEE Computer Society 2012, pp. 130-137. https://doi.org/10.1109/HPCC.2010.30

Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism. / Marr, Stefan; Verhaegen, Stijn; De Fraine, Bruno et al.
Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications. IEEE Computer Society 2012, 2010. p. 130-137 5581443 (HPCC).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

TY - GEN

T1 - Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism

AU - Marr, Stefan

AU - Verhaegen, Stijn

AU - De Fraine, Bruno

AU - D'Hondt, Theo

AU - De Meuter, Wolfgang

N1 - Best Student Paper AwardAcceptance Rate: 19,1% (58/304)

PY - 2010/9/1

Y1 - 2010/9/1

N2 - 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.

AB - 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.

KW - Barrier MeMyPublication Phasers X10 algorithm benchmarks clocks evaluation habanero insertionTree myown tree

UR - https://www.scopus.com/pages/publications/78149349249

U2 - 10.1109/HPCC.2010.30

DO - 10.1109/HPCC.2010.30

M3 - Conference proceedings

SN - 978-0-7695-4214-0

T3 - HPCC

SP - 130

EP - 137

BT - Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications

PB - IEEE Computer Society 2012

ER -

Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism

Abstract

Publication series

Fields of science

Access to Document

Other files and links

Cite this