SHF: Small: Accelerating Graph Traversal on GPUs

George Washington University, Washington DC

Investigators

Abstract

Graph algorithms are crucial to a wide range of big data applications from social network analysis, biological network analysis and simulation, to cybersecurity. Analyzing such graphs has important practical usages, e.g., providing targeted recommendations for e-commerce, as well as identifying person of interest and suspicious behaviors in social networks. Graph-based approaches rely heavily on a number of traversal methods, e.g., breadth-first search serves as one of the most significant building blocks for many graph algorithms. This project advances the state-of-the-art in graph traversal by achieving exceptional performance on both a single graphics processing unit (GPU) and large GPU-based supercomputers. New techniques developed in this project enable many graph applications to run efficiently in data centers, bringing enormous benefits to a number of scientific domains. New educational opportunities for undergraduate and graduate students are also enabled by this project. Although GPUs provide both massive parallelism and high memory bandwidth ideal for running graph algorithms, unleashing their full power to achieve high-performance, highly scalable graph traversal remains extremely challenging. The main obstacles are highly unbalanced workload and irregular data access, both inherent to data-driven graph algorithms. To address this challenge, this project develops a set of novel techniques that not only remove several performance bottlenecks, but also optimize data access, communication, and task management for graph traversal on GPUs.