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可扩展的图形处理系统，这些系统遵循一种新的基于任务的并行范式，称为t -思考者。然而，由于GPU的IO带宽和计算能力之间存在更大的差距，并且由于GPU程序具有可扩展性的独特编程要求，因此将这种成功扩展到GPU丰富的环境中并非易事。本项目将开发一种新的基于任务的分布式GPU框架T-thinkerGPU，并在其上实现子图匹配、密集子图挖掘和频繁子图模式挖掘三种应用。T-thinkerGPU将在阿贡国家实验室（ANL）的极光超级计算机以及UAB的Cheaha超级计算机上进行测试，该实现将利用现代GPU功能，包括原子操作，统一共享内存和动态并行性。这项工作将为与ANL的长期合作奠定坚实的基础，为各种科学应用开发gpu可扩展的高性能计算解决方案。该项目还将培训阿拉巴马州急需的gpu编程人员（包括一名博士生，他也将访问ANL），所有提议的工具都将是开源的。这项研究基础设施改善轨道4 EPSCoR研究研究员（RII Track-4）提案将为阿拉巴马大学伯明翰分校（UAB）的助理教授提供奖学金并为研究生提供培训。GPU超级计算机正越来越多地取代CPU超级计算机，希望不仅能从显著的性能改进中受益，还能从能源效率中受益。基于基于任务的并行范式t -思考者在多cpu环境中扩展图形处理的成功，该项目旨在研究基于任务的新技术，以在多gpu环境中扩展基本的计算密集型图形操作，特别是基于英特尔gpu的ANL百亿亿次极光超级计算机。具体来说，该项目将首先研究有效的表示方案，这些方案对输入图和中间子图结果进行编码和压缩，以减少内存占用，并在共享内存中实现合并内存访问和数据重用，例如散列邻域签名和基于模式的无损压缩。其次，该项目将设计gpu友好的基于任务的基本图操作算法，包括子图匹配、密集子图挖掘和频繁子图模式挖掘，以释放极光超级计算机等多gpu环境所带来的大规模并行性。新技术将被研究，如核即任务执行模型，一个真正的混合BFS-DFS任务调度策略，以及其他几种GPU优化方法，这些方法将被合并到一个统一的编程框架T-thinkerGPU中，考虑到可扩展性，以促进GPU可扩展的基于任务的算法的发展，用于其他图形操作。最后，开发的GPU程序将在极光（使用英特尔GPU）和UAB的Cheaha超级计算机（使用英伟达GPU）上进行广泛评估，使用ANL和UAB的公共基准测试和科学应用程序，代码将在GitHub上发布。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Faster Depth-First Subgraph Matching on GPUs

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

• 发表时间: 2024
• 期刊: 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

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

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

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

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

FSM-Explorer: An Interactive Tool for Frequent Subgraph Pattern Mining from a Big Graph

FSM-Explorer：用于从大图中挖掘频繁子图模式的交互式工具

• 发表时间: 2024
• 期刊: 40th IEEE International Conference on Data Engineering
• 作者: Khalil, Jalal;Yan, Da;Yuan, Lyuheng;Han, Jiao;Adhikari Saugat;Long Cheng;Zhou Yang
• 通讯作者: Zhou Yang

Accelerating k-Core Decomposition by a GPU

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