Skip to content

Research at St Andrews

Finding parallel functional pearls: automatic parallel recursion scheme detection in Haskell functions via anti-unification

Research output: Contribution to journalArticlepeer-review

Author(s)

Adam D. Barwell, Christopher Brown, Kevin Hammond

School/Research organisations

Abstract

This paper describes a new technique for identifying potentially parallelisable code structures in functional programs. Higher-order functions enable simple and easily understood abstractions that can be used to implement a variety of common recursion schemes, such as maps and folds over traversable data structures. Many of these recursion schemes have natural parallel implementations in the form of algorithmic skeletons. This paper presents a technique that detects instances of potentially parallelisable recursion schemes in Haskell 98 functions. Unusually, we exploit anti-unification to expose these recursion schemes from source-level definitions whose structures match a recursion scheme, but which are not necessarily written directly in terms of maps, folds, etc. This allows us to automatically introduce parallelism, without requiring the programmer to structure their code a priori in terms of specific higher-order functions. We have implemented our approach in the Haskell refactoring tool, HaRe, and demonstrated its use on a range of common benchmarking examples. Using our technique, we show that recursion schemes can be easily detected, that parallel implementations can be easily introduced, and that we can achieve real parallel speedups (up to 23 . 79 × the sequential performance on 28 physical cores, or 32 . 93 × the sequential performance with hyper-threading enabled).
Close

Details

Original languageEnglish
Pages (from-to)669-686
JournalFuture Generation Computer Systems
Volume79
Issue numberPart 2
Early online date27 Jul 2017
DOIs
Publication statusPublished - Feb 2018

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

View graph of relations

Related by author

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

    Brown, C. M., Janjic, V., Goli, M. & McCall, J., Aug 2020, In: International Journal of Parallel Programming. 48, 4, p. 583–602 20 p.

    Research output: Contribution to journalArticlepeer-review

  2. Refactoring GrPPI: generic refactoring for generic parallelism in C++

    Brown, C. M., Janjic, V., Barwell, A. D., Garcia, J. D. & MacKenzie, K., 10 Jul 2020, In: International Journal of Parallel Programming. First Online, 23 p.

    Research output: Contribution to journalArticlepeer-review

  3. Restoration of legacy parallelism in C and C++ applications

    Brown, C. M., Barwell, A. D. & Janjic, V., 1 Jul 2020, (Accepted/In press).

    Research output: Contribution to conferencePaperpeer-review

  4. 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., 14 May 2020, 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). IEEE Computer Society, 5 p. 9092377. (Proceedings - Euromicro Workshop on Parallel and Distributed Processing).

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

  5. A trustworthy framework for resource-aware embedded programming

    Barwell, A. D. & Brown, C. M., 11 Feb 2020, (Accepted/In press) Proceedings of International Symposium on Implementation and Application of Functional Languages (IFL'19). ACM

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

Related by journal

  1. A survey and taxonomy of resource optimisation for executing Bag-of-Task applications on public clouds

    Thai, L., Varghese, B. & Barker, A., May 2018, In: Future Generation Computer Systems. 82, p. 1-11

    Research output: Contribution to journalArticlepeer-review

  2. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y., Feb 2018, In: Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticlepeer-review

  3. High-Performance Computing in Chemistry; NWChem

    Guest, M. F., Apra, E., Bernholdt, D. E., Fruchtl, H. A., Harrison, R. J., Kendall, R. A., Kutteh, R. A., Long, X., Nicholas, J. B., Nichols, J. A., Taylor, H. L., Wong, A. T., Fann, G. I., Littlefield, R. J. & Nieplocha, J., Dec 1996, In: Future Generation Computer Systems. 12, 4, p. 273-289

    Research output: Contribution to journalArticlepeer-review

ID: 250572396

Top