Synchronization Modeling

Motivation

Synchronization is an indispensable part of parallel programs. Understanding the influence of synchronization is important for understanding the scalability of parallel programs. However this has not been thoroughly studied. The factors contributing to the synchronization cost are not clear and their impact has not been quantified. To show how synchronization can affect the parallel program's performance, we use the following example.

We have a parallel program with four threads sharing a lock (The red part are the critical section and the snake shaped lines are contending for the critical section). In the worst case, all parallel parts but one will contend (This happens when all threads are trying to enter critical section at the same time but only one of them can succeed, as shown on the left in Figure 1 and the synchronization fraction turns into a sequential fraction. In the best case, no parallel part contend (as shown on the right in Figure 1 and it turns into a parallel part. In this example, the performance of the parallel program is dependent on the accesses to the critical section.

Long Term Goal

• Understand the affecting factors in synchronization (we consider three kinds of most widely used methods of synchronization: synchronization via critical section, conditional variable and barriers)
• Predict the average time spent in synchronization and its impact on the scalability of a parallel program on multi-core architectures

Teaching results

Course on Models for performance analysis of concurrent programs (Spring 2010)

Funding

This project is funded by CoDeR-MP

Staff

Senior: Bengt Jonsson
Ph.D students: Jonatan Lindén, Xiaoyue Pan

internal project page