Title :
A probabilistic analysis of a barrier eliminating algorithm
Author :
Yonezawa, Naoki ; Kino, Issei ; Wada, Koichi
Author_Institution :
Dept. of Inf. & Comput. Sci., Kanagawa Univ., Hiratsuka, Japan
Abstract :
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 this paper, we model the behavior of parallel programs and stochastically analyze our algorithm. Using the behavioral model, we evaluated the execution time before eliminating barrier synchronizations as well as after eliminating barrier synchronizations. As a result, we confirmed the observation, which we have found experimentally, that is, the ratio of improvement increases as the number of processors increases.
Keywords :
parallel algorithms; probability; program compilers; stochastic processes; synchronisation; barrier eliminating algorithm; barrier synchronization; parallel programs; probabilistic analysis; stochastic process; Algorithm design and analysis; Computer science; Concurrent computing; Costs; Information analysis; Jacobian matrices; Mathematical model; Message passing; Personal communication networks; Upper bound;
Conference_Titel :
Communications, Computers and Signal Processing, 2009. PacRim 2009. IEEE Pacific Rim Conference on
Conference_Location :
Victoria, BC
Print_ISBN :
978-1-4244-4560-8
Electronic_ISBN :
978-1-4244-4561-5
DOI :
10.1109/PACRIM.2009.5291318
