STCLang: State Thread Composition as a Foundation for Monadic Dataflow Parallelism

Sebastian Ertel, Justus Adam, Norman A. Rink, Andrés Goens, Jeronimo Castrillon

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

Abstract

Dataflow execution models are used to build highly scalable parallel systems. A programming model that targets parallel dataflow execution must answer the following question: How can parallelism between two dependent nodes in a dataflow graph be exploited? This is difficult when the dataflow language or programming model is implemented by a monad, as is common in the functional community, since expressing dependence between nodes by a monadic bind suggests sequential execution. Even in monadic constructs that explicitly separate state from computation, problems arise due to the need to reason about opaquely defined state. Specifically, when abstractions of the chosen programming model do not enable adequate reasoning about state, it is difficult to detect parallelism between composed stateful computations. In this paper, we propose a programming model that enables the composition of stateful computations and still exposes opportunities for parallelization. We also introduce smap, a higher-order function that can exploit parallelism in stateful computations. We present an implementation of our programming model and smap in Haskell and show that basic concepts from functional reactive programming can be built on top of our programming model with little effort. We compare these implementations to a state-of-the-art approach using monad-par and LVars to expose parallelism explicitly and reach the same level of performance, showing that our programming model successfully extracts parallelism that is present in an algorithm. Further evaluation shows that smap is expressive enough to implement parallel reductions and our programming model resolves short-comings of the stream-based programming model for current state-of-the-art big data processing systems.
Original languageEnglish
Title of host publicationHaskell '19
Subtitle of host publicationProceedings of the 12th ACM SIGPLAN International Symposium on Haskell
EditorsRichard A. Eisenberg
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery, Inc
Pages146–161
Number of pages16
ISBN (Print)9781450368131
DOIs
Publication statusPublished - 8 Aug 2019
Event12th ACM SIGPLAN International Symposium on Haskell - Berlin, Germany
Duration: 22 Aug 201923 Aug 2019
https://icfp19.sigplan.org/home/haskellsymp-2019

Publication series

NameHaskell 2019
PublisherAssociation for Computing Machinery

Conference

Conference12th ACM SIGPLAN International Symposium on Haskell
Abbreviated titleHaskell 2019
Country/TerritoryGermany
CityBerlin
Period22/08/1923/08/19
Internet address

Keywords / Materials (for Non-textual outputs)

  • partitioned state
  • functional languages
  • parallel programming

Fingerprint

Dive into the research topics of 'STCLang: State Thread Composition as a Foundation for Monadic Dataflow Parallelism'. Together they form a unique fingerprint.

Cite this