A graph based approach to barrier synchronisation minimisation
Elena A. Stöhr, Michael O’Boyle · 1997
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 ...