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 journalArticle

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
StatePublished - Feb 2018

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. Towards semi-automatic data-type translation for parallelism in Erlang

    Barwell, A. D., Brown, C. M., Castro, D. & Hammond, K. 23 Sep 2016 Proceedings of the 15th International Workshop on Erlang. New York: ACM, p. 60-61

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

  3. 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

  4. 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

  5. Timing properties and correctness for structured parallel programs on x86-64 multicores

    Hammond, K., Brown, C. M. & Sarkar, S. 2016 Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers. van Eekelen, M. & Dal Lago, U. (eds.). Springer, p. 101-125 26 p. (Lecture Notes in Computer Science; vol. 9964)

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

Related by journal

  1. 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 journalArticle

  2. 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 journalArticle

ID: 250572396