History-based adaptive work distribution

Evgenij Belikov

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

1 Citation (Scopus)

Abstract

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
Pages3-10
Number of pages8
Volume43
ISBN (Print)9783939897767
DOIs
Publication statusPublished - 1 Jan 2014
Event4th Imperial College Computing Student Workshop - London, United Kingdom
Duration: 25 Sep 201426 Sep 2014

Conference

Conference4th Imperial College Computing Student Workshop
Abbreviated titleICCSW 2014
CountryUnited Kingdom
CityLondon
Period25/09/1426/09/14

Keywords

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

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modelling and Simulation

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

Cite this