DocumentCode :
1959554
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
fYear :
2009
fDate :
23-26 Aug. 2009
Firstpage :
503
Lastpage :
508
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/PACRIM.2009.5291318
Filename :
5291318
Link To Document :
بازگشت