Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized
Object-based Programs
Pedro Diniz and Martin Rinard
Department of Computer Science,
University of California at Santa Barbara
Santa Barbara, CA 93106-5110
Abstract
Atomic operations are a key primitive in parallel computing systems. The standard
implementation mechanism for atomic operations uses mutual exclusion locks.
In an object-based programming system the natural granularity is to give each
object its own lock. Each operation can then make its execution atomic by
acquiring and releasing the lock for the object that it accesses. But this
fine lock granularity may have high synchronization overhead because it
maximizes the number of executed acquire and release constructs. To achieve good
performance it may be necessary to reduce the overhead by coarsening the
granularity at which the computation locks objects.
In this paper we describe a static analysis technique --- lock coarsening ---
designed to automatically increase the lock granularity in object-based programs
with atomic operations. We have implemented this technique in the context of a
parallelizing compiler for irregular, object-based programs and used it to improve
the generated parallel code. Experiments with two automatically parallelized
applications show these algorithms to be effective in reducing the lock overhead
to negligible levels.