435 citations · 1.3k across the 28 of their papers we have counts for
18 papers · 1 filter
BOBA: A Parallel Lightweight Graph Reordering Algorithm with Heavyweight Implications
Matthew Drescher, Muhammad A. Awad, Serban D. Porumbescu +1
We describe a simple parallel-friendly lightweight graph reordering algorithm for COO graphs (edge lists). Our ``Batched Order By Attachment'' (BOBA) algorithm is linear in the num…
Essentials of Parallel Graph Analytics
Muhammad Osama, Serban D. Porumbescu, John D. Owens
We identify the graph data structure, frontiers, operators, an iterative loop structure, and convergence conditions as essential components of graph analytics systems based on the…
Atos: A Task-Parallel GPU Dynamic Scheduling Framework for Dynamic Irregular Computations
Yuxin Chen, Benjamin Brock, Serban Porumbescu +3
We present Atos, a task-parallel GPU dynamic scheduling framework that is especially suited to dynamic irregular applications. Compared to the dominant Bulk Synchronous Parallel (B…
Fast Gunrock Subgraph Matching (GSM) on GPUs
Leyuan Wang, John D. Owens
In this paper, we propose a GPU-efficient subgraph isomorphism algorithm using the Gunrock graph analytic framework, GSM (Gunrock Subgraph Matching), to compute graph matching on G…
RDMA vs. RPC for Implementing Distributed Data Structures
Benjamin Brock, Yuxin Chen, Jiakun Yan +3
Distributed data structures are key to implementing scalable applications for scientific simulations and data analysis. In this paper we look at two implementation styles for distr…
Fast BFS-Based Triangle Counting on GPUs
Leyuan Wang, John D. Owens
In this paper, we propose a novel method to compute triangle counting on GPUs. Unlike previous formulations of graph matching, our approach is BFS-based by traversing the graph in…
GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU
Carl Yang, Aydin Buluc, John D. Owens
High-performance implementations of graph algorithms are challenging to implement on new parallel hardware such as GPUs because of three challenges: (1) the difficulty of coming up…
A Comparative Study on Exact Triangle Counting Algorithms on the GPU
Leyuan Wang, Yangzihao Wang, Carl Yang +1
We implement exact triangle counting in graphs on the GPU using three different methodologies: subgraph matching to a triangle pattern; programmable graph analytics, with a set-int…
Scalable Breadth-First Search on a GPU Cluster
Yuechao Pan, Roger Pearce, John D. Owens
On a GPU cluster, the ratio of high computing power to communication bandwidth makes scaling breadth-first search (BFS) on a scale-free graph extremely challenging. By separating h…
Implementing Push-Pull Efficiently in GraphBLAS
Carl Yang, Aydin Buluc, John D. Owens
We factor Beamer's push-pull, also known as direction-optimized breadth-first-search (DOBFS) into 3 separable optimizations, and analyze them for generalizability, asymptotic speed…
Design Principles for Sparse Matrix Multiplication on the GPU
Carl Yang, Aydin Buluc, John D. Owens
We implement two novel algorithms for sparse-matrix dense-matrix multiplication (SpMM) on the GPU. Our algorithms expect the sparse input in the popular compressed-sparse-row (CSR)…
A Dynamic Hash Table for the GPU
Saman Ashkiani, Martin Farach-Colton, John D. Owens
We design and implement a fully concurrent dynamic hash table for GPUs with comparable performance to the state of the art static hash tables. We propose a warp-cooperative work sh…
GPU LSM: A Dynamic Dictionary Data Structure for the GPU
Saman Ashkiani, Shengren Li, Martin Farach-Colton +2
We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA…
Gunrock: GPU Graph Analytics
Yangzihao Wang, Yuechao Pan, Andrew Davidson +8
For large-scale graph analytics on the GPU, the irregularity of data access and control flow, and the complexity of programming GPUs, have presented two significant challenges to d…
GPU Multisplit: an extended study of a parallel algorithm
Saman Ashkiani, Andrew Davidson, Ulrich Meyer +1
Multisplit is a broadly useful parallel primitive that permutes its input data into contiguous buckets or bins, where the function that categorizes an element into a bucket is prov…
Multi-GPU Graph Analytics
Yuechao Pan, Yangzihao Wang, Yuduo Wu +2
We present a single-node, multi-GPU programmable graph processing library that allows programmers to easily extend single-GPU graph algorithms to achieve scalable performance on la…
Gunrock: A High-Performance Graph Processing Library on the GPU
Yangzihao Wang, Andrew Davidson, Yuechao Pan +3
For large-scale graph analytics on the GPU, the irregularity of data access and control flow, and the complexity of programming GPUs have been two significant challenges for develo…
A GPU Implementation for Two-Dimensional Shallow Water Modeling
Kerry A. Seitz, Alex Kennedy, Owen Ransom +2
In this paper, we present a GPU implementation of a two-dimensional shallow water model. Water simulations are useful for modeling floods, river/reservoir behavior, and dam break s…