research-article

Seq no more: better strategies for parallel Haskell

Authors:

Hans-Wolfgang Loidl,

Mustafa K. Aswad,

Phil TrinderAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 11

Pages 91 - 102

https://doi.org/10.1145/2088456.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

Pasarella EVidal MZoltan CRoyo Sales J(2024)A computational framework based on the dynamic pipeline approachJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100966139(100966)Online publication date: Jun-2024
https://doi.org/10.1016/j.jlamp.2024.100966
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
Calderón Trilla JPoulding SRunciman C(2015)Weaving Parallel ThreadsSearch-Based Software Engineering10.1007/978-3-319-22183-0_5(62-76)Online publication date: 28-Jul-2015
https://doi.org/10.1007/978-3-319-22183-0_5
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: Proceedings of the third ACM Haskell symposium on Haskell

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 SIGPLAN Notices

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2010

Published in SIGPLAN Volume 45, Issue 11

Check for updates

Author Tags

Qualifiers

Research-article

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

Pasarella EVidal MZoltan CRoyo Sales J(2024)A computational framework based on the dynamic pipeline approachJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100966139(100966)Online publication date: Jun-2024
https://doi.org/10.1016/j.jlamp.2024.100966
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
Calderón Trilla JPoulding SRunciman C(2015)Weaving Parallel ThreadsSearch-Based Software Engineering10.1007/978-3-319-22183-0_5(62-76)Online publication date: 28-Jul-2015
https://doi.org/10.1007/978-3-319-22183-0_5
Duke DCarr H(2014)Computational Topology via Functional Programming: A Baseline AnalysisTopological Methods in Data Analysis and Visualization III10.1007/978-3-319-04099-8_5(73-87)Online publication date: 19-Mar-2014
https://doi.org/10.1007/978-3-319-04099-8_5
González CFraguela B(2013)A framework for argument-based task synchronization with automatic detection of dependenciesParallel Computing10.1016/j.parco.2013.04.01239:9(475-489)Online publication date: Sep-2013
https://doi.org/10.1016/j.parco.2013.04.012
Lobachev O(2012)Parallel computation skeletons with premature termination propertyProceedings of the 11th international conference on Functional and Logic Programming10.1007/978-3-642-29822-6_17(197-212)Online publication date: 23-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29822-6_17
Maier PTrinder P(2011)Implementing a high-level distributed-memory parallel haskell in haskellProceedings of the 23rd international conference on Implementation and Application of Functional Languages10.1007/978-3-642-34407-7_3(35-50)Online publication date: 3-Oct-2011
https://dl.acm.org/doi/10.1007/978-3-642-34407-7_3
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

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 Issue’s Table of Contents