The cost of synchronizing imbalanced processes in message passing systems
2015 (English)In: Proceedings - IEEE International Conference on Cluster Computing, ICCC, Institute of Electrical and Electronics Engineers (IEEE), 2015, 408-417 p.Conference paper (Refereed)Text
Synchronization in message passing systems is achieved by communication among processes. System and architectural noise and different workloads cause processes to be imbalanced and to reach synchronization points at different time. Thus, both communication and imbalance impact the synchronization performance. In this paper, we study the algorithmic properties that allow the communication in synchronization to absorb the initial imbalance among processes. We quantify the imbalance absorption properties of different barrier algorithms using a LogP Monte Carlo simulator. We found that linear and f-way tournament barriers can absorb up to 95% of random exponential imbalance with the standard deviation equal to the communication time for one message. Dissemination, butterfly and pairwise exchange barriers, on the other hand, do not absorb imbalance but can effectively bound the post-barrier imbalance. We identify that synchronization transits from communication-dominated to imbalance-dominated when the standard deviation of imbalance distribution is more than twice the communication time for one message. In our study, f-way tournament barriers provided the best imbalance absorption rate and convenient communication time.
Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2015. 408-417 p.
Message Passing, Monte Carlo Simulations, Performance Modeling, Synchronization, Cluster computing, Computer architecture, Intelligent systems, Monte Carlo methods, Statistics, Absorption property, Algorithmic properties, Imbalance distributions, Message passing systems, Monte Carlo simulators, Performance Model, Synchronization performance, Synchronization points
IdentifiersURN: urn:nbn:se:kth:diva-186851DOI: 10.1109/CLUSTER.2015.63ISI: 000378648100052ScopusID: 2-s2.0-84959308490ISBN: 9781467365987OAI: oai:DiVA.org:kth-186851DiVA: diva2:937281
IEEE International Conference on Cluster Computing, CLUSTER 2015, 8 September 2015 through 11 September 2015
QC 201606152016-06-152016-05-132016-07-26Bibliographically approved