SHF: Small: Accelerating Graph Traversal on GPUs

从社会网络分析、生物网络分析和模拟到网络安全，图算法对于广泛的大数据应用至关重要。分析这些图表具有重要的实际用途，例如，为电子商务提供有针对性的建议，以及识别社交网络中的相关人员和可疑行为。基于图的方法在很大程度上依赖于许多遍历方法，例如，广度优先搜索是许多图算法最重要的组成部分之一。该项目通过在单个图形处理单元(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.