research-article

Seq no more: better strategies for parallel Haskell

Authors:

Hans-Wolfgang Loidl,

Mustafa K. Aswad,

Phil TrinderAuthors Info & Claims

Haskell '10: Proceedings of the third ACM Haskell symposium on Haskell

Pages 91 - 102

https://doi.org/10.1145/1863523.1863535

Published: 30 September 2010 Publication History

Abstract

We present a complete redesign of evaluation strategies, a key abstraction for specifying pure, deterministic parallelism in Haskell. Our new formulation preserves the compositionality and modularity benefits of the original, while providing significant new benefits. First, we introduce an evaluation-order monad to provide clearer, more generic, and more efficient specification of parallel evaluation. Secondly, the new formulation resolves a subtle space management issue with the original strategies, allowing parallelism (sparks) to be preserved while reclaiming heap associated with superfluous parallelism. Related to this, the new formulation provides far better support for speculative parallelism as the garbage collector now prunes unneeded speculation. Finally, the new formulation provides improved compositionality: we can directly express parallelism embedded within lazy data structures, producing more compositional strategies, and our basic strategies are parametric in the coordination combinator, facilitating a richer set of parallelism combinators.

We give measurements over a range of benchmarks demonstrating that the runtime overheads of the new formulation relative to the original are low, and the new strategies even yield slightly better speedups on average than the original strategies

Supplementary Material

JPG File (haskell-1420-marlow.jpg)

Download
12.77 KB

MOV File (haskell-1420-marlow.mov)

Download
113.45 MB

References

[1]

}}M. K. Aswad, P. W. Trinder, A. D. Al Zain, G. J. Michaelson, and J. Berthold. Low pain vs no pain multi-core Haskells. In TFP '09 - Draft Proc. of Symp. on Trends in Functional Programming, pages 112--130, Komarno, Slovakia, June 2009.

[2]

}}C. Baker-Finch, D. J. King, and P. Trinder. An operational semantics for parallel lazy evaluation. In ICFP '00 - Intl. Conf. on Functional Programming, pages 162--173, Montreal, Canada, Sept. 2000. ACM Press.

Digital Library

[3]

}}G. E. Blelloch. Programming parallel algorithms. Commun. ACM, 39 (3): 85--97, 1996.

Digital Library

[4]

}}M. M. T. Chakravarty, R. Leshchinskiy, S. Peyton Jones, G. Keller, and S. Marlow. Data parallel Haskell: a status report. In DAMP '07 - Workshop on Declarative Aspects of Multicore Programming, pages 10--18, Nice, France, Jan. 2007. ACM Press.

Digital Library

[5]

}}M. I. Cole. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press & Pitman, 1989.

Digital Library

[6]

}}C. Grelck and S.-B. Scholz. SAC - from high-level programming with arrays to efficient parallel execution. Parallel Processing Letters, 13 (3): 401--412, 2003.

[7]

}}K. Hammond and G. Michaelson, editors. Research Directions in Parallel Functional Programming. Springer, 1999.

Digital Library

[8]

}}T. Harris and S. Singh. Feedback directed implicit parallelism. In ICFP '07 - Intl. Conf. on Functional Programming, pages 251--264, Freiburg, Germany, Oct. 2007. ACM Press.

Digital Library

[9]

}}T. Harris, S. Marlow, and S. Peyton Jones. Haskell on a shared-memory multiprocessor. In Haskell '05 - Workshop on Haskell, pages 49--61, Tallinn, Estonia, Sept. 2005. ACM Press.

Digital Library

[10]

}}D. Jones Jr., S. Marlow, and S. Singh. Parallel performance tuning for Haskell. In Haskell '09 - Symposium on Haskell, pages 81--92, Edinburgh, Scotland, Sept. 2009. ACM Press.

Digital Library

[11]

}}H.-W. Loidl, P. W. Trinder, K. Hammond, S. B. Junaidu, R. G. Morgan, and S. L. Peyton Jones. Engineering parallel symbolic programs in GpH. Concurrency - Practice and Experience, 11 (12): 701--752, 1999.

[12]

}}H.-W. Loidl, P. W. Trinder, and C. Butz. Tuning task granularity and data locality of data parallel GpH programs. Parallel Processing Letters, 11 (4): 471--486, 2001.

[13]

}}R. Loogen, Y. Ortega-Mallén, and R. Peña-Marí. Parallel functional programming in Eden. J. Funct. Program., 15 (3): 431--475, 2005.

Digital Library

[14]

}}S. Marlow, S. Peyton Jones, and S. Singh. Runtime support for multicore Haskell. In ICFP '09 - Intl. Conf. on Functional Programming, pages 65--78, Edinburgh, Scotland, Sept. 2009. ACM Press.

Digital Library

[15]

}}C. McBride and R. Paterson. Applicative programming with effects. J. Funct. Program., 18 (1): 1--13, 2008.

Digital Library

[16]

}}E. Mohr, D. A. Kranz, and R. H. Halstead Jr. Lazy task creation: A technique for increasing the granularity of parallel programs. IEEE Trans. Parallel Distrib. Syst., 2 (3): 264--280, 1991.

Digital Library

[17]

}}R. S. Nikhil and Arvind. Implicit Parallel Programming in pH. Morgan Kaufmann Publishers, 2001.

Digital Library

[18]

}}P. Prabhu, G. Ramalingam, and K. Vaswani. Safe programmable speculative parallelism. In PLDI '10 - Conf. on Programming Language Design and Implementation, pages 50--61, Toronto, Ontario, Canada, June 2010. ACM Press.

Digital Library

[19]

}}N. Scaife, S. Horiguchi, G. Michaelson, and P. Bristow. A parallel SML compiler based on algorithmic skeletons. J. Funct. Program., 15 (4): 615--650, 2005.

Digital Library

[20]

}}P. W. Trinder, K. Hammond, H.-W. Loidl, and S. L. Peyton Jones. Algorithms + strategy = parallelism. J. Funct. Program., 8 (1): 23--60, 1998.

Digital Library

[21]

}}P. W. Trinder, H.-W. Loidl, and R. F. Pointon. Parallel and distributed Haskells. J. Funct. Program., 12 (4&5): 469--510, 2002. Special Issue on Haskell.

Digital Library

Cited By

MORIHATA A(2021)Lambda calculus with algebraic simplification for reduction parallelisation: Extended studyJournal of Functional Programming10.1017/S095679682100005831Online publication date: 5-Apr-2021
https://doi.org/10.1017/S0956796821000058
Navarro Leija OShiptoski KScott RWang BRenner NNewton RDevietti JLarus JCeze LStrauss K(2020)Reproducible ContainersProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378519(167-182)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378519
Schiller L(2020)Placement Strategies: Structured Skeleton Composition with Location-Aware Remote DataTrends in Functional Programming10.1007/978-3-030-57761-2_11(229-248)Online publication date: 18-Aug-2020
https://doi.org/10.1007/978-3-030-57761-2_11
Show More Cited By

Index Terms

Seq no more: better strategies for parallel Haskell
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages
        Functional languages

Recommendations

Seq no more: better strategies for parallel Haskell
HASKELL '10

We present a complete redesign of evaluation strategies, a key abstraction for specifying pure, deterministic parallelism in Haskell. Our new formulation preserves the compositionality and modularity benefits of the original, while providing significant ...
Coordinating functional processes with Haskell_#
SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

This paper presents Haskell_#, a parallel functional language based on coordination. Haskell_# supports lazy stream communication and facilities, at coordination level, to the specification of data parallel programs. Haskell_# supports a clean and complete,...
Seeing the futures: profiling shared-memory parallel racket
FHPC '12: Proceedings of the 1st ACM SIGPLAN workshop on Functional high-performance computing

This paper presents the latest chapter in our adventures coping with a large, sequentially-tuned, legacy runtime system in today's parallel world. Specifically, this paper introduces our new graphical visualizer that helps programmers understand how to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '10: Proceedings of the third ACM Haskell symposium on Haskell

September 2010

166 pages

ISBN:9781450302524

DOI:10.1145/1863523

General Chair:
Jeremy Gibbons
University of Oxford, UK

ACM SIGPLAN Notices Volume 45, Issue 11
HASKELL '10
November 2010
156 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2088456
Issue’s Table of Contents

Copyright © 2010 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '10

Sponsor:

SIGPLAN

ICFP '10: ACM SIGPLAN International Conference on Functional Programming

September 30, 2010

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
436
Total Downloads

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

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

MORIHATA A(2021)Lambda calculus with algebraic simplification for reduction parallelisation: Extended studyJournal of Functional Programming10.1017/S095679682100005831Online publication date: 5-Apr-2021
https://doi.org/10.1017/S0956796821000058
Navarro Leija OShiptoski KScott RWang BRenner NNewton RDevietti JLarus JCeze LStrauss K(2020)Reproducible ContainersProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378519(167-182)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378519
Schiller L(2020)Placement Strategies: Structured Skeleton Composition with Location-Aware Remote DataTrends in Functional Programming10.1007/978-3-030-57761-2_11(229-248)Online publication date: 18-Aug-2020
https://doi.org/10.1007/978-3-030-57761-2_11
Morihata A(2019)Lambda calculus with algebraic simplification for reduction parallelization by equational reasoningProceedings of the ACM on Programming Languages10.1145/33416443:ICFP(1-25)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341644
Belikov ELoidl HMichaelson G(2019)Colocation of Potential Parallelism in a Distributed Adaptive Run-Time System for Parallel HaskellZivilgesellschaft und Wohlfahrtsstaat im Wandel10.1007/978-3-030-18506-0_1(1-19)Online publication date: 24-Apr-2019
https://doi.org/10.1007/978-3-030-18506-0_1
Barwell ABrown CHammond K(2018)Finding parallel functional pearlsFuture Generation Computer Systems10.1016/j.future.2017.07.02479:P2(669-686)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.future.2017.07.024
Blöcker CHoffmann U(2018)PardisThe Journal of Supercomputing10.1007/s11227-018-2289-674:4(1473-1484)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11227-018-2289-6
Ishii H(2018)A Purely Functional Computer Algebra System Embedded in HaskellDevelopments in Language Theory10.1007/978-3-319-99639-4_20(288-303)Online publication date: 23-Aug-2018
https://doi.org/10.1007/978-3-319-99639-4_20
Scott RNavarro Leija ODevietti JNewton R(2017)Monadic composition for deterministic, parallel batch processingProceedings of the ACM on Programming Languages10.1145/31338971:OOPSLA(1-26)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133897
Barwell AHammond KTrinder POancea C(2017)In search of a map: using program slicing to discover potential parallelism in recursive functionsProceedings of the 6th ACM SIGPLAN International Workshop on Functional High-Performance Computing10.1145/3122948.3122951(30-41)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122948.3122951
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