Streaming Task Parallelism
Albert Cohen · 2015
Stream computing is often associated with regular, data-intensive applications, and more specifically with the family of cyclo-static data-flow models. The term also refers to bulk-synchronous data parallelism on SIMD architectures. Both interpretations are valid but incomplete: streams underline the formal definition of Kahn process networks, a foundation for deterministic concurrent languages and systems with a solid heritage. Streaming task parallelism is a semantical framework for parallel languages and a model for task-parallel execution with first-class dependences. Parallel languages with dynamic, nested task creation and first-class streams expose more parallelism and enable application-specific throttle control. These expressiveness and resource management capabilities address a key limitation of previous data-flow programming models. To support the class of streaming task parallel languages, we propose a new lock-free algorithm for stalling and waking-up tasks in a shared memory, user-space scheduler according to changes in the state of streaming queues. The algorithm generalizes both work-stealing with concurrent ring buffers, and proven correct against the C11 memory model. We show through experiments that it can serve as a common runtime for efficient parallel runtime systems. We also report on scalability-oriented extensions of a streaming task parallel runtime, with multiple optimizations leveraging the explicit data flow conveyed by the programming model. We will report on recent experiments on large scale NUMA systems with up to 24 nodes.