Static analysis to reduce synchronization costs in data-parallel programs

Abstract

A novel methodology is presented for reducing synchronization costs of programs compiled for SPMD execution. The methodology combines data flow analysis with communication analysis to determine the ordering between production and consumption of data on different processors. It is shown that several commonly occurring computation patterns lend themselves well to this optimization. The framework presented also recognizes situations where the synchronization needs for multiple data transfers can be satisfied by a single synchronization message. This analysis, while applicable to all shared memory machines as well, is especially useful for those with a flexible cache-coherence protocol.