Abstract
Lock Coarsening: Eliminating Lock Overhead in AutomaticallyParallelized Object-Based Programs
by: Pedro Diniz and Martin Rinard
Abstract:
Atomic operations are a key primitive in parallel computing systems. Thestandard implementation mechanism for atomic operations uses mutual exclusionlocks. In an object-based programming system the natural granularity is togive each object its own lock. Each operation can then make its executionatomic by acquiring and releasing the lock for the object that it accesses.But this fine lock granularity may have high synchronization overhead becauseit maximizes the number of executed acquire and release constructs. To achievegood performance it may be necessary to reduce the overhead by coarsening thegranularity 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-basedprograms with atomic operations. We have implemented this technique in thecontext of a parallelizing compiler for irregular, object-based programs andused it to improve the generated parallel code. Experiments with twoautomatically parallelized applications show these algorithms to be effectivein reducing the lock overhead to negligible levels.
Keywords:
parallelizing compilers, synchronization, locking, commutativityanalysis, parallel computation
Date:
May 29, 1996
Document: 1996-07
