Spinning Fast Iterative Data Flows
Spinning Fast Iterative Data Flows
复制标题
DOI：
10.14778/2350229.2350245
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
Stephan Ewen;K. Tzoumas;Moritz Kaufmann;V. Markl
中科院分区：
文献类型：
--
作者：
Stephan Ewen;K. Tzoumas;Moritz Kaufmann;V. Markl
并行数据流系统是大数据分析管道的核心部分。但是，许多分析和机器学习算法的迭代性质仍然是当前系统的挑战。尽管新型数据流框架支持某些类型的散装迭代算法，但这些系统无法利用许多算法中存在的计算依赖性，例如图形算法。结果，这些算法效率低下，并基于其他范式（例如消息传递或共享内存）导致了专门的系统。我们提出了一种与并行数据流相结合的增量迭代，一种工作集迭代形式的方法。在展示了如何将批量迭代集成到数据流系统及其优化器中之后，我们为增量迭代的编程模型提供了扩展。该扩展可以减轻数据流中缺乏可变状态的扩展，并允许利用许多迭代算法中固有的稀疏计算依赖性。对原型实现的评估表明，当被利用时，这些方面在算法运行时最多导致两个数量级加速。在我们的实验中，改进的数据流系统具有高度竞争性的专用系统，同时保持了透明和统一的数据流抽象。
Parallel dataflow systems are a central part of most analytic pipelines for big data. The iterative nature of many analysis and machine learning algorithms, however, is still a challenge for current systems. While certain types of bulk iterative algorithms are supported by novel dataflow frameworks, these systems cannot exploit computational dependencies present in many algorithms, such as graph algorithms. As a result, these algorithms are inefficiently executed and have led to specialized systems based on other paradigms, such as message passing or shared memory. We propose a method to integrate incremental iterations, a form of workset iterations, with parallel dataflows. After showing how to integrate bulk iterations into a dataflow system and its optimizer, we present an extension to the programming model for incremental iterations. The extension alleviates for the lack of mutable state in dataflows and allows for exploiting the sparse computational dependencies inherent in many iterative algorithms. The evaluation of a prototypical implementation shows that those aspects lead to up to two orders of magnitude speedup in algorithm runtime, when exploited. In our experiments, the improved dataflow system is highly competitive with specialized systems while maintaining a transparent and unified dataflow abstraction.