Skip to content

Research at St Andrews

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

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


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
Publication statusPublished - 2013

Publication series

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

    Research areas

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

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V., Feb 2018, In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  2. HPC-GAP: engineering a 21st-century High-Performance Computer algebra system

    Behrends, R., Hammond, K., Janjic, V., Konovalov, A., Linton, S. A., Loidl, H-W., Maier, P. & Trinder, P., 10 Sep 2016, In : Concurrency and Computation : Practice and Experience. 28, 13, p. 3606-3636 33 p.

    Research output: Contribution to journalArticle

  3. Lapedo: hybrid skeletons for programming heterogeneous multicore machines in Erlang

    Janjic, V., Brown, C. M. & Hammond, K., Apr 2016, Parallel Computing: On the Road to Exascale. Joubert, G. R., Leather, H., Parsons, M., Peters, F. & Sawyer, M. (eds.). IOS Press, p. 185-195 (Advances in Parallel Computing; vol. 27).

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

  4. RPL: a domain-specific language for designing and implementing parallel C++ applications

    Janjic, V., Brown, C. M., MacKenzie, K. W., Hammond, K., Danelutto, M., Aldinucci, M. & Garcia, D. J., 31 Mar 2016, 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP). Cotronis, Y., Daneshtalab, M. & Papadopoulos, G. A. (eds.). Institute of Electrical and Electronics Engineers Inc., p. 288-295 7445342

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

  5. Kindergarten Cop: dynamic nursery resizing for GHC

    Ferreiro, H., Castro, L., Janjic, V. & Hammond, K., 17 Mar 2016, CC 2016 Proceedings of the 25th International Conference on Compiler Construction . New York: ACM, p. 56-66 10 p.

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

ID: 52294326