IAS Seminar "Queue Delegation Locking"

The scalability of parallel programs is often bounded by the performance of synchronization mechanisms used to protect critical sections. The performance of these mechanisms is in turn determined by their sequential execution time, efficient use of hardware, and use of waiting time. In this talk, we will describe queue delegation locking, a family of locks that both delegate critical sections and enable detaching execution. Threads delegate work to the thread currently holding the lock and are able to detach, i.e. immediately continue their execution until they need a result from a previously delegated critical section. We show how to use queue delegation to build synchronization algorithms with lower overhead and higher throughput than existing algorithms, even when critical sections need to communicate results back. Experiments on a shared priority queue show that queue delegation outperforms leading synchronization algorithms by up to 115% when only half of the critical sections can be fully detached.

Last but not least, continuing execution instead of waiting for the execution of critical sections leads to better scalability than existing algorithms. Thanks to its simple building blocks, even its uncontended overhead is low, making queue delegation locking useful in a wide variety of applications. Time permitting, we will describe how and why queue delegation locking is a crucial component of ArgoDSM, a system for scalable distributed shared memory.

Anyone interested is cordially invited to participate in this seminar.
Contact: Dr. Sabine Höfler-Thierfeldt, JSC