Automatic synchronisation elimination in synchronous FORALLs

This paper investigates a promising optimization technique that automatically eliminates redundant synchronization barriers in synchronous FORALLs. We present complete algorithms for the necessary program restrictions and subsequent code generation. Furthermore, we discuss the correctness, complexity, and performance of our restructuring algorithm before we finally evaluate its practical usefulness by quantitative experimentation. The experimental evaluation results are very encouraging. An implementation of the optimization algorithms in our Modula-2* compiler eliminated more than 50% of the originally present synchronization barriers in a set of seven parallel benchmarks. This barrier reduction improved the execution times of the generated programs by over 40% on a MasPar MP-1 with 16384 processors and by over 100% on a sequential workstation