Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale
Topology-aware Parallel Data Processing: Models, Algorithms and Systems at Scale
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Spyros Blanas;Paraschos Koutris;Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
Spyros Blanas;Paraschos Koutris;Anastasios Sidiropoulos
海量数据集的分析需要大量的处理器。之前的研究在很大程度上假设跟踪集群的实际数据分布和底层网络结构（我们统称为拓扑）成本很高，而且几乎没有实际好处。因此，理论模型，算法和系统通常假设一个统一的拓扑结构，但这种假设很少在实践中成立。这就需要对如何为大规模的基本数据处理任务建模、设计和部署拓扑感知算法进行端到端的研究。为了实现这一目标，我们首先开发了一个理论上的并行模型，可以共同捕获计算和通信的成本。使用这个模型，我们探索算法的理论保证三个基本任务：聚合，连接和排序。最后，我们考虑了在规模上实现拓扑感知算法的实际方面，并表明它们有可能比拓扑无关的算法快几个数量级。
The analysis of massive datasets requires a large number of processors. Prior research has largely assumed that tracking the actual data distribution and the underlying network structure of a cluster, which we collectively refer to as the topology, comes with a high cost and has little practical ben-efit. As a result, theoretical models, algorithms and systems often assume a uniform topology; however this assumption rarely holds in practice. This necessitates an end-to-end investigation of how one can model, design and deploy topology-aware algorithms for fundamental data processing tasks at large scale. To achieve this goal, we first develop a theoretical parallel model that can jointly capture the cost of computation and communication. Using this model, we explore algorithms with theoretical guarantees for three basic tasks: aggregation, join, and sorting. Finally, we consider the practical aspects of implementing topology-aware algorithms at scale, and show that they have the potential to be orders of magnitude faster than their topology-oblivious counterparts.