A Graph Based Approach to Barrier Synchronisation Minimisation

Elena Stöhr, Michael F. P. O'Boyle

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper presents a new graph theoretic approach to minimising the number of barriers in parallelised programs. A simple procedure to reduce the complexity of barrier placement, without athscting optimality, is developed. A new algorithm is then presented which places provably the minimal number of barriers in perfect loop nests. This technique is extended so as to place the minimal number of barriers in certain imperfect loop nest structures. This scheme is generalised to accept entire programs and implemented in a prototype parallelising compiler where it has been applied to several well-known benchmarks and shown to place significantly fewer synchronisation points than an existing commercial compiler.
Original languageEnglish
Title of host publicationICS '97 Proceedings of the 11th international conference on Supercomputing
Number of pages8
ISBN (Print)0-89791-902-5
Publication statusPublished - 1997

Fingerprint Dive into the research topics of 'A Graph Based Approach to Barrier Synchronisation Minimisation'. Together they form a unique fingerprint.

Cite this