Execution Time Estimation of Multithreaded Programs With Critical Sections

The ideal benefit of parallelizing/multithreading a program is diminished in practice by several factors such as hardware scaling, memory bandwidth, power constraints, and synchronization due to critical sections. Several models have been proposed in the past to estimate the resulting performance and extend the traditional Amdahl’s law. In this work, we focus on the effect of synchronization, and develop a model for the execution time estimation of multithreaded programs under the presence of critical sections. The proposed model is applicable to multiple different critical sections and generalizes and improves previously proposed models. Experimental results on simulated, synthetic and benchmark examples show that the proposed model provides accurate approximations.