Granularity-aware work-stealing for computationally-uniform Grids

Vladimir Janjic, Kevin Hammond

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

11 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationCCGrid 2010 - 10th IEEE/ACM International Conference on Cluster, Cloud, and Grid Computing
PublisherIEEE
Pages123-134
Number of pages12
ISBN (Electronic)9781424469888, 9780769540399
ISBN (Print)9781424469871
DOIs
Publication statusPublished - 24 Jun 2010
Event10th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2010 - Melbourne, VIC, Australia
Duration: 17 May 201020 May 2010

Conference

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

Keywords

  • Computational grids
  • Granularity
  • Grid-GUM
  • Haskell
  • Load-balancing
  • Performance measurement
  • Simulation
  • Work-stealing

Fingerprint Dive into the research topics of 'Granularity-aware work-stealing for computationally-uniform Grids'. Together they form a unique fingerprint.

Cite this