SHF: Small: Accelerating Graph Traversal on GPUs

图算法对于从社交网络分析、生物网络分析和模拟到网络安全的各种大数据应用至关重要。分析这样的图具有重要的实际用途，例如，为电子商务提供有针对性的建议，以及识别社交网络中的感兴趣的人和可疑行为。基于图的方法严重依赖于许多遍历方法，例如，宽度优先搜索用作许多图算法的最重要的构造块之一。该项目通过在单个图形处理单元（GPU）和基于GPU的大型超级计算机上实现卓越的性能，推进了图形遍历的最新技术。该项目开发的新技术使许多图形应用程序能够在数据中心高效运行，为许多科学领域带来巨大好处。虽然GPU提供了大规模并行性和高内存带宽，非常适合运行图算法，但要充分发挥其能力来实现高性能、高可扩展的图遍历仍然极具挑战性。主要障碍是高度不平衡的工作负载和不规则的数据访问，这两个都是数据驱动图算法所固有的。为了应对这一挑战，该项目开发了一套新技术，不仅消除了几个性能瓶颈，而且还优化了GPU上图遍历的数据访问、通信和任务管理。

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.