Aquila: Adaptive Parallel Computation of Graph Connectivity Queries
Aquila: Adaptive Parallel Computation of Graph Connectivity Queries
复制标题
DOI：
10.1145/3369583.3392690
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Yuede Ji;Howie Huang
中科院分区：
文献类型：
--
作者：
Yuede Ji;Howie Huang
图连通性算法解决图中两个节点在特定条件下是否连通的问题，这对许多应用（如模式识别和网络安全）有益。不幸的是，现有的图计算框架仅支持少量连通性算法，且计算并行度较低。在本文中，我们设计了一种自适应并行计算框架Aqila，它涵盖了多种高度优化的不同图连通性算法。对于给定的图，如果可以通过部分计算来回答查询，Aqila首先会转换该查询。在计算过程中，Aqila能够将工作量大幅减少多达98%。此外，Aqila识别连通性算法中的不规则任务，并对不同任务应用不同的并行策略。结果，Aqila分别比Multistep、Galois、Ligra、GraphChi、X - Stream、DFS和Boost等现有系统性能平均高出13倍、53倍、264倍、364倍、1369倍、45倍和255倍。
Graph connectivity algorithms answer whether two nodes in a graph are connected under specific conditions, which are beneficial to a number of applications, such as pattern recognition and cybersecurity. Unfortunately, existing graph computing frameworks support only a small number of connectivity algorithms and achieve low computation parallelism. In this paper, we have designed an adaptive parallel computation framework, Aqila, that covers a wide range of different highly optimized graph connectivity algorithms. Given a graph, Aqila first transforms the query if it can be answered with partial computation. During the computation, Aqila is able to greatly reduce the workload by up to 98%. Furthermore, Aqila identifies the irregular tasks in the connectivity algorithms and applies different parallel strategies for different tasks. As a result, Aqila significantly outperforms existing systems such as Multistep, Galois, Ligra, GraphChi, X-Stream, DFS, and Boost, by average 13x, 53x, 264x, 364x, 1,369x, 45x, and 255x, respectively.