Report ID
1996-07
Report Authors
Pedro Diniz and Martin Rinard
Report Date
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.
Document
1996-07.ps401.11 KB