Informatics Report Series


Report   

EDI-INF-RR-0499


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Compile Time Barrier Synchronisation Minimisation
Authors: Michael O'Boyle ; Elena A. Stohr
Date:Jun 2002
Publication Title:IEEE Transactions on Parallel and Distributed Systems (TPDS)
Publisher:IEEE Computer Society
Publication Type:Journal Article Publication Status:Published
Volume No:13(6) Page Nos:529-543
DOI:10.1109/TPDS.2002.1011394
Abstract:
This paper presents a new compiler approach to minimising the number of barriers executed in parallelised programs. A simple procedure is developed to reduce the complexity of barrier placement by eliminating certain data dependences, without affecting optimality. An algorithm is presented which, provably, places the minimal number of barriers in perfect loop nests and in certain imperfect loop nest structures. This scheme is generalised to accept entire, well-structured control-low programs containing arbitrary nesting of IF constructs, loops and subroutines. It has been implemented in a prototype parallelising compiler and applied to several well-known benchmarks where it has been shown to place significantly fewer synchronisation points than existing techniques. Experiments indicate that on average the number of barriers executed is reduced by 70% and there is a 3 fold improvement in execution time when evaluated on a 32-processor SGI Origin 2000.
Links To Paper
1st Link
Bibtex format
@Article{EDI-INF-RR-0499,
author = { Michael O'Boyle and Elena A. Stohr },
title = {Compile Time Barrier Synchronisation Minimisation},
journal = {IEEE Transactions on Parallel and Distributed Systems (TPDS)},
publisher = {IEEE Computer Society},
year = 2002,
month = {Jun},
volume = {13(6)},
pages = {529-543},
doi = {10.1109/TPDS.2002.1011394},
url = {http://www.dcs.ed.ac.uk/home/mob/ieee02.ps},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh