Automatic synchronization elimination in synchronous FORALLs
Michæl Philippsen, Ernst A. Heinz · Repository KITopen (Karlsruhe Institute of Technology) · 1995
This paper investigates a promising optimization technique that automatically eliminates redundant synchronization barriers in synchronous FORALLs. We present complete algorithms for the necessary program restructurings 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. 1 Introduction Data-parallel programs operate on all elements of a data structure simultaneously and are expressed with explicit or implic...