research-article

Regular, shape-polymorphic, parallel arrays in Haskell

Authors:

Gabriele Keller,

Manuel M.T. Chakravarty,

Roman Leshchinskiy,

Simon Peyton Jones,

Ben LippmeierAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 9

Pages 261 - 272

https://doi.org/10.1145/1932681.1863582

Published: 27 September 2010 Publication History

Get Access

Abstract

We present a novel approach to regular, multi-dimensional arrays in Haskell. The main highlights of our approach are that it (1) is purely functional, (2) supports reuse through shape polymorphism, (3) avoids unnecessary intermediate structures rather than relying on subsequent loop fusion, and (4) supports transparent parallelisation.

We show how to embed two forms of shape polymorphism into Haskell's type system using type classes and type families. In particular, we discuss the generalisation of regular array transformations to arrays of higher rank, and introduce a type-safe specification of array slices.

We discuss the runtime performance of our approach for three standard array algorithms. We achieve absolute performance comparable to handwritten C code. At the same time, our implementation scales well up to 8 processor cores.

Supplementary Material

JPG File (icfp-weds-1055-lippmeier.jpg)

Download
11.30 KB

MOV File (icfp-weds-1055-lippmeier.mov)

Download
115.49 MB

References

[1]

}}The Boost Multidimensional Array Library, April 20URL http://www.boost.org/doc/libs/1_42_0/libs/multi_array/doc/user.html.

Google Scholar

[2]

}}C. Burke. J and APL. Iverson Software Inc., 1996.

Google Scholar

[3]

}}M. M. T.Chakravarty, G. Keller,and S. Peyton Jones. Associated type synonyms. In ICFP '05: Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming, pages 241--253, New York, NY, USA, 2005. ACM Press. ISBN 1-59593-064-7.

Digital Library

Google Scholar

[4]

}}M. M. T. Chakravarty, G. Keller, S. Peyton Jones, and S. Marlow. Associated types with class. In POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1--13. ACM Press, 2005. ISBN 1-58113-830-X.

Digital Library

Google Scholar

[5]

}}M. M. T. Chakravarty, R. Leshchinskiy, S. Peyton Jones, G. Keller, and S. Marlow. Data Parallel Haskell: a status report. In DAMP 2007: Workshop on Declarative Aspects of Multicore Programming. ACM Press, 2007.

Digital Library

Google Scholar

[6]

}}D. Coutts, R. Leshchinskiy, and D. Stewart. Stream fusion: From lists to streams to nothing at all. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP 2007). ACM Press, 2007.

Digital Library

Google Scholar

[7]

}}D. Coutts, D. Stewart, and R. Leshchinskiy. Rewriting Haskell strings. In Practical Aspects of Declarative Languages 8th International Symposium, PADL 2007, pages 50--64. Springer-Verlag, Jan. 2007.

Digital Library

Google Scholar

[8]

}}M. Frigo and S. G. Johnson. The design and implementation of FFTW3. Proceedings of the IEEE, 93(2):216--231, 2005. Special issue on Program Generation, Optimization, and Platform Adaptation.

Crossref

Google Scholar

[9]

}}A. Gilat. MATLAB: An Introduction with Applications 2nd Edition. John Wiley & Sons, 2004. ISBN 978-0-471-69420-5.

Google Scholar

[10]

}}J. H. v.Groningen. The implementation and efficiency of arrays in Clean 1.1. In W. Kluge, editor, Proceedings of Implementation of Functional Languages, 8th International Workshop, IFL '96, Selected Papers, number 1268 in LNCS, pages 105--124. Springer-Verlag, 1997.

Digital Library

Google Scholar

[11]

}}J. Launchbury and S. Peyton Jones. Lazy functional state threads. In Proceedings of Programming Language Design and Implementation (PLDI 1994), pages 24--35, New York, NY, USA, 1994. ACM.

Digital Library

Google Scholar

[12]

}}S. Lee, M. M. T. Chakravarty, V. Grover, and G. Keller. GPU kernels as data-parallel array computations in haskell. In EPAHM 2009: Workshop on Exploiting Parallelism using GPUs and other Hardware-Assisted Methods, 2009.

Google Scholar

[13]

}}X. Leroy, D. Doligez, J. Garrigue, D. Rémy, and J. Vouillon. The Objective Caml system, release 3.11, documentation and user's manual. Technical report, INRIA, 2008.

Google Scholar

[14]

}}J. Mathews and K. Fink. Numerical Methods using MATLAB, 3rd edition. Prentice Hall, 1999.

Digital Library

Google Scholar

[15]

}}S. Peyton Jones. Call-pattern specialisation for Haskell programs. In Proceedings of the International Conference on Functional Programming (ICFP 2007), pages 327--337, 1997.

Digital Library

Google Scholar

[16]

}}S. Peyton Jones, R. Leshchinskiy, G. Keller, and M. M. T. Chakravarty. Harnessing the multicores: Nested data parallelism in Haskell. In R. Hariharan, M. Mukund, and V. Vinay, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), Dagstuhl, Germany, 2008. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. URL http://drops.dagstuhl.de/opus/volltexte/2008/1769.

Google Scholar

[17]

}}F. A. Rabhi and S. Gorlatch, editors. Patterns and Skeletons for Parallel and Distributed Computing. Springer-Verlag, 2003.

Digital Library

Google Scholar

[18]

}}S.-B. Scholz. Single assignment C - efficient support for high-level array operations in a functional setting. Journal of Functional Programming, 13(6):1005--1059, 2003.

Digital Library

Google Scholar

[19]

}}T. Schrijvers, S. Peyton-Jones, M. M. T. Chakravarty, and M. Sulzmann. Type checking with open type functions. In Proceedings of ICFP 2008 : The 13th ACM SIGPLAN International Conference on Functional Programming, pages 51--62. ACM Press, 2008.

Digital Library

Google Scholar

[20]

}}W. Swierstra and T. Altenkirch. Dependent types for distributed arrays. In Trends in Functional Programming, volume 9, 2008.

Google Scholar

[21]

}}The International Standards Organisation. Programming Language APL. ISO standard 8485, 1989.

Google Scholar

[22]

}}The OpenMP Architecture Review Board. OpenMP Application Program Interface, 2008. URL http://www.openmp.org/specs.

Google Scholar

[23]

}}T. L. Veldhuizen. Arrays in Blitz++. In Proceedings of the 2nd International Scientific Computing in Object Oriented Parallel Environments (ISCOPE'98). Springer-Verlag, 1998. ISBN 978-3-540-65387-5.

Digital Library

Google Scholar

[24]

}}H. Xi. Dependent ML: an approach to practical programming with dependent types. Journal of Functional Programming, 17(2):215--286, 2007.

Digital Library

Google Scholar

Cited By

View all

van Balen DKeller Gde Wolff IMcDonell TRainey MScholz S(2024)Fusing Gathers with Integer Linear ProgrammingProceedings of the 1st ACM SIGPLAN International Workshop on Functional Programming for Productivity and Performance10.1145/3677997.3678227(10-23)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1145/3677997.3678227
Shaikhha AHuot MSmith JOlteanu D(2022)Functional collection programming with semi-ring dictionariesProceedings of the ACM on Programming Languages10.1145/35273336:OOPSLA1(1-33)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527333
Reguly IMudalige G(2020)Productivity, Performance, and Portability for Computational Fluid Dynamics ApplicationsComputers & Fluids10.1016/j.compfluid.2020.104425(104425)Online publication date: Jan-2020
https://doi.org/10.1016/j.compfluid.2020.104425
Show More Cited By

Index Terms

Regular, shape-polymorphic, parallel arrays in Haskell
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
    2. General programming languages
      1. Language features
        Abstract data types
        Concurrent programming structures
        Polymorphism

Recommendations

Accelerating Haskell array codes with multicore GPUs
DAMP '11: Proceedings of the sixth workshop on Declarative aspects of multicore programming

Current GPUs are massively parallel multicore processors optimised for workloads with a large degree of SIMD parallelism. Good performance requires highly idiomatic programs, whose development is work intensive and requires expert knowledge.

To raise ...
Regular, shape-polymorphic, parallel arrays in Haskell
ICFP '10: Proceedings of the 15th ACM SIGPLAN international conference on Functional programming

We present a novel approach to regular, multi-dimensional arrays in Haskell. The main highlights of our approach are that it (1) is purely functional, (2) supports reuse through shape polymorphism, (3) avoids unnecessary intermediate structures rather ...
Efficient parallel stencil convolution in Haskell
Haskell '11: Proceedings of the 4th ACM symposium on Haskell

Stencil convolution is a fundamental building block of many scientific and image processing algorithms. We present a declarative approach to writing such convolutions in Haskell that is both efficient at runtime and implicitly parallel. To achieve this ...

Reviews

Reviewer: Rafael Corchuelo

Algorithms that work on arrays are very common in science and engineering, and range from finding connected components in a graph to complex atmospheric simulations. Supporters of purely functional languages claim that these algorithms are often easier to understand and more conceptually elegant than their imperative counterparts. Detractors, however, tend to claim that the functional versions are often too inefficient for practical purposes. Keller et al. report on a technique, and an accompanying library, that supports multidimensional functional arrays and parallel optimization, and also provides a high degree of reuse by supporting shape parallelism and polymorphism. Their technique seems very efficient in practice since it can perform similarly to native C code in some cases. Following the introductory section 1, the paper is organized into two logical parts. First, sections 2 and 3 present the authors' approach to representing arrays and implementing array algorithms. Then, the remaining sections (4 to 9) discuss their proposal to support constrained shape polymorphism, their functional application programming interface (API), parallel optimization, and an empirical evaluation using three well-known benchmarks. The paper is well written. The authors clearly address what the problem is, why it is actually a problem, what their solution is, and why it advances the state of the art. I definitely recommend it to researchers who are interested in parallel array algorithms. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 45, Issue 9

ICFP '10

September 2010

382 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1932681

Issue’s Table of Contents

ICFP '10: Proceedings of the 15th ACM SIGPLAN international conference on Functional programming
September 2010
398 pages
ISBN:9781605587943
DOI:10.1145/1863543
General Chair:
Paul Hudak
Yale University, USA
,
Program Chair:
Stephanie Weirich
University of Pennsylvania, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 September 2010

Published in SIGPLAN Volume 45, Issue 9

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

157
Total Citations
View Citations
452
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

van Balen DKeller Gde Wolff IMcDonell TRainey MScholz S(2024)Fusing Gathers with Integer Linear ProgrammingProceedings of the 1st ACM SIGPLAN International Workshop on Functional Programming for Productivity and Performance10.1145/3677997.3678227(10-23)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1145/3677997.3678227
Shaikhha AHuot MSmith JOlteanu D(2022)Functional collection programming with semi-ring dictionariesProceedings of the ACM on Programming Languages10.1145/35273336:OOPSLA1(1-33)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527333
Reguly IMudalige G(2020)Productivity, Performance, and Portability for Computational Fluid Dynamics ApplicationsComputers & Fluids10.1016/j.compfluid.2020.104425(104425)Online publication date: Jan-2020
https://doi.org/10.1016/j.compfluid.2020.104425
Boehm MReinwald BHutchison DSen PEvfimievski APansare N(2018)On optimizing operator fusion plans for large-scale machine learning in systemMLProceedings of the VLDB Endowment10.14778/3229863.322986511:12(1755-1768)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3229865
Rasch AGorlatch S(2018)Multi-dimensional Homomorphisms and Their Implementation in OpenCLInternational Journal of Parallel Programming10.1007/s10766-017-0508-z46:1(101-119)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10766-017-0508-z
Ungureanu GSander I(2017)A layered formal framework for modeling of cyber-physical systemsProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130780(1719-1724)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130780
Ungureanu GSander I(2017)A layered formal framework for modeling of cyber-physical systemsDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927270(1715-1720)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927270
Gibbons J(2017)APLicative Programming with Naperian FunctorsProgramming Languages and Systems10.1007/978-3-662-54434-1_21(556-583)Online publication date: 19-Mar-2017
https://doi.org/10.1007/978-3-662-54434-1_21
Muranushi THotta HMakino JNishizawa STomita HNitadori KIwasawa MHosono NMaruyama YInoue HYashiro HNakamura YWest J(2016)Simulations of below-ground dynamics of fungiProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014908(1-11)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014908
Gibbons JChapman JSwierstra W(2016)APLicative programming with Naperian functors (extended abstract)Proceedings of the 1st International Workshop on Type-Driven Development10.1145/2976022.2976023(13-14)Online publication date: 18-Sep-2016
https://dl.acm.org/doi/10.1145/2976022.2976023
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

EPUB

View this article in ePub.

ePub

Abstract

Supplementary Material

References

Cited By

Index Terms

Recommendations

Accelerating Haskell array codes with multicore GPUs