Using load information in work-stealing on distributed systems with non-uniform communication latencies

Vladimir Janjic, Kevin Hammond

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

We evaluate four state-of-the-art work-stealing algorithms for distributed systems with non-uniform communication latenices (Random Stealing, Hierarchical Stealing, Cluster-aware Random Stealing and Adaptive Cluster-aware Random Stealing) on a set of irregular Divide-and-Conquer (D&C) parallel applications. We also investigate the extent to which these algorithms could be improved if dynamic load information is available, and how accurate this information needs to be. We show that, for highly-irregular D&C applications, the use of load information can significantly improve application speedups, whereas there is little improvement for less irregular ones. Furthermore, we show that when load information is used, Cluster-aware Random Stealing gives the best speedups for both regular and irregular D&C applications.

Original languageEnglish
Title of host publicationParallel Processing - 18th International Conference, Euro-Par 2012, Proceedings
EditorsChristos Kaklamanis, Theodore Papatheodorou, Paul G. Spirakis
Place of PublicationBerlin
PublisherSpringer
Pages155-166
Number of pages12
ISBN (Electronic)9783642328206
ISBN (Print)9783642328190
DOIs
Publication statusPublished - 2012
Event18th International Conference on Parallel Processing, Euro-Par 2012 - Rhodes Island, Greece
Duration: 27 Aug 201231 Aug 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7484
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Parallel Processing, Euro-Par 2012
CountryGreece
CityRhodes Island
Period27/08/1231/08/12

Keywords

  • Processing Element
  • Parallel Application
  • Runtime System
  • Load Information
  • Potential Victim

Fingerprint Dive into the research topics of 'Using load information in work-stealing on distributed systems with non-uniform communication latencies'. Together they form a unique fingerprint.

  • Cite this

    Janjic, V., & Hammond, K. (2012). Using load information in work-stealing on distributed systems with non-uniform communication latencies. In C. Kaklamanis, T. Papatheodorou, & P. G. Spirakis (Eds.), Parallel Processing - 18th International Conference, Euro-Par 2012, Proceedings (pp. 155-166). (Lecture Notes in Computer Science; Vol. 7484). Springer . https://doi.org/10.1007/978-3-642-32820-6_17