文章基本信息

标题：PROBABILISTIC ANALYSIS OF LOAD-IMBALANCED PARALLEL APPLICATIONS WITH PARTIALLY ELIMINATED BARRIERS
本地全文：下载
作者：Naoki Yonezawa ; Ken'ichi Katou ; Issei Kino 等
期刊名称：日本オペレーションズ・リサーチ学会論文誌
印刷版ISSN：0453-4514
电子版ISSN：2188-8299
出版年度：2015
卷号：58
期号：2
页码：149-164
DOI：10.15807/jorsj.58.149
出版社：Japan Science and Technology Information Aggregator, Electronic
摘要：In order 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. As a result, we have found that the algorithm is more effective to the load-imbalanced program than load-balanced program. However, the degree of the load balance has not been discussed quantitatively. In this paper, we model the behavior of parallel programs. In our model, the execution time of a phase contained in a parallel program is represented as a random variable. To investigate how the degree of the load balance influences the performance of our algorithm, we varied the coefficient of variation (CV) of probability distribution which the random variable follows. Using the model, we evaluated the execution time of parallel programs which have four typical dependency patterns. Based on results, we found that theoretical results are consistent with experimental ones.