×

Probabilistic analysis of load-imbalanced parallel applications with partially eliminated barriers. (English) Zbl 1328.68038

Summary: 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.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI