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

SHF：小型：用于加速迭代图分析的 GPU 专用图转换

• 批准号: 1813173
• 负责人: Zhijia Zhao
• 金额: $ 50万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813173&HistoricalAwards=false
• 关键词: SHF; Small; GPU; dedicated; Graph

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.

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

项目成果

MultiLyra: Scalable Distributed Evaluation of Batches of Iterative Graph Queries

• DOI: 10.1109/bigdata47090.2019.9006359
• 发表时间: 2019-12
• 期刊: 2019 IEEE International Conference on Big Data (Big Data)
• 作者: Abbas Mazloumi;Xiaolin Jiang;Rajiv Gupta

SimGQ+: Simultaneously evaluating iterative point-to-all and point-to-point graph queries

SimGQ：同时评估迭代点对所有和点对点图查询

• DOI: 10.1016/j.jpdc.2022.01.007
• 发表时间: 2022
• 期刊: Journal of parallel and distributed computing
• 影响因子: 3.8
• 作者: Xu, Chengshuo;Mazloumi, Abbas;Jiang, Xiaolin;Gupta, Rajiv
• 通讯作者: Gupta, Rajiv

VRGQ: Evaluating a Stream of Iterative Graph Queries via Value Reuse

VRGQ：通过值重用评估迭代图查询流

• DOI: 10.1145/3469379.3469382
• 发表时间: 2021
• 期刊: ACM SIGOPS Operating Systems Review
• 作者: Jiang, Xiaolin;Xu, Chengshuo;Gupta, Rajiv
• 通讯作者: Gupta, Rajiv

GraphPulse: An Event-Driven Hardware Accelerator for Asynchronous Graph Processing

• DOI: 10.1109/micro50266.2020.00078
• 发表时间: 2020-10
• 期刊: 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)
• 作者: Shafiur Rahman;N. Abu-Ghazaleh;Rajiv Gupta

DSGEN: concolic testing GPU implementations of concurrent dynamic data structures

DSGEN：并发动态数据结构的 concolic 测试 GPU 实现

• DOI: 10.1145/3447818.3460962
• 发表时间: 2021
• 期刊: ICS '21: Proceedings of the ACM International Conference on Supercomputing
• 作者: Sun, Xiaofan;Gupta, Rajiv
• 通讯作者: Gupta, Rajiv