435 citations · 1.3k across the 28 of their papers we have counts for
32 papers
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…
Stream-K: Work-centric Parallel Decomposition for Dense Matrix-Matrix Multiplication on the GPU
Muhammad Osama, Duane Merrill, Cris Cecka +2
We introduce Stream-K, a work-centric parallelization of matrix multiplication (GEMM) and related computations in dense linear algebra. Whereas contemporary decompositions are prim…
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…
Building a Performance Model for Deep Learning Recommendation Model Training on GPUs
Zhongyi Lin, Louis Feng, Ehsan K. Ardestani +5
We devise a performance model for GPU training of Deep Learning Recommendation Models (DLRM), whose GPU utilization is low compared to other well-optimized CV and NLP models. We sh…
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…
Supporting Unified Shader Specialization by Co-opting C++ Features
Kerry A. Seitz, Theresa Foley, Serban D. Porumbescu +1
Modern unified programming models (such as CUDA and SYCL) that combine host (CPU) code and GPU code into the same programming language, same file, and same lexical scope lack adequ…
Better GPU Hash Tables
Muhammad A. Awad, Saman Ashkiani, Serban D. Porumbescu +2
We revisit the problem of building static hash tables on the GPU and design and build three bucketed hash tables that use different probing schemes. Our implementations are lock-fr…
Energy-based Out-of-distribution Detection
Weitang Liu, Xiaoyun Wang, John D. Owens +1
Determining whether inputs are out-of-distribution (OOD) is an essential building block for safely deploying machine learning models in the open world. However, previous methods re…
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…
Unsupervised Object Segmentation with Explicit Localization Module
Weitang Liu, Lifeng Wei, James Sharpnack +1
In this paper, we propose a novel architecture that iteratively discovers and segments out the objects of a scene based on the image reconstruction quality. Different from other ap…
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…
VoroCrust: Voronoi Meshing Without Clipping
Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida +4
Polyhedral meshes are increasingly becoming an attractive option with particular advantages over traditional meshes for certain applications. What has been missing is a robust poly…
Object Localization with a Weakly Supervised CapsNet
Weitang Liu, Emad Barsoum, John D. Owens
Inspired by CapsNet's routing-by-agreement mechanism with its ability to learn object properties, we explore if those properties in turn can determine new properties of the objects…
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…
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida +4
We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled so…
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…