Article

Data parallel Haskell: a status report

Authors:

Manuel M. T. Chakravarty,

Roman Leshchinskiy,

Simon Peyton Jones,

Gabriele Keller,

Simon MarlowAuthors Info & Claims

DAMP '07: Proceedings of the 2007 workshop on Declarative aspects of multicore programming

Pages 10 - 18

https://doi.org/10.1145/1248648.1248652

Published: 16 January 2007 Publication History

Abstract

We describe the design and current status of our effort to implement the programming model of nested data parallelism into the Glasgow Haskell Compiler. We extended the original programming model and its implementation, both of which were first popularised by the NESL language, in terms of expressiveness as well as efficiency. Our current aim is to provide a convenient programming environment for SMP parallelism, and especially multicore architectures. Preliminary benchmarks show that we are, at least for some programs, able to achieve good absolute performance and excellent speedups.

References

[1]

Guy E. Blelloch. Programming parallel algorithms. Communications of the ACM, 39(3):85--97, 1996.

Digital Library

[2]

Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, and Marco Zagha. Implementation of a portable nested data-parallel language. Journal of Parallel and Distributed Computing, 21(1):4--14, April 1994.

Digital Library

[3]

Manuel Chakravarty, Gabriele Keller, and Simon Peyton Jones. Associated type synonyms. In ACM SIGPLAN International Conference on Functional Programming (ICFP '05), Tallin, Estonia, 2005.

Digital Library

[4]

Manuel Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. Associated types with class. In ACM Symposium on Principles of Programming Languages (POPL'05). ACM Press, 2005.

Digital Library

[5]

Manuel M. T. Chakravarty and Gabriele Keller. More types for nested data parallel programming. In Philip Wadler, editor, Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP'00), pages 94--105. ACM Press, 2000.

Digital Library

[6]

Manuel M. T. Chakravarty and Gabriele Keller. Functional array fusion. In Xavier Leroy, editor, Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP'01), pages 205--216. ACM Press, 2001.

Digital Library

[7]

Duncan Coutts, Don Stewart, and Roman Leshchinskiy. Rewriting Haskell strings. In Practical Aspects of Declarative Languages 8th International Symposium, PADL 2007, LNCS. Springer-Verlag, 2007.

Digital Library

[8]

Matthew Fluet, Mike Rainey, John Reppy, Adam Shaw, and Yingqi Xiao. Manticore: A heterogeneous parallel language. In Proceedings of the Workshop on Declarative Aspects of Multicore Programming (DAMP 2007). ACM Press, 2007.

Digital Library

[9]

A Gill, J Launchbury, and SL Peyton Jones. A short cut to deforestation. In ACM Conference on Functional Programming and Computer Architecture (FPCA'93), pages 223--232, Cophenhagen, 1993. ACM Press. ISBN 0-89791-595-X.

Digital Library

[10]

Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable memory transactions. In ACM Symposium on Principles and Practice of Parallel Programming (PPoPP '05), June 2005.

Digital Library

[11]

Gabriele Keller and Manuel M. T. Chakravarty. On the distributed implementation of aggregate data structures by program transformation. In José Rolim et al., editors, Parallel and Distributed Processing, Fourth International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS'99), number 1586 in LNCS, pages 108--122, Berlin, Germany, 1999. Springer-Verlag.

Digital Library

[12]

Ken Kennedy and Kathryn S. McKinley. Maximizing loop parallelism and improving data locality via loop fusion and distribution. In 1993 Workshop on Languages and Compilers for Parallel Computing, number 768, pages 301--320. Springer Verlag, 1993.

Digital Library

[13]

J Launchbury and SL Peyton Jones. State in Haskell. Lisp and Symbolic Computation, 8(4):293--342, December 1995.

Digital Library

[14]

Roman Leshchinskiy, Manuel M. T. Chakravarty, and Gabriele Keller. Higher order flattening. In Third International Workshop on Practical Aspects of High-level Parallel Programming (PAPP 2006), number 3992 in LNCS. Springer-Verlag, 2006.

Digital Library

[15]

E Christopher Lewis, Calvin Lin, and Lawrence Snyder. The implementation and evaluation of fusion and contraction in array languages. In Proc ACM Conference on Programming Language Design and Implementation, pages 50--59, 1998.

Digital Library

[16]

Naraig Manjikian. Combining loop fusion with prefetching on shared-memory multiprocessors. In Proceedings of the 1997 International Conference on Parallel Processing (ICPP '97). IEEE Computer Society Press, 1997.

Digital Library

[17]

Daniel Palmer, Jan Prins, and Stephan Westfold. Work-efficient nested data-parallelism. In Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Processing (Frontiers 95). IEEE Press, 1995.

Digital Library

[18]

Simon Peyton Jones, Tony Hoare, and Andrew Tolmach. Playing by the rules: rewriting as a practical optimisation technique. In Proceedings of the ACM SIGPLAN 2001 Haskell Workshop, 2001.

[19]

SL Peyton Jones. Compilation by transformation: a report from the trenches. In European Symposium on Programming, volume 1058 of LNCS, pages 18--44. Springer Verlag, 1996.

Digital Library

[20]

SL Peyton Jones, AJ Gordon, and SO Finne. Concurrent Haskell. In 23rd ACM Symposium on Principles of Programming Languages (POPL'96), pages 295--308, St Petersburg Beach, Florida, January 1996. ACM Press.

Digital Library

[21]

SL Peyton Jones and J Launchbury. Unboxed values as first class citizens. In RJM Hughes, editor, ACM Conference on Functional Programming and Computer Architecture (FPCA'91), volume 523 of Lecture Notes in Computer Science, pages 636--666, Boston, 1991. Springer.

Digital Library

[22]

SL Peyton Jones and S Marlow. Secrets of the Glasgow Haskell Compiler inliner. Journal of Functional Programming, 12:393--434, 2002. First published at Workshop on Implementing Declarative Languages, Paris, Sept 1999.

Digital Library

[23]

Gerald Roth and Ken Kennedy. Loop fusion in High Performance Fortran. In Conference Proceedings of the 1998 International Conference on Supercomputing, pages 125--132. ACM Press, 1998.

Digital Library

[24]

SB Scholz. Single Assignment C -- efficient support for high-level array operations in a functional setting. Journal of Functional Programming, 13:1005--1059, 2003.

Digital Library

[25]

Byoungro So, Anwar Ghuloum, and Youfeng Wu. Optimizing data parallel operations on many-core platforms. In First Workshop on Software Tools for Multi-Core Systems (STMCS), 2006. http://www.isi.edu/~kintali/stmcs06/prog.html.

[26]

Martin Sulzmann, Manuel M. T. Chakravarty, Simon Peyton Jones, and Kevin Donnelly. System F with type equality coercions. In Proc ACM SIGPLAN Workshop on Types in Language Design and Implementation, Nice, France, January 2007. ACM.

Digital Library

[27]

Josef Svenningsson. Shortcut fusion for accumulating parameters and zip-like functions. In Proc ACM International Conference on Functional Programming, pages 124--132, Pittsburgh, 2002.

Digital Library

[28]

PW Trinder, K Hammond, H-W Loidl, and SL Peyton Jones. Algorithm + strategy = parallelism. Journal of Functional Programming, 8:23--60, January 1998.

Digital Library

[29]

Philip Wadler. Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science, 73:231--248, 1990.

Digital Library

[30]

M. Wolf and M. Lam. An algorithmic approach to compound loop transformations. In T. Gross A. Nicolau, D. Gelernter and D. Padua, editors, Advances in Languages and Compilers for Parallel Computing, pages 243--259. The MIT Press, 1991.

Cited By

Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Kovach SKolichala PGu TKjolstad F(2023)Indexed Streams: A Formal Intermediate Representation for Fused Contraction ProgramsProceedings of the ACM on Programming Languages10.1145/35912687:PLDI(1169-1193)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591268
Muller SSinger KKeeney DNeth AAgrawal KLee IAcar U(2023)Responsive Parallelism with SynchronizationProceedings of the ACM on Programming Languages10.1145/35912497:PLDI(712-735)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591249
Show More Cited By

Data parallel Haskell: a status report
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
2. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Eden --- parallel functional programming with haskell
CEFP'11: Proceedings of the 4th Summer School conference on Central European Functional Programming School

Eden is a parallel functional programming language which extends Haskell with constructs for the definition and instantiation of parallel processes. Processes evaluate function applications remotely in parallel. The programmer has control over process ...
Deterministic Parallel Programming with Haskell

Haskell is a modern, functional programming language with an interesting story to tell about parallelism: rather than using concurrent threads and locks, Haskell offers a variety of libraries that enable concise, high-level parallel programs with ...
Data-Parallel Programming on MIMD Computers

The implementation of two compilers for the data-parallel programming language Dataparallel C is described. One compiler generates code for Intel and nCUBE hypercube multicomputers; the other generates code for Sequent multiprocessors. A suite of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAMP '07: Proceedings of the 2007 workshop on Declarative aspects of multicore programming

January 2007

49 pages

ISBN:9781595936905

DOI:10.1145/1248648

General Chair:
Neal Glew
Intel Corporation
,
Program Chair:
Guy Blelloch
Carnegie Mellon University

Copyright © 2007 ACM.

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
Intel: Intel

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL07

Sponsor:

SIGPLAN
Intel

POPL07: The 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 16, 2007

Nice, France

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

179
Total Citations
View Citations
738
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Kovach SKolichala PGu TKjolstad F(2023)Indexed Streams: A Formal Intermediate Representation for Fused Contraction ProgramsProceedings of the ACM on Programming Languages10.1145/35912687:PLDI(1169-1193)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591268
Muller SSinger KKeeney DNeth AAgrawal KLee IAcar U(2023)Responsive Parallelism with SynchronizationProceedings of the ACM on Programming Languages10.1145/35912497:PLDI(712-735)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591249
Lisper BKällberg LHenriksen TSinkarovs A(2023)HERO-ML: A Very High-Level Array Language for Executable Modelling of Data Parallel AlgorithmsProceedings of the 9th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming10.1145/3589246.3595370(13-21)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3589246.3595370
Wilkins MWeil GArnold LHardavellas NDinda P(2023)Evaluating Functional Memory-Managed Parallel Languages for HPC using the NAS Parallel Benchmarks2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW59300.2023.00072(413-422)Online publication date: May-2023
https://doi.org/10.1109/IPDPSW59300.2023.00072
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Westrick SRainey MAnderson DBlelloch GLee JAgrawal KSpear M(2022)Parallel block-delayed sequencesProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508434(61-75)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508434
Arora JWestrick SAcar U(2021)Provably space-efficient parallel functional programmingProceedings of the ACM on Programming Languages10.1145/34342995:POPL(1-33)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434299
Muller SSinger KGoldstein NAcar UAgrawal KLee IDonaldson ATorlak E(2020)Responsive parallelism with futures and stateProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386013(577-591)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386013
Durst DFeldman MHuff DAkeley DDaly RBernstein GPatrignani MFatahalian KHanrahan PDonaldson ATorlak E(2020)Type-directed scheduling of streaming acceleratorsProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385983(408-422)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385983
Show More Cited By

View Options

Get Access

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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents