Synchronization Transformations for Parallel Computing

Pedro Diniz (


As parallel computing becomes part of the mainstream computing environment, compilers will need to apply the synchronization optimizations required to deliver efficient parallel software. This work describes a new framework for synchronization optimizations and a new set of transformations for programs that implement critical sections using mutual exclusion locks. These transformations allow the compiler to move constructs that acquire and release locks both within and between procedures and to eliminate acquire and release constructs.

We present a new synchronization algorithm, lock elimination, for reducing synchronization overhead. The basic idea is to locate computations that repeatedly acquire and release the same lock, then use the transformations to obtain equivalent computations that acquire and release the lock only once. Experimental results from a parallelizing compiler for object-based programs illustrate the practical utility of this optimization: it improves the overall performance of our two benchmark applications by a factor of 2.0 and a factor of 1.1, which reduces the synchronization overhead to negligible levels.

Related Publications