How to be a Successful Thief: Feudal Work Stealing for Irregular Divide-and-Conquer Applications on Heterogeneous Distributed Systems

Vladimir Janjic, Kevin Hammond

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

Abstract

Work Stealing has proved to be an effective method for load balancing regular divide-and-conquer (D&C) applications on heteroge- neous distributed systems, but there have been relatively few attempts to adapt it to address irregular D&C applications. For such applications, it is essential to have a mechanism that can estimate dynamic system load during the execution of the applications. In this paper, we evaluate a number of work-stealing algorithms on a set of generic Unbalanced Tree Search (UTS) benchmarks. We present a novel Feudal Stealing work- stealing algorithm and show, using simulations, that it delivers consis- tently better speedups than other work-stealing algorithms for irregular D&C applications on high-latency heterogeneous distributed systems. Compared to the best known work-stealing algorithm for high-latency distributed systems, we achieve improvements of between 9% and 48% for irregular D&C applications.
Original languageEnglish
Title of host publicationProc. EuroPar 2013: European Conference on Parallelism
Place of PublicationAachen, Germany
Number of pages12
ISBN (Electronic)978-3-642-40047-6
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
Volume8097
ISSN (Print)0302-9743

Keywords

  • work stealing
  • load balancing
  • parallelism
  • high-performance computing
  • divide-and-conquer

Fingerprint

Dive into the research topics of 'How to be a Successful Thief: Feudal Work Stealing for Irregular Divide-and-Conquer Applications on Heterogeneous Distributed Systems'. Together they form a unique fingerprint.

Cite this