Probabilistic analysis of parallel program with partially eliminated barriers

Proceedings of the 5th IEEE International Workshop on Multicore and Multithreaded Architectures and Algorithms (M2A2 2013, in conjunction with the 11th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA- 13)), 1840

Since barrier synchronization is a simple means to guarantee the order of data producing and data consuming, it is often used in parallel programs. However, barrier synchronization causes the processors' idle time to increase. To reduce the overhead of barrier synchronization, we have proposed an algorithm which eliminates barrier synchronizations and evaluated its validity experimentally in our previous study. In this paper, we model the behavior of parallel programs and proposed a dependency matrix to represent dependencies among processors. Using the behavioral model, we evaluated the execution time of parallel programs which have three typical dependency patterns. Based on results, we found that 1) if a processors depends on less other processors, the obtained effect of eliminating barriers is higher, 2) even if the number of directly-depended processors is the same between two dependency patterns, less indirectly-depended processors in all previous phases provide more effect of eliminating barriers.