Single-Job Dynamic Parallelism Scaling through Lock Contention Monitoring

Abstract

Harnessing available parallelism resources is an important but complicated task. Lock contention is one such factor that complicates this task and is of major concern, since locks and locking constructs are used heavily in multithreaded code. When an application experiences changing levels of lock contention, simply allocating a fixed level of parallelism may cause resource waste and performance loss. The work presented here introduces the idea of dynamically scaling up or down the level of parallelism by monitoring the current level of lock contention. This is done by keeping track of lock acquisition failures and using that metric as an estimator for the current level of lock contention. This dynamic scaling approach was evaluated using the parallel Boruvka’s MST algorithm, which exhibits rising levels of lock contention. The algorithm was tested using different input graphs and the speedup of the dynamic scaling was recorded relative to the original parallel version.