Skip to content

Research at St Andrews

In search of a map: using program slicing to discover potential parallelism in recursive functions

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

Abstract

Recursion schemes, such as the well-known map, can be used as loci of potential parallelism, where schemes are replaced with an equivalent parallel implementation. This paper formalises a novel technique, using program slicing, that automatically and statically identifies computations in recursive functions that can be lifted out of the function and then potentially performed in parallel. We define a new program slicing algorithm, build a prototype implementation, and demonstrate its use on 12 Haskell examples, including benchmarks from the NoFib suite and functions from the standard Haskell Prelude. In all cases, we obtain the expected results in terms of finding potential parallelism. Moreover, we have tested our prototype against synthetic benchmarks, and found that our prototype has quadratic time complexity. For the NoFib benchmark examples we demonstrate that relative parallel speedups can be obtained (up to 32.93x the sequential performance on 56 hyperthreaded cores).
Close

Details

Original languageEnglish
Title of host publicationProceedings of the 6th ACM SIGPLAN International Workshop on Functional High-Performance Computing (FHPC 2017)
Place of PublicationNew York
PublisherACM
Pages30-41
ISBN (Electronic)9781450351812
DOIs
Publication statusPublished - 7 Sep 2017
EventFHPC 2017 Workshop on Functional High-Performance Computing - Oxford, United Kingdom
Duration: 7 Sep 20177 Sep 2017
https://icfp17.sigplan.org/track/FHPC-2017-papers

Workshop

WorkshopFHPC 2017 Workshop on Functional High-Performance Computing
Abbreviated titleFHPC
CountryUnited Kingdom
CityOxford
Period7/09/177/09/17
Internet address

    Research areas

  • Program slicing, Recursion schemes, Patten discovery, Parallelism

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

View graph of relations

Related by author

  1. A hybrid approach to parallel pattern discovery in C++

    Brown, C. M., Janjic, V., Barwell, A. D., Thomson, J. D., Castañeda Lozano, R., Cole, M., Franke, B., Garcia-Sanchez, J. D., Del Rio Astorga, D. & MacKenzie, K., 1 Dec 2019, (Accepted/In press) 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). IEEE Computer Society

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

  2. Reasoning about non-functional properties using compiler intrinsic function annotations

    Jadhav, S., Roth, M., Falk, H., Brown, C. M. & Barwell, A. D., 6 Nov 2019, Proceedings of the 13th Junior Researcher Workshop on Real-Time Computing. INP ENSEEIHT/IRIT, p. 25-28 4 p.

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

  3. Type-driven verification of non-functional properties

    Brown, C. M., Barwell, A. D., Marquer, Y., Minh, C. & Zendra, O., 7 Oct 2019, Proceedings of the 21st International Symposium on Principles and Practice of Programming Languages 2019 (PPDP '19). New York: ACM, p. 1-15 15 p. 6

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

  4. Refactoring for introducing and tuning parallelism for heterogeneous multicore machines in Erlang

    Janjic, V., Brown, C., Barwell, A. & Hammond, K., 24 Jun 2019, In : Concurrency and Computation : Practice and Experience. Early View, p. 1-25 25 p., e5420.

    Research output: Contribution to journalArticle

  5. Extending the ‘Open-Closed Principle’ to automated algorithm configuration

    Swan, J., Adriænsen, S., Barwell, A. D., Hammond, K. & White, D., 4 Mar 2019, In : Evolutionary Computation. 27, 1, p. 173-193 21 p.

    Research output: Contribution to journalArticle

ID: 257273951

Top