History-based adaptive work distribution

Evgenij Belikov*

*Corresponding author for this work

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

1 Citation (Scopus)


Exploiting parallelism of increasingly heterogeneous parallel architectures is challenging due to the complexity of parallelism management. To achieve high performance portability whilst preserving high productivity, high-level approaches to parallel programming delegate parallelism management, such as partitioning and work distribution, to the compiler and the run-time system. Random work stealing proved efficient for well-structured workloads, but neglects potentially useful context information that can be obtained through static analysis or monitoring at run time and used to improve load balancing, especially for irregular applications with highly varying thread granularity and thread creation patterns. We investigate the effectiveness of an adaptive work distribution scheme to improve load balancing for an extension of Haskell which provides a deterministic parallel programming model and supports both shared-memory and distributed-memory architectures. This scheme uses a less random work stealing that takes into account information on past stealing successes and failures. We quantify run time performance, communication overhead, and stealing success of four divide-and-conquer and data parallel applications for three different update intervals on a commodity 64-core Beowulf cluster of multi-cores.

Original languageEnglish
Title of host publicationOpenAccess Series in Informatics
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages8
ISBN (Print)9783939897767
Publication statusPublished - 1 Jan 2014
Event4th Imperial College Computing Student Workshop - London, United Kingdom
Duration: 25 Sept 201426 Sept 2014


Conference4th Imperial College Computing Student Workshop
Abbreviated titleICCSW 2014
Country/TerritoryUnited Kingdom


  • Adaptive load balancing
  • Context-awareness
  • High-level parallel programming
  • History
  • Work stealing

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modelling and Simulation


Dive into the research topics of 'History-based adaptive work distribution'. Together they form a unique fingerprint.

Cite this