License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICCSW.2014.3
URN: urn:nbn:de:0030-drops-47671
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4767/
Go to the corresponding OASIcs Volume Portal

Belikov, Evgenij

History-Based Adaptive Work Distribution

pdf-format:
p003-03-Belikou.pdf (1.0 MB)

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.

BibTeX - Entry

@InProceedings{belikov:OASIcs:2014:4767,
  author =	{Evgenij Belikov},
  title =	{{History-Based Adaptive Work Distribution}},
  booktitle =	{2014 Imperial College Computing Student Workshop},
  pages =	{3--10},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-76-7},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{43},
  editor =	{Rumyana Neykova and Nicholas Ng},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4767},
  URN =		{urn:nbn:de:0030-drops-47671},
  doi =		{10.4230/OASIcs.ICCSW.2014.3},
  annote =	{Keywords: Adaptive Load Balancing, Work Stealing, Work Pushing, High-Level Parallel Programming, Context-Awareness}
}

Keywords: Adaptive Load Balancing, Work Stealing, Work Pushing, High-Level Parallel Programming, Context-Awareness
Collection: 2014 Imperial College Computing Student Workshop
Issue Date: 2014
Date of publication: 08.10.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI