Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2020

Abstract

The recently emerging applications such as software-defined networks and autonomous vehicles require efficient and exact solutions for constrained shortest paths (CSP), which finds the shortest path in a graph while satisfying some user-defined constraints. Compared with the common shortest path problems without constraints, CSP queries have a significantly larger number of subproblems. The most widely used labeling algorithm becomes prohibitively slow and impractical. Other existing approaches tend to find approximate solutions and build costly indices on graphs for fast query processing, which are not suitable for emerging applications with the requirement of exact solutions. A natural question is whether and how we can efficiently find the exact solution for CSP.In this paper, we propose Vine, a framework that parallelizes the labeling algorithm to efficiently find the exact CSP solution using GPUs. The major challenge addressed in Vine is how to deal with a large number of subproblems that are mostly unpromising but require a significant amount of memory and computational resources. Our solution is twofold. First, we develop a two-level pruning approach to eliminate the subproblems by making good use of the GPU's hierarchical memory. Second, we propose an adaptive parallelism control model based on the observations that the degree of parallelism (DOP) is the key to performance optimization with the given amount of computational resources. Extensive experiments show that Vine achieves 18x speedup on average over the widely adopted CPU-based solution running on 40 CPU threads. Vine also has over 5x speedup compared with a GPU approach that statically controls the DOP. Compared to the state-of-the-art approximate solution with preprocessed indices, Vine provides exact results with competitive or even better performance.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

Proceedings of the VLDB Endowment: 46th VLDB 2020, Tokyo, Japan, August 31 - September 4

Volume

14

First Page

547

Last Page

559

Identifier

10.14778/3436905.3436914

Publisher

VLBD Endownment

City or Country

Stanford, CA

Embargo Period

7-5-2021

Copyright Owner and License

Authors

Comments

The source code, data, and/or other artifacts have been made available at https://github.com/xtra-computing/vine.

Additional URL

https://doi.org/10.14778/3436905.3436914

Download
Download Research Data

Share

COinS