- 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},
- }
|