SimGQ: Simultaneously Evaluating Iterative Graph Queries
SimGQ: Simultaneously Evaluating Iterative Graph Queries
复制标题
DOI：
10.1109/hipc50609.2020.00014
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Chengshuo Xu;Abbas Mazloumi;Xiaolin Jiang;Rajiv Gupta
中科院分区：
文献类型：
--
作者：
Chengshuo Xu;Abbas Mazloumi;Xiaolin Jiang;Rajiv Gupta
图形处理框架通常是为了优化单个图形查询的评估。我们开发SIMGQ，该系统优化了对一组源自不同源顶点的顶点查询的简单评估（例如，多个最短的路径查询源于不同的源顶点），并在传统框架上提供大量加速，以评估一个查询并响应一个查询。通过批处理和共享，通过一个人来评估一批查询，并通过划分的问题来实现绩效。这基本代表了批次评估不同查询的子分组，评估共享查询，然后使用其结果加速批次中所有查询的评估。在基线实现的最多45.67×，最多可查询512个查询，该查询使用ART LIGRA系统来一一评估查询。
Graph processing frameworks are typically designed to optimize the evaluation of a single graph query. However, in practice, we often need to respond to multiple graph queries, either from different users or from a single user performing a complex analytics task. Therefore in this paper we develop SimGQ, a system that optimizes simultaneous evaluation of a group of vertex queries that originate at different source vertices (e.g., multiple shortest path queries originating at different source vertices) and delivers substantial speedups over a conventional framework that evaluates and responds to queries one by one. The performance benefits are achieved via batching and sharing. Batching fully utilizes system resources to evaluate a batch of queries and amortizes runtime overheads incurred due to fetching vertices and edge lists, synchronizing threads, and maintaining computation frontiers. Sharing dynamically identifies shared queries that substantially represent subcomputations in the evaluation of different queries in a batch, evaluates the shared queries, and then uses their results to accelerate the evaluation of all queries in the batch. With four input power-law graphs and four graph algorithms SimGQ achieves speedups of up to 45.67 × with batch sizes of up to 512 queries over the baseline implementation that evaluates the queries one by one using the state of the art Ligra system. Moreover, both batching and sharing contribute substantially to the speedups.