Skip to content

Research at St Andrews

Granularity-Aware Work-Stealing for Computationally-Uniform Grids

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

DOI

Abstract

Good scheduling is important for ensuring effective use of Grid resources, while maximising parallel performance. In this paper, we show how a basic ``Random-Stealing'' load balancing algorithm for computational Grids can be improved by using information about the task granularity of parallel programs. We propose several strategies (SSL, SLL and LLL) for using granularity information to improve load balancing, presenting results both from simulations and from a real implementation (the Grid-GUM Runtime System for Parallel Haskell). We assume a common model of task creation which subsumes both master/worker and data-parallel programming paradigms under a task-stealing work distribution strategy. Overall, we achieve improvement in runtime of up to 19.4% for irregular problems in the real implementation, and up to 40% for the simulations (typical improvements of more that 15% for irregular programs, and from 5-10% for regular ones). Our results show that, for computationally-uniform Grids, advanced load balancing methods that exploit granularity information generally have the greatest impact on reducing the runtimes of irregular parallel programs. Moreover, the more irregular the program is, the better the improvements that can be achieved.
Close

Details

Original languageEnglish
Title of host publication2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid 2010)
PublisherIEEE
Pages123-134
Number of pages12
ISBN (Print)978-1-4244-6987-1
DOIs
Publication statusPublished - 2010
Event10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid), 2010 - Melbourne, Australia
Duration: 17 May 201020 May 2010

Conference

Conference10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid), 2010
CountryAustralia
CityMelbourne
Period17/05/1020/05/10

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: 45161401