RII Track-4: NSF: Massively Parallel Graph Processing on Next-Generation Multi-GPU Supercomputers

RII Track-4：NSF：下一代多 GPU 超级计算机上的大规模并行图形处理

• 批准号: 2229394
• 负责人: Da Yan
• 金额: $ 27.56万
• 依托单位: University of Alabama at Birmingham
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-02-01 至 2024-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2229394&HistoricalAwards=false
• 关键词: RII; Track; NSF; Massively; Parallel

Graph processing is essential in real-world applications such as bioinformatics and social network analysis. Many fundamental graph operations are compute-intensive, for which the PI has successfully developed a series of CPU-scalable graph processing systems following a novel task-based parallel paradigm called T-thinker. However, it is non-trivial to extend this success to a GPU-rich environment due to a much larger gap between IO bandwidth and computing power of GPUs, and due to the unique programming requirements for GPU programs to be scalable. This project will develop a new task-based distributed GPU framework, T-thinkerGPU, and implement three applications on top, including subgraph matching, dense subgraph mining, and frequent subgraph pattern mining. T-thinkerGPU will be tested on the Aurora supercomputer at Argonne National Laboratory (ANL) as well as UAB’s Cheaha supercomputer, and the implementation will exploit modern GPU features including atomic operations, unified shared memory, and dynamic parallelism. This work will establish a solid foundation for long-term collaboration with ANL towards the development of GPU-scalable HPC solutions for various scientific applications. The project will also train a GPU-programming workforce (including a PhD student who will also visit ANL) that is in urgent need in Alabama, and all the proposed tools will be open source.This Research Infrastructure Improvement Track-4 EPSCoR Research Fellows (RII Track-4) proposal would provide a fellowship to an Assistant professor and training for a graduate student at the University of Alabama at Birmingham (UAB). GPU supercomputers are increasingly being deployed in place of CPU supercomputers in the hope to benefit from not only significant performance improvement but also energy efficiency. Built on the success of task-based parallel paradigm, T-thinker, for scaling graph processing in a multi-CPU environment, this project aims to investigate novel task-based techniques to scale fundamental compute-intensive graph operations in a multi-GPU environment, especially the exascale Aurora supercomputer at ANL that is based on Intel GPUs. Specifically, the project will first investigate efficient representation schemes that encode and compress the input graph and intermediate subgraph results compactly to reduce memory footprint and enable coalesced memory access and data reuse in shared memory, such as hashed neighborhood signature and lossless pattern-based contraction. Secondly, the project will design GPU-friendly task-based algorithms for fundamental graph operations including subgraph matching, dense subgraph mining, and frequent subgraph pattern mining, to unleash the massive parallelism enabled by a multi-GPU environment like the Aurora supercomputer. Novel techniques will be investigated such as kernel-as-a-task execution model, a truly hybrid BFS-DFS task scheduling strategy, and several other GPU optimization approaches, which will be combined into a unified programming framework, T-thinkerGPU, with extendibility in mind to facilitate the development of GPU-scalable task-based algorithms for other graph operations in the future. Finally, the developed GPU programs will be extensively evaluated on Aurora (with Intel GPUs) and UAB’s Cheaha supercomputer (with Nvidia GPUs), using public benchmarks and scientific applications at ANL and UAB, and the code will be released on GitHub.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.

图形处理在生物信息学和社交网络分析等现实世界应用中至关重要，许多基本图形操作都是计算密集型的，为此，PI 遵循一种新颖的基于任务的并行范例，成功开发了一系列 CPU 可扩展的图形处理系统。然而，由于 GPU 的 IO 带宽和计算能力之间存在更大的差距，并且由于 GPU 程序具有可扩展性的独特编程要求，因此将这一成功扩展到 GPU 丰富的环境中并非易事。 。这项目将开发一个新的基于任务的分布式GPU框架T-thinkerGPU，并在其上实现三个应用，包括子图匹配、密集子图挖掘和频繁子图模式挖掘，T-thinkerGPU将在阿贡国家实验室的Aurora超级计算机上进行测试。实验室 (ANL) 以及 UAB 的 Cheaha 超级计算机，其实现将利用现代 GPU 功能，包括原子操作、统一共享内存和动态并行性。这项工作将为双方的长期合作奠定坚实的基础。 ANL 致力于为各种科学应用开发 GPU 可扩展的 HPC 解决方案，该项目还将培训阿拉巴马州急需的 GPU 编程人员（包括一名也将访问 ANL 的博士生），并且所有提议的工具都将得到满足。这项研究基础设施改进 Track-4 EPSCoR 研究员 (RII Track-4) 提案将为越来越多的阿拉巴马大学伯明翰分校 (UAB) 的助理教授提供奖学金，并为研究生提供培训。正在部署到位该项目旨在研究基于任务的并行范例 T-thinker 的成功，用于在多 CPU 环境中扩展图形处理。为了在多 GPU 环境中扩展基本计算密集型图形操作的新颖的基于任务的技术，特别是 ANL 的基于英特尔 GPU 的百亿亿级 Aurora 超级计算机，该项目将首先研究对输入进行编码和压缩的高效表示方案。图和中间子图紧凑的结果，以减少内存占用，并在共享内存中实现合并内存访问和数据重用，例如哈希邻域签名和基于无损模式的收缩。 其次，该项目将为包括子图匹配在内的基本图操作设计 GPU 友好的基于任务的算法。 、密集子图挖掘和频繁子图模式挖掘，以释放由 Aurora 超级计算机等多 GPU 环境实现的大规模并行性。将研究诸如内核即任务执行模型（真正的混合）的新技术。 BFS-DFS任务调度策略以及其他几种GPU优化方法，将被组合成一个统一的编程框架T-thinkerGPU，并考虑到可扩展性，以方便开发用于其他图操作的GPU可扩展的基于任务的算法最后，开发的GPU程序将在Aurora（配备Intel GPU）和UAB的Cheaha超级计算机（配备Nvidia GPU）上进行评估，使用ANL和UAB的公共基准和科学应用，并主要发布代码。 GitHub。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Faster Depth-First Subgraph Matching on GPUs

GPU 上更快的深度优先子图匹配

• 发表时间: 2024-04
• 期刊: 40th IEEE International Conference on Data Engineering (ICDE
• 作者: Yuan, Lyuheng;Yan, Da;Han, Jiao;Ahmad, Akhlaque;Zhou, Yang;Jiang, Zhe
• 通讯作者: Jiang, Zhe

T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph

T-FSM：一种基于任务的大图大规模并行频繁子图模式挖掘系统

• DOI: 10.1145/3588928
• 发表时间: 2023-05-30
• 期刊: Proceedings of the ACM on Management of Data
• 作者: Lyuheng Yuan;Da Yan;Wenwen Qu;Saugat Adhikari;J. Khalil;Cheng Long;Xiaoling Wang
• 通讯作者: Xiaoling Wang

Systems for Scalable Graph Analytics and Machine Learning: Trends and Methods

可扩展图形分析和机器学习系统：趋势和方法

• 发表时间: 2024-04
• 期刊: The 33rd International Joint Conference on Artificial Intelligence (IJCAI-24
• 作者: Yan, Da;Yuan, Lyuheng;Ahmad, Akhlaque;Zheng, Chenguang;Chen, Hongzhi;Cheng, James
• 通讯作者: Cheng, James

Accelerating k-Core Decomposition by a GPU

通过 GPU 加速 k-Core 分解

• DOI: 10.1109/icde55515.2023.00142
• 发表时间: 2023-04-01
• 期刊: 2023 IEEE 39th International Conference on Data Engineering (ICDE)
• 作者: Akhlaque Ahmad;Lyuheng Yuan;Da Yan;Guimu Guo;Jieyang Chen;Chengcui Zhang
• 通讯作者: Chengcui Zhang

G2-AIMD: A Memory-Efficient Subgraph-Centric Framework for Efficient Subgraph Search on GPUs

G2-AIMD：一种以内存高效的子图为中心的框架，用于在 GPU 上进行高效的子图搜索

• 发表时间: 2024-04
• 期刊: 40th IEEE International Conference on Data Engineering
• 作者: Yuan, Lyuheng;Ahmad, Akhlaque;Yan, Da;Han, Jiao;Adhikari, Saugat;Yu, Xiaodong;Zhou, Yang
• 通讯作者: Zhou, Yang