SimGQ: Simultaneously Evaluating Iterative Graph Queries
| Autor: | Xiaolin Jiang, Rajiv Gupta, Chengshuo Xu, Abbas Mazloumi |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Theoretical computer science
Computational complexity theory Computer science Graph theory 02 engineering and technology Supercomputer Instruction set Task (computing) Parallel processing (DSP implementation) 020204 information systems Shortest path problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Enhanced Data Rates for GSM Evolution |
| Zdroj: | HiPC |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|