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

4 Citations (Scopus)

Abstract

Work Stealing has proved to be an effective method for load balancing regular divide-and-conquer (D&C) applications on heterogeneous 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 consistently 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 publicationEuro-Par 2013 Parallel Processing - 19th International Conference, Proceedings
EditorsFelix Wolf, Bernd Mohr, Dieter an Mey
Place of PublicationBerlin
PublisherSpringer
Pages114-125
Number of pages12
ISBN (Electronic)9783642400476
ISBN (Print)9783642400469
DOIs
Publication statusPublished - 2013
Event19th International Conference on Parallel Processing, Euro-Par 2013 - Aachen, Germany
Duration: 26 Aug 201330 Aug 2013

Publication series

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

Conference

Conference19th International Conference on Parallel Processing, Euro-Par 2013
Country/TerritoryGermany
CityAachen
Period26/08/1330/08/13

Keywords

  • Divide-and-Conquer
  • Heterogeneous Systems
  • Irregular Parallelism
  • Work Stealing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

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