Argo: Architecture-aware graph partitioning
Argo: Architecture-aware graph partitioning
复制标题
Argo：架构感知图分区
DOI：
10.1109/bigdata.2016.7840614
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Lange, Jack
中科院分区：
文献类型：
--
作者：
Zheng, Angen;Labrinidis, Alexandros;Chrysanthis, Panos K.;Lange, Jack
各种大型图数据集的日益普及和普遍存在引起了人们对图划分的新兴趣。现有的图分区要么对大型图的扩展性很差，要么忽略底层硬件拓扑的影响。一些解决方案表明，不均匀的网络通信成本可能会对性能产生很大影响。然而，它们都没有考虑资源争用对存储器子系统的影响（例如，LLC和内存控制器）。他们都忽略了一个事实，即现代高速网络的带宽（例如，Infiniband）已经变得可以与内存子系统相媲美。在本文中，我们提供了一个深入的分析，理论和实验，分布式工作负载的竞争问题。我们发现，争用导致的速度减慢可能高达11倍。然后，我们设计了一个架构感知的图形分区，Argo，允许充分利用多核机器的所有核心，而不会受到竞争或通信异构性问题。我们的实验研究表明：（1）Argo的有效性，在三种经典工作负载上实现了高达12倍的加速：广度优先搜索，单源最短路径和PageRank;以及（2）Argo在20亿边真实世界图形上的图形大小和分区数量方面的可扩展性。
The increasing popularity and ubiquity of various large graph datasets has caused renewed interest for graph partitioning. Existing graph partitioners either scale poorly against large graphs or disregard the impact of the underlying hardware topology. A few solutions have shown that the nonuniform network communication costs may affect the performance greatly. However, none of them considers the impact of resource contention on the memory subsystems (e.g., LLC and Memory Controller) of modern multicore clusters. They all neglect the fact that the bandwidth of modern high-speed networks (e.g., Infiniband) has become comparable to that of the memory subsystems. In this paper, we provide an in-depth analysis, both theoretically and experimentally, on the contention issue for distributed workloads. We found that the slowdown caused by the contention can be as high as 11x. We then design an architecture-aware graph partitioner, Argo, to allow the full use of all cores of multicore machines without suffering from either the contention or the communication heterogeneity issue. Our experimental study showed (1) the effectiveness of Argo, achieving up to 12x speedups on three classic workloads: Breadth First Search, Single Source Shortest Path, and PageRank; and (2) the scalability of Argo in terms of both graph size and the number of partitions on two billion-edge real-world graphs.