Stclang: State thread composition as a foundation for monadic dataflow parallelism

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

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.

Details

OriginalspracheEnglisch
TitelHaskell 2019 - Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell, co-located with ICFP 2019
Redakteure/-innenRichard A. Eisenberg
Herausgeber (Verlag)Association for Computing Machinery, Inc
Seiten146-161
Seitenumfang16
ISBN (elektronisch)9781450368131
PublikationsstatusVeröffentlicht - 8 Aug. 2019
Peer-Review-StatusJa

Konferenz

Titel12th ACM SIGPLAN International Symposium on Haskell, Haskell 2019, co-located with ICFP 2019
Dauer22 - 23 August 2019
StadtBerlin
LandDeutschland

Externe IDs

ORCID /0000-0002-5007-445X/work/141545538

Schlagworte

Forschungsprofillinien der TU Dresden

Schlagwörter

  • Functional languages, Par titioned state, Parallel programming