The Single Source Shortest Path (SSSP) problem is a classic graph theory problem that arises frequently in various practical scenarios;hence, many parallelalgorithms have been developed to solve it. However, these al...
详细信息
The Single Source Shortest Path (SSSP) problem is a classic graph theory problem that arises frequently in various practical scenarios;hence, many parallelalgorithms have been developed to solve it. However, these algorithms operate on static graphs, whereas many real-world problems are best modeled as dynamic networks, where the structure of the network changes with time. This gap between the dynamic graph modeling and the assumed static graph model in the conventional SSSP algorithms motivates this work. We present a novel parallelalgorithmic framework for updating the SSSP in large-scale dynamic networks and implement it on the shared-memory and GPU platforms. The basic idea is to identify the portion of the network affected by the changes and update the information in a rooted tree data structure that stores the edges of the network that are most relevant to the analysis. Extensive experimental evaluations on real-world and synthetic networks demonstrate that our proposed parallel updating algorithm is scalable and, in most cases, requires significantly less execution time than the state-of-the-art recomputing-from-scratch algorithms.
The graph partitioning problem is one of the most fundamental combinatorial problems with a wide variety of applications. In this paper, we propose an efficient approach for implementing spectral graph partitioning th...
详细信息
ISBN:
(纸本)9781665423694
The graph partitioning problem is one of the most fundamental combinatorial problems with a wide variety of applications. In this paper, we propose an efficient approach for implementing spectral graph partitioning that has a solid theoretical foundation but is practically less efficient than standard multilevel partitioners. The proposed method is based on the approximation of the eigenvectors of a graph-Laplacian matrix derived using the basis vectors by geodesic distance-based approach, instead of a standard linear algebraic approach. This geodesic distance-based approach is the key to making our method competitive in comparison to the multilevel partitioners. The primary building blocks of our method are the breadth-first search and the sparse matrix-vector product, which are the main kernels intensively studied in the high-performance computing field. Based on a performance evaluation in the shared-memoryparallel setting, we demonstrate that our method is comparable to standard partitioners in terms of both quality and speed. We also show that our method has the potential to facilitate reproducibility-aware parallel partitioning.
We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important p...
详细信息
ISBN:
(纸本)9781538639146
We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memoryparallel SpMSpV algorithm is work efficient in the sense that its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs.
暂无评论