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.
This project is funded by CoDeR-MP