SCnC: Efficient Unification of Streaming with Dynamic Task Parallelism

Stream processing is a special form of the dataflow execution model that offers extensive opportunities for optimization and auto-matic parallelization. To take full advantage of the paradigm, how-ever, typically requires programmers to learn a new language and re-implement their applications. This work shows that it is possible to exploit streaming as a safe and automatic optimization of a more general dataflow-based model—one in which computation kernels are written in standard, general-purpose languages and organized as a coordination graph. We propose Streaming Concurrent Collections (SCnC), a stream-ing system that can efficiently run a subset of programs supported by Concurrent Collections (CnC). CnC is a general purpose par-allel programming paradigm with a task-parallel look and feel but based on dataflow graph principles. Its expressivity extends to any arbitrary task graph. Integration of these models would allow appli-cation developers to benefit from the performance and tight mem-ory footprint of stream parallelism for eligible subgraphs of their application. In this paper we formally define the requirements (streaming ac-cess patterns) needed for using SCnC, and outline a static decision procedure for identifying and processing eligible SCnC subgraphs. We present initial results on an prototype implementation that show that transitioning from general CnC to SCnC leads to a throughput increase of up to 40 × for certain benchmarks, and also enable pro-grams with large data sizes to execute in available memory for cases where CnC execution may run out of memory. 1