Programming heterogeneous parallel machines using refactoring and Monte-Carlo tree search

Christopher Mark Brown; Vladimir Janjic; M. Goli; John McCall

doi:10.1007/s10766-020-00665-z

Programming heterogeneous parallel machines using refactoring and Monte-Carlo tree search

Christopher Mark Brown, Vladimir Janjic, M. Goli, John McCall

Research output: Contribution to journal › Article › peer-review

10 Downloads (Pure)

Abstract

This paper presents a new technique for introducing and tuning parallelism for heterogeneous shared-memory systems (comprising a mixture of CPUs and GPUs), using a combination of algorithmic skeletons (such as farms and pipelines), Monte–Carlo tree search for deriving mappings of tasks to available hardware resources, and refactoring tool support for applying the patterns and mappings in an easy and effective way. Using our approach, we demonstrate easily obtainable, significant and scalable speedups on a number of case studies showing speedups of up to 41 over the sequential code on a 24-core machine with one GPU. We also demonstrate that the speedups obtained by mappings derived by the MCTS algorithm are within 5–15% of the best-obtained manual parallelisation.

Original language	English
Pages (from-to)	583–602
Number of pages	20
Journal	International Journal of Parallel Programming
Volume	48
Issue number	4
Early online date	10 Jun 2020
DOIs	https://doi.org/10.1007/s10766-020-00665-z
Publication status	Published - Aug 2020

Keywords

Heterogenous parallel computing
Monte-Carlo tree search
Optimisations

Access to Document

10.1007/s10766-020-00665-zLicence: CC BY

Brown2020_Article_ProgrammingHeterogeneousParall
Copyright © 2020 the Author(s). Open Access. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Final published version, 1.33 MBLicence: CC BY

TeamPlay: H2020 ICT-5 Teamplay
Brown, C. M. (PI)
European Commission
1/01/18 → 31/12/20
Project: Standard
Discovery: Pattern Discovery and Program: Discovery: Pattern Discovery and Program Shaping for Manycore Systems
Thomson, J. D. (PI), Hammond, K. (CoI) & Sarkar, S. (CoI)
EPSRC
1/07/17 → 31/12/20
Project: Standard

Christopher Mark Brown
- cmb21st-andrews.acuk
- School of Computer Science - Lecturer
Person: Academic

Cite this

@article{1d472917f52749cf8f350e3939539525,

title = "Programming heterogeneous parallel machines using refactoring and Monte-Carlo tree search",

abstract = "This paper presents a new technique for introducing and tuning parallelism for heterogeneous shared-memory systems (comprising a mixture of CPUs and GPUs), using a combination of algorithmic skeletons (such as farms and pipelines), Monte–Carlo tree search for deriving mappings of tasks to available hardware resources, and refactoring tool support for applying the patterns and mappings in an easy and effective way. Using our approach, we demonstrate easily obtainable, significant and scalable speedups on a number of case studies showing speedups of up to 41 over the sequential code on a 24-core machine with one GPU. We also demonstrate that the speedups obtained by mappings derived by the MCTS algorithm are within 5–15% of the best-obtained manual parallelisation.",

keywords = "Heterogenous parallel computing, Monte-Carlo tree search, Optimisations",

author = "Brown, {Christopher Mark} and Vladimir Janjic and M. Goli and John McCall",

note = "Funding: This work was supported by the EU Horizon 2020 project, TeamPlay, Grant Number 779882, and UK EPSRC Discovery, Grant Number EP/P020631/1.",

year = "2020",

month = aug,

doi = "10.1007/s10766-020-00665-z",

language = "English",

volume = "48",

pages = "583–602",

journal = "International Journal of Parallel Programming",

issn = "0885-7458",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Programming heterogeneous parallel machines using refactoring and Monte-Carlo tree search

AU - Brown, Christopher Mark

AU - Janjic, Vladimir

AU - Goli, M.

AU - McCall, John

N1 - Funding: This work was supported by the EU Horizon 2020 project, TeamPlay, Grant Number 779882, and UK EPSRC Discovery, Grant Number EP/P020631/1.

PY - 2020/8

Y1 - 2020/8

N2 - This paper presents a new technique for introducing and tuning parallelism for heterogeneous shared-memory systems (comprising a mixture of CPUs and GPUs), using a combination of algorithmic skeletons (such as farms and pipelines), Monte–Carlo tree search for deriving mappings of tasks to available hardware resources, and refactoring tool support for applying the patterns and mappings in an easy and effective way. Using our approach, we demonstrate easily obtainable, significant and scalable speedups on a number of case studies showing speedups of up to 41 over the sequential code on a 24-core machine with one GPU. We also demonstrate that the speedups obtained by mappings derived by the MCTS algorithm are within 5–15% of the best-obtained manual parallelisation.

AB - This paper presents a new technique for introducing and tuning parallelism for heterogeneous shared-memory systems (comprising a mixture of CPUs and GPUs), using a combination of algorithmic skeletons (such as farms and pipelines), Monte–Carlo tree search for deriving mappings of tasks to available hardware resources, and refactoring tool support for applying the patterns and mappings in an easy and effective way. Using our approach, we demonstrate easily obtainable, significant and scalable speedups on a number of case studies showing speedups of up to 41 over the sequential code on a 24-core machine with one GPU. We also demonstrate that the speedups obtained by mappings derived by the MCTS algorithm are within 5–15% of the best-obtained manual parallelisation.

KW - Heterogenous parallel computing

KW - Monte-Carlo tree search

KW - Optimisations

U2 - 10.1007/s10766-020-00665-z

DO - 10.1007/s10766-020-00665-z

M3 - Article

SN - 0885-7458

VL - 48

SP - 583

EP - 602

JO - International Journal of Parallel Programming

JF - International Journal of Parallel Programming

IS - 4

ER -

Programming heterogeneous parallel machines using refactoring and Monte-Carlo tree search

Abstract

Keywords

Access to Document

Fingerprint

Projects

TeamPlay: H2020 ICT-5 Teamplay

Discovery: Pattern Discovery and Program: Discovery: Pattern Discovery and Program Shaping for Manycore Systems

Profiles

Christopher Mark Brown

Cite this