Seq no more: Better Strategies for Parallel Haskell

Simon Marlow, Patrick Maier, Hans Wolfgang Loidl, Mustafa K. Aswad, Phil Trinder

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

30 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationHaskell'10 - Proceedings of the 2010 ACM SIGPLAN Haskell Symposium, Co-located with ICFP'10
PublisherAssociation for Computing Machinery
Pages91-102
Number of pages12
ISBN (Print)9781450302524
DOIs
Publication statusPublished - Sep 2010
Event2010 ACM SIGPLAN Haskell Symposium - Baltimore, MD, United States
Duration: 30 Sep 201030 Sep 2010

Conference

Conference2010 ACM SIGPLAN Haskell Symposium
Abbreviated titleHaskell'10
CountryUnited States
CityBaltimore, MD
Period30/09/1030/09/10

Keywords

  • parallel functional programming
  • strategies

Fingerprint Dive into the research topics of 'Seq no more: Better Strategies for Parallel Haskell'. Together they form a unique fingerprint.

  • Cite this

    Marlow, S., Maier, P., Loidl, H. W., Aswad, M. K., & Trinder, P. (2010). Seq no more: Better Strategies for Parallel Haskell. In Haskell'10 - Proceedings of the 2010 ACM SIGPLAN Haskell Symposium, Co-located with ICFP'10 (pp. 91-102). Association for Computing Machinery. https://doi.org/10.1145/1863523.1863535