CRII: SHF: Expediting Subgraph Matching on GPUs

CRII：SHF：加快 GPU 上的子图匹配

• 批准号: 2000722
• 负责人: Hang Liu
• 金额: $ 17.5万
• 依托单位: Stevens Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-10 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2000722&HistoricalAwards=false
• 关键词: CRII; SHF; Expediting; Subgraph; Matching

We are living in an increasingly connected world, where the Big Data movement has resulted in not only more data but, more importantly, more connected data, such as, social networks, knowledge graphs and deep neural networks. Sub-graph isomorphism, which finds sub-graphs of interest from an enormous data graph, is a fundamental tool for an array of critical applications, e.g., cyber-security, criminal detection and health care. In spite of such a great potential, identifying all isomorphic sub-graphs is a challenge in the Big Data context due to high computation complexity and memory consumption. This project addresses this issue, and will benefit both industrial and academic communities, as well as train undergraduate, underrepresented and STEM high school students for high-performance data analytics (HPDA) research (https://www.uml.edu/research/hpda/).Conventional efforts split the query graph into two disjoint parts for prune and join, which impairs the prune strength of the query graph and results in a large volume of unpromising candidates for the 'join' phase. This project advocates an entire query graph-based prune approach to resolve the computation and memory challenge. In particular, this research consists of two parts: 1) algorithms research -- provenance-aware intersection-based candidate construction -- will greatly reduce the false positives faced by the conventional approaches; 2) systems research, i.e., GPU-enabled massively parallel provenance group intersection, will tackle the bottleneck that is encountered on conventional CPU platforms, through use of Graph Processing Unit (GPU) acceleration.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.

我们生活在一个联系日益紧密的世界里，大数据运动不仅带来了更多的数据，更重要的是，带来了更多的连接数据，比如社交网络、知识图谱和深度神经网络。子图同构，从一个巨大的数据图中找到感兴趣的子图，是一系列关键应用的基本工具，例如，网络安全，犯罪侦查和医疗保健。尽管有如此巨大的潜力，但是在大数据环境下，由于计算复杂度和内存消耗高，识别所有同构子图是一个挑战。该项目解决了这一问题，并将有利于工业界和学术界，以及培养本科生，代表性不足和STEM高中学生进行高性能数据分析（HPDA）研究（https://www.uml.edu/research/hpda/）.Conventional)，努力将查询图分成两个不相交的部分进行修剪和连接，这削弱了查询图的修剪强度，并导致大量没有希望的候选对象进入“连接”阶段。这个项目提倡一种完整的基于查询图的修剪方法来解决计算和内存方面的挑战。具体而言，本研究包括两个部分：1)算法研究——基于来源感知的交叉点候选构建——将大大减少传统方法面临的误报；2)系统研究，即GPU支持的大规模并行源群交叉，将通过使用图形处理单元（GPU）加速来解决传统CPU平台上遇到的瓶颈。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

GSOFA: Scalable Sparse Symbolic LU Factorization on GPUs

GSOFA：GPU 上的可扩展稀疏符号 LU 分解

• DOI: 10.1109/tpds.2021.3090316
• 发表时间: 2022
• 期刊: IEEE transactions on parallel and distributed systems
• 影响因子: 5.3
• 作者: Gaihre, Anil;Li, Xiaoye S;Liu, Hang
• 通讯作者: Liu, Hang

SIMD-X: Programming and Processing of Graph Algorithms on GPUs

• 发表时间: 2018-12
• 作者: Hang Liu;Howie Huang

Trust: Triangle Counting Reloaded on GPUs

信任：在 GPU 上重新加载三角形计数

• DOI: 10.1109/tpds.2021.3064892
• 发表时间: 2021-11-01
• 期刊: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
• 影响因子: 5.3
• 作者: Pandey, Santosh;Wang, Zhibin;Liu, Hang
• 通讯作者: Liu, Hang

FTDL: A Tailored FPGA-Overlay for Deep Learning with High Scalability

• DOI: 10.1109/dac18072.2020.9218581
• 发表时间: 2020-07
• 期刊: 2020 57th ACM/IEEE Design Automation Conference (DAC)
• 作者: Runbin Shi;Yuhao Ding;Xuechao Wei;He Li;Hang Liu;Hayden Kwok-Hay So;Caiwen Ding

Dr. Top-k: Delegate-Centric Top-k on GPUs

• DOI: 10.1145/3458817.3476141
• 发表时间: 2021-09
• 期刊: SC21: International Conference for High Performance Computing, Networking, Storage and Analysis
• 作者: Anil Gaihre;Da Zheng;Scott Weitze;Lingda Li;S. Song;Caiwen Ding;X. Li;Hang Liu