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