Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
复制标题
DOI：
10.1145/3210377.3210414
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Laxman Dhulipala;G. Blelloch;Julian Shun
中科院分区：
文献类型：
--
作者：
Laxman Dhulipala;G. Blelloch;Julian Shun
由于需要快速分析当今可用的大图，因此最近对并行图处理引起了重大兴趣。许多图形代码已设计用于分布式内存或外部内存。但是，如今，即使是最大的公共现实世界图（超过35亿个顶点和1280亿个边缘的超链接Web图）也可以符合单个商品多核心服务器的内存。然而，文献报告中的大多数实验工作都会导致较小的图，而超链接图的图形则使用了分布式或外部存储器。因此，很自然地询问我们是否可以在内存中有效地在此图上有效地解决了一系列图形问题。本文表明，理论上有效的并行图算法可以使用带有Terabyte的RAM的单个计算机来扩展到最大的公共可用图，并在几分钟内对其进行处理。我们为13个重要的图形问题提供理论上有效的并行算法的实现。我们还介绍了我们在实施中使用的优化和技术，这对于使我们能够快速处理这些大图至关重要。我们表明，实现的运行时间优于最大现实图表上现有的最新实现。对于我们考虑的许多问题，这是他们第一次在此规模上求解它们。我们提供一个包含我们实施的公共基准套件。
There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed memory or external memory. However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server. Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones for the Hyperlink graph use distributed or external memory. Therefore, it is natural to ask whether we can efficiently solve a broad class of graph problems on this graph in memory. This paper shows that theoretically-efficient parallel graph algorithms can scale to the largest publicly-available graphs using a single machine with a terabyte of RAM, processing them in minutes. We give implementations of theoretically-efficient parallel algorithms for 13 important graph problems. We also present the optimizations and techniques that we used in our implementations, which were crucial in enabling us to process these large graphs quickly. We show that the running times of our implementations outperform existing state-of-the-art implementations on the largest real-world graphs. For many of the problems that we consider, this is the first time they have been solved on graphs at this scale. We provide a publicly-available benchmark suite containing our implementations.