Algorithms for a Topology-aware Massively Parallel Computation Model
Algorithms for a Topology-aware Massively Parallel Computation Model
复制标题
DOI：
10.1145/3452021.3458318
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Xiao Hu;Paraschos Koutris;Spyros Blanas
中科院分区：
文献类型：
--
作者：
Xiao Hu;Paraschos Koutris;Spyros Blanas
大规模并行数据处理中的大多数先前工作假设同质性，即，每个计算单元具有相同的计算能力，并且可以以相同的等待时间和带宽与每个其它单元通信。然而，这种统一拓扑的强假设在实际环境中很少成立，其中计算单元通过复杂网络连接。为了解决这个问题，Blanas等人最近提出了一种拓扑感知的大规模并行计算模型，该模型在建模成本中集成了网络结构和异构性。该网络被建模为有向图，其中每条边与成本函数相关联，该成本函数取决于两个端点之间传输的数据。计算在同步循环中进行，并且每个循环的成本被测量为网络中所有边缘上的最大成本。在这项工作中，我们采取的第一步，调查三个基本的数据处理任务，在这个拓扑感知的并行模型：集合相交，carnival产品，排序。我们专注于网络拓扑结构，树拓扑结构，并提出了两个下界以及（渐近）匹配的上界。而不是假设一个最坏情况下的分布在以前的结果，我们的算法的最优性是相对于网络节点之间的初始数据分布。除了我们的结果的理论最优性之外，我们的协议很简单，使用恒定的轮数，我们相信也可以在实际环境中实现。
Most of the prior work in massively parallel data processing assumes homogeneity, i.e., every computing unit has the same computational capability and can communicate with every other unit with the same latency and bandwidth. However, this strong assumption of a uniform topology rarely holds in practical settings, where computing units are connected through complex networks. To address this issue, Blanas et al. \citeblanas2020topology recently proposed a topology-aware massively parallel computation model that integrates the network structure and heterogeneity in the modeling cost. The network is modeled as a directed graph, where each edge is associated with a cost function that depends on the data transferred between the two endpoints. The computation proceeds in synchronous rounds and the cost of each round is measured as the maximum cost over all the edges in the network. In this work, we take the first step into investigating three fundamental data processing tasks in this topology-aware parallel model: set intersection, cartesian product, and sorting. We focus on network topologies that are tree topologies, and present both lower bounds as well as (asymptotically) matching upper bounds. Instead of assuming a worst-case distribution as in previous results, the optimality of our algorithms is with respect to the initial data distribution among the network nodes. Apart from the theoretical optimality of our results, our protocols are simple, use a constant number of rounds, and we believe can be implemented in practical settings as well.