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


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.

Links and resources

BibTeX key:
search on:

Comments and Reviews  

There is no review or comment yet. You can write one!


Cite this publication