SHF: Small: GPU-dedicated Graph Transformations for Accelerating Iterative Graph Analytics

图分析通过挖掘大量高度关联的数据，如社交网络、航空网络、生物网络和互联网拓扑，在许多科学领域产生更深层次的知识。由于其计算和数据密集型的特性，具有大规模并行性的gpu在加速图形分析方面具有巨大的潜力。然而，由于GPU的常规计算设计与现实世界图形的高度不规则性之间的不匹配，现有的解决方案表现出GPU资源的低利用率。此外，由于gpu有限的设备内存，它经常无法处理相对较大的图形。本研究的目标是通过转换图形，使数据和工作负载更适合GPU计算，从而显着提高GPU资源利用率并提高图形分析的可扩展性。这项研究的结果包括可以很容易地部署在现有的大规模高性能系统上的软件产品，这些系统配备了gpu，用于执行现实世界的图形应用程序。更广泛地说，这项研究有助于加速生物信息学、社会科学和公共安全等科学领域的新发现。具体来说，本研究开发了一系列面向gpu的图形转换，这些转换共同解决了输入图形级别的不规则性、可伸缩性和负载不平衡的挑战。其中包括：(1)规律性图变换，将不规则的图结构转换为更规则的图结构，以解决GPU效率低的问题；(2)可扩展性的图形转换，将大图形转换为无循环和循环小图形的混合，每个小图形都适合GPU全局内存。通过最大限度地将计算从非循环图迁移到循环图，转换可以大大减少GPU内存和主机内存之间的数据移动；(3)针对多GPU系统的图变换，解决迭代图分析中活动节点变化导致的GPU负载不平衡问题。这是通过生成小而重叠的图并有选择地处理重叠的区域来实现的。最后，本研究通过根据输入图形和GPU平台的属性定制转换设计，将上述转换集成在一起，以最大限度地提高整体效益。评估包括来自KONNECT和SNAP存储库的大型图形数据集。图分析算法的实现被打包成易于使用的编程接口，并在这个项目的过程中发布。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Graph analytics yields deeper knowledge in many scientific domains by mining large volumes of highly connected data, such as social networks, airline networks, biological networks, and internet topology. Due to its compute and data-intensive nature, GPUs with massive parallelism hold great potential in accelerating graph analytics. However, existing solutions exhibit low utilization of GPU resources caused by the mismatch between GPU's design for regular computations and the highly irregular nature of real-world graphs. Moreover, GPUs often fail to handle relatively large graphs due to their limited on-device memory. The goal of this research is to dramatically improve the GPU resource utilization and boost the scalability of graph analytics by transforming the graphs in ways that make the data and workloads better fit in the GPU computing. The results of this research include software products that can be readily deployed on existing large-scale high-performance systems equipped with GPUs for executing real-world graph applications. More broadly, this research helps accelerate new discoveries in scientific fields like bioinformatics, social science, and public security. Specifically, this research develops a series of GPU-oriented graph transformations that together address the challenges of irregularity, scalability, and load imbalance at the input graph level. These include: (1) graph transformations for regularity which transform the irregular graph structures into more regular ones to address the low GPU efficiency; (2) graph transformations for scalability which transform a large graph into a mix of acyclic and cyclic small graphs, with each of them fitting into the GPU global memory. By maximally migrating computation from the acyclic graphs to the cyclic ones, the transformations can greatly reduce the data movement between GPU memory and host memory; and (3) graph transformations for multi-GPU systems which address the GPU load imbalance caused by the variation of active nodes in iterative graph analytics. This is achieved by generating small yet overlapped graphs and selectively processing the overlapped regions. Finally, this research integrates the above transformations to maximize the overall benefits by tailoring the design of the transformations to the properties of input graphs and GPU platforms. The evaluation includes large graph data sets from KONNECT and SNAP repositories. The implementations of graph analysis algorithms are packaged into easy-to-use programming interfaces and released over the course of this project.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.