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

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

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.