Synchronization Transformations for Parallel Computing
Pedro Diniz (pedro@isi.edu)
Summary
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