This paper presents a new compiler approach to minimizing the number of barriers executed in parallelized 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 generalized to accept entire, well-structured control-flow programs containing arbitrary nesting of IF constructs, loops, and subroutines. It has been implemented in a prototype parallelizing compiler and applied to several well-known benchmarks where it has been shown to place significantly fewer synchronization points than existing techniques. Experiments indicate that on average the number of barriers executed is reduced by 70 percent and there is a three fold improvement in execution time when evaluated on a 32-processor SGI Origin 2000.

This paper presents an overview of the activities carried out within the ESPRIT project OCEANS whose objective is to investigate and develop advanced compiler infrastructure for embedded VLIW processors. This combines high and low-level optimisation approaches within an iterative framework for compilation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

This paper presents a new graph theoretic approach to minimising the number of barriers in parallelised programs. A simple procedure to reduce the complexity of barrier placement, without affecting optimality, is developed. A new algorithm is then presented which places provably the minimal number of barriers in perfect loop nests. This technique is extended so as to place the minimal number of barriers in certain imperfect loop nest structures. This scheme is generalised to accept entire programs and implemented in a prototype parallelising compiler where it has been applied to several well-known benchmarks and shown to place significantly fewer synchronisation points than an existing commercial compiler. 1 Introduction Many widely-used parallel machines, such as the SGI challenge, Convex Exemplar and Sequent NumaQ, provide a shared address space. Such architectures are attractive as they are easier to program than message passing systems, speeding the implementation and porting of ...