PROBABILISTIC ANALYSIS OF LOAD-IMBALANCED PARALLEL APPLICATIONS WITH PARTIALLY ELIMINATED BARRIERS

Access this Article

Search this Article

Author(s)

Abstract

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.

Journal

  • Journal of the Operations Research Society of Japan

    Journal of the Operations Research Society of Japan 58(2), 149-164, 2015

    The Operations Research Society of Japan

Codes

  • NII Article ID (NAID)
    130005083505
  • NII NACSIS-CAT ID (NCID)
    AA00703935
  • Text Lang
    ENG
  • ISSN
    0453-4514
  • NDL Article ID
    026498639
  • NDL Call No.
    Z53-M226
  • Data Source
    NDL  J-STAGE 
Page Top