Change search
ReferencesLink to record
Permanent link

Direct link
The cost of synchronizing imbalanced processes in message passing systems
KTH, School of Computer Science and Communication (CSC), Computational Science and Technology (CST).
KTH, School of Computer Science and Communication (CSC), Computational Science and Technology (CST).
KTH, School of Computer Science and Communication (CSC), Computational Science and Technology (CST).
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
Abstract [en]

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.
Keyword [en]
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
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-186851DOI: 10.1109/CLUSTER.2015.63ISI: 000378648100052ScopusID: 2-s2.0-84959308490ISBN: 9781467365987OAI: oai:DiVA.org:kth-186851DiVA: diva2:937281
Conference
IEEE International Conference on Cluster Computing, CLUSTER 2015, 8 September 2015 through 11 September 2015
Note

QC 20160615

Available from: 2016-06-15 Created: 2016-05-13 Last updated: 2016-07-26Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopusIEEE International Conference on Cluster Computing, CLUSTER 2015

Search in DiVA

By author/editor
Peng, I. B.Markidis, StefanoLaure, Erwin
By organisation
Computational Science and Technology (CST)
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

ReferencesLink to record
Permanent link

Direct link