Skip to main content

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

Marr, Stefan and Verhaegen, Stijn and De Fraine, Bruno and D'Hondt, Theo and De Meuter, Wolfgang (2010) Insertion Tree Phasers: Efficient and Scalable Barrier Synchronization for Fine-grained Parallelism. In: 2010 IEEE 12th International Conference on High Performance Computing and Communications (HPCC). IEEE, pp. 130-137. ISBN 978-1-4244-8335-8. (doi:10.1109/HPCC.2010.30) (KAR id:63847)

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.

Item Type: Book section
DOI/Identification number: 10.1109/HPCC.2010.30
Additional information: Best Student Paper Award, Acceptance Rate: 19,1% (58/304)
Uncontrolled keywords: synchronization; radiation detectors; clocks; parallel processing; data structures; heuristic algorithms; scalability
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Stefan Marr
Date Deposited: 08 Nov 2017 23:24 UTC
Last Modified: 16 Nov 2021 10:24 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/63847 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.