Projects per year
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 language | English |
---|---|
Title of host publication | Proc. EuroPar 2013: European Conference on Parallelism |
Place of Publication | Aachen, Germany |
Number of pages | 12 |
ISBN (Electronic) | 978-3-642-40047-6 |
DOIs | |
Publication status | Published - 2013 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 8097 |
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.Projects
- 4 Finished
-
-
FP7 ADVANCE: EU FP7 'Asynchronous and Dynamic Virtualisation through performance Analysis to support Concurrency Engineering 'ADVANCE'
Hammond, K. (PI) & Brady, E. C. (CoI)
1/02/10 → 30/09/13
Project: Standard
-
HPC-GAP: High performance computational: HPC-GAP High Performance Computational Algebra and Discrete Mathematics
Linton, S. A. (PI), Gent, I. P. (CoI) & Hammond, K. (CoI)
1/09/09 → 28/02/14
Project: Standard