Probabilistic analysis of time reduction by eliminating barriers in parallel programmes

摘要

Since barrier synchronisation is a simple means to guarantee the order of data producing and data consuming, it is often used in parallel programmes. However, barrier synchronisation causes the processors' idle time to increase. To reduce the overhead of barrier synchronisation, we have proposed an algorithm which eliminates barrier synchronisations and evaluated its validity experimentally. In this paper, we model the behaviour of parallel programmes and stochastically analyse our algorithm. Using the behavioural model, we evaluated the execution time before eliminating barrier synchronisations as well as after eliminating barrier synchronisations. As a result, we confirmed the observations, which we have found experimentally, that is