CRII: SHF: A Parallel and Distributed Framework for Graph Mining on GPUs

从一个大图中挖掘出满足一定条件的子图在社区检测和子图匹配等许多应用中都是很有用的。大图中的子图挖掘越来越依赖于并行和分布式计算来衡量数据的处理量和速度。已经开发了许多基于中央处理器(CPU)的系统来并行化图挖掘算法。然而，我们国家正在以前所未有的速度用图形处理单元(GPU)超级计算机取代CPU超级计算机，期望不同的CPU/GPU不仅可以提高性能，还可以节省能源。这一趋势给大规模图形处理带来了困难，因为用户必须为每个单独的图形问题设计定制的GPU程序。该项目的创新之处在于：1)将开发一个新的图并行和分布式框架，将在图形处理器丰富的环境中加速图形计算；2)将在该框架上实现包括密集子图挖掘和子图匹配在内的多个图挖掘任务，以利用多个GPU的巨大并行性。该项目的影响是：1)它服务于许多跨学科项目，如生物信息学和化学信息学。2)该项目将公开使用，并将丰富与大数据和并行计算相关的现有课程，从而为科学界提供长期利益。该项目旨在多CPU环境中扩展图形处理的成功，并研究新的基于任务的技术，以在多GPU环境中扩展基本计算密集型图形操作。现有的GPU算法由于GPU内存的有限大小而施加了内存限制，这限制了可以处理的输入图形的大小。这个项目将探索有效的表示方案，对输入图和中间子图结果进行紧凑的编码和压缩，以最大限度地减少GPU的内存占用。这将启用合并的全局内存访问，并在共享内存中实现数据重用。GPU友好的基于任务的算法将被设计用于基本的图操作，包括子图匹配和密集子图挖掘，以释放由多GPU环境实现的大规模并行性。所有图形挖掘修剪规则将使用与新任务方案相关联的GPU高级曲线级原语进行仔细的重新设计。该奖项反映了NSF的法定使命，并已通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. Subgraph mining in a big graph increasingly relies on parallel and distributed computing to scale the data processing volume and velocity. Numerous central processing unit (CPU)-based systems have been developed to parallelize graph mining algorithms. However, our nation is replacing CPU supercomputers with graphics processing unit (GPU) supercomputers faster than ever before, with the expectation that heterogeneous CPU/GPUs will not only boost performance but also conserve energy. This trend poses difficulties for large-scale graph processing, as users must design GPU programs tailored to each individual graph problem. The project’s novelties are: 1) a new graph parallel and distributed framework will be developed, which will accelerate graph computations in a GPU-rich environment; 2) multiple graph mining tasks, including dense subgraph mining and subgraph matching, will be implemented atop this framework to take advantage of the massive parallelism of multi-GPUs. The project's impacts are: 1) it serves a number of cross-disciplinary projects, such as bioinformatics and chem-informatics 2) this project will be released for public use and will enrich existing courses related to big data and parallel computing, thereby providing long-term benefits to the scientific community.This project aims to build on the success in scaling graph processing in a multi-CPU environment and investigate novel task-based techniques to scale fundamental compute-intensive graph operations in a multi-GPU environment. Existing GPU algorithms impose a memory restriction because of the restricted size of GPU memory, which limits the size of input graphs that can be processed. This project will explore effective representation schemes that encode and compress the input graph and intermediate subgraph results compactly to minimize the memory footprint of the GPU. This will enable coalesced global memory access and enable data reuse in shared memory. GPU-friendly task-based algorithms will be designed for fundamental graph operations including subgraph matching and dense subgraph mining, to unleash the massive parallelism enabled by a multi-GPU environment. All graph mining pruning rules will be carefully re-designed using the GPU advanced warp-level primitives in association with the new task schemes.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.