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. Learning-based dynamic pinning of parallelized applications in many-core systems

    Chasparis, G., Rossbory, M., Janjic, V. & Hammond, K., 21 Mar 2019, Proceedings 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2019). Institute of Electrical and Electronics Engineers Inc., 8 p. 8671569

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

  2. 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

  3. Efficient dynamic pinning of parallelized applications by reinforcement learning with applications

    Chasparis, G., Rossbory, M. & Janjic, V., 1 Aug 2017, Euro-Par 2017: Parallel Processing: 23rd International Conference on Parallel and Distributed Computing, Santiago de Compostela, Spain, August 28 – September 1, 2017, Proceedings. Rivera, F. F., Pena, T. F. & Cabaleiro, J. C. (eds.). Cham: Springer, p. 164-176 13 p. (Lecture Notes in Computer Science (Theoretical Computer Science and General Issues); vol. 10417).

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

  4. 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

ID: 52294326