1. Programming Heterogeneous Parallel Machines Using Refactoring and Monte–Carlo Tree Search
- Author
-
Vladimir Janjic, Christopher Brown, Mehdi Goli, John McCall, European Commission, EPSRC, University of St Andrews. School of Computer Science, and University of St Andrews. Centre for Interdisciplinary Research in Computational Algebra
- Subjects
QA75 ,Monte-Carlo tree search ,Computer science ,Heterogenous parallel computing ,QA75 Electronic computers. Computer science ,T-NDAS ,Monte Carlo tree search ,Monte Carlo method ,02 engineering and technology ,Parallel computing ,computer.software_genre ,Theoretical Computer Science ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Code (cryptography) ,Algorithmic skeleton ,020207 software engineering ,Tree (data structure) ,Code refactoring ,Theory of computation ,Scalability ,BDC ,Optimisations ,computer ,Software ,Information Systems - Abstract
Funding: This work was supported by the EU Horizon 2020 project, TeamPlay, Grant Number 779882, and UK EPSRC Discovery, Grant Number EP/P020631/1. 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. Publisher PDF
- Published
- 2020
- Full Text
- View/download PDF