LOCK COARSENING - ELIMINATING LOCK OVERHEAD IN AUTOMATICALLY PARALLELIZED OBJECT-BASED PROGRAMS

Atomic operations are a key primitive in parallel computing systems. T he standard implementation mechanism for atomic operations uses mutual exclusion locks. In an object-based programming system, the natural g ranularity is to give each object its own lock. Each operation can the n make its execution atomic by acquiring and releasing the lock for th e object that it accesses. But this fine lock granularity may have hig h 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 whi ch the computation locks objects. In this article we describe a static analysis technique--lock coarsening-designed to automatically increas e 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 parall elized applications show these algorithms to be effective in reducing the lock overhead to negligible levels. The results also show, however , that an overly aggressive lock coarsening algorithm may harm the ove rall parallel performance by serializing sections of the parallel comp utation. A successful compiler must therefore negotiate a trade-off be tween reducing lock overhead and increasing the serialization. (C) 199 8 Academic Press.