Skip to content

Research at St Andrews

Mapping parallel programs to heterogeneous CPU/GPU architectures using a Monte Carlo Tree Search

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


The single core processor, which has dominated for over 30 years, is now obsolete with recent trends increasing towards parallel systems, demanding a huge shift in programming techniques and practices. Moreover, we are rapidly moving towards an age where almost all programming will be targeting parallel systems. Parallel hardware is rapidly evolving, with large heterogeneous systems, typically comprising a mixture of CPUs and GPUs, becoming the mainstream. Additionally, with this increasing heterogeneity comes increasing complexity: not only does the programmer have to worry about where and how to express the parallelism, they must also express an efficient mapping of resources to the available system. This generally requires in-depth expert knowledge that most application programmers do not have. In this paper we describe a new technique that derives, automatically, optimal mappings for an application onto a heterogeneous architecture, using a Monte Carlo Tree Search algorithm. Our technique exploits high-level design patterns, targeting a set of well-specified parallel skeletons. We demonstrate that our MCTS on a convolution example obtained speedups that are within 5% of the speedups achieved by a hand-tuned version of the same application.


Original languageEnglish
Title of host publication2013 IEEE Congress on Evolutionary Computation, CEC 2013
Number of pages8
ISBN (Electronic)9781479904525
ISBN (Print)9781479904532
Publication statusPublished - 20 Jun 2013

    Research areas

  • Monte Carlo Tree Search, Heuristic algorithm, Static mapping, Parallel programming, Heterogenous architecture

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V., Feb 2018, In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  2. Lapedo: hybrid skeletons for programming heterogeneous multicore machines in Erlang

    Janjic, V., Brown, C. M. & Hammond, K., Apr 2016, Parallel Computing: On the Road to Exascale. Joubert, G. R., Leather, H., Parsons, M., Peters, F. & Sawyer, M. (eds.). IOS Press, p. 185-195 (Advances in Parallel Computing; vol. 27).

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

  3. RPL: a domain-specific language for designing and implementing parallel C++ applications

    Janjic, V., Brown, C. M., MacKenzie, K. W., Hammond, K., Danelutto, M., Aldinucci, M. & Garcia, D. J., 31 Mar 2016, 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP). Cotronis, Y., Daneshtalab, M. & Papadopoulos, G. A. (eds.). Institute of Electrical and Electronics Engineers Inc., p. 288-295 7445342

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

  4. Space exploration using parallel orbits: a study in parallel symbolic computing

    Janjic, V., Brown, C. M., Neunhoeffer, M., Hammond, K., Linton, S. A. & Loidl, H-W., Sep 2013, Parallel Computing: Accelerating Computational Science and Engineering (CSE). Bader, M., Bode, A., Bungartz, H-J., Gerndt, M., Joubert, G. R. & Peters, F. (eds.). IOS Press, Vol. 25. p. 225-232 8 p. (Advances in Parallel Computing).

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

ID: 51070558