Synchronization Barrier Elimination in Synchronous FORALLs

This paper presents and evaluates a restructuring optimization technique for the compilation of synchronous FORALLs. Because of its elegant machine-independence we choose Modula-2*, a problem-oriented explicitly parallel programming language, as our conceptual framework. The presented optimization technique has improved runtime performance on Modula-2* benchmarks by over 40% on a MasPar MP-1 and by over 100% on sequential workstations. We present our approach in terms of a source-to-source transformation. The compiler analyzes programs that contain synchronous FORALLs and, hence, vast numbers of synchronization barriers. These are transformed into semantically equivalent programs that only contain asynchronous FORALLs, thus greatly simplifying the task of mapping them onto any parallel machine. The transformed programs run significantly faster since redundant synchronization barriers are eliminated. 1 Introduction Most parallel programmers consider the data parallel paradigm to be eas..