TACC: Topology-Aware Coded Computing for Distributed Graph Processing
TACC: Topology-Aware Coded Computing for Distributed Graph Processing
复制标题
DOI：
10.1109/tsipn.2020.2998223
复制
发表时间：
2020-05
影响因子：
3.2
通讯作者：
Basak Guler;S. Avestimehr;Antonio Ortega
中科院分区：
文献类型：
--
作者：
Basak Guler;S. Avestimehr;Antonio Ortega
针对大规模分布式图形处理中的通信瓶颈问题，提出了一种编码分布式图形处理框架。特别地，我们提出了一种拓扑感知编码计算(TACC)算法，该算法具有两个新的显著特征：(I)拓扑感知的图分配策略；(Ii)在构造编码消息的同时结合图处理的中间计算的编码聚集方案。建议的设置导致了计算和通信之间的权衡，因为增加分布式各方的计算负载可以反过来减少通信负载。我们通过比较ErdöS-Rényi和Barabási-Albert型随机图上的通信负载以及用于PageRank计算的真实Google Web图来验证TACC算法的有效性。特别是，与最先进的编码策略相比，在Amazon EC2云计算平台上实施的编码策略可以使通信负载减少高达82美元，总执行时间减少高达46美元。
This article proposes a coded distributed graph processing framework to alleviate the communication bottleneck in large-scale distributed graph processing. In particular, we propose a topology-aware coded computing (TACC) algorithm that has two novel salient features: (i) a topology-aware graph allocation strategy, and (ii) a coded aggregation scheme that combines the intermediate computations for graph processing while constructing coded messages. The proposed setup results in a trade-off between computation and communication, in that increasing the computation load at the distributed parties can in turn reduce the communication load. We demonstrate the effectiveness of the TACC algorithm by comparing the communication load with existing setups on both Erdös-Rényi and Barabási-Albert type random graphs, as well as real-world Google web graph for PageRank computations. In particular, we show that the proposed coding strategy can lead to up to $82\%$ reduction in communication load and up to $46\%$ reduction in overall execution time, when compared to the state-of-the-art and implemented on the Amazon EC2 cloud compute platform.