SHF: Small: High Performance Graph Pattern Mining System and Architecture

该研究项目旨在开发高性能的图模式挖掘系统和架构，该系统是各种应用的关键组件，包括挖掘生化结构，发现生物保守子网络，发现功能模块，程序控制流分析，入侵网络分析，挖掘通信图，社交网络分析，异常检测和挖掘XML结构。高性能的图模式挖掘使基础科学研究得以推进。这项研究的动机是需要扩展到大型图形和模式;最快的算法和一般的图形模式挖掘系统之间的巨大差距;以及当前计算机架构在执行此类工作负载时的效率低下。该项目通过寻求算法，系统，架构和硬件实现之间的协同作用来垂直推进该领域。该项目为女性、少数民族和本科生提供研究机会，以促进计算机科学教育的更广泛参与。特别是，该项目涉及非CS专业的学生，向他们介绍图形分析技术，以解决科学和工程问题。本研究采用自顶向下的方法，从算法开始，开发高效的图模式挖掘系统和架构。基于模式分解算法，它开发了高效和通用的系统机制和编译器优化与精确的成本模型。为了支持基于分区图的分布式图模式挖掘，提出了将模式枚举算法分解为具有关键抽象、可扩展嵌入的小任务的思想，并建立了一个高效的执行模型，实现了通信和计算的重叠。在架构层面，研究提出了新的扩展和架构组件，以支持流和交集操作。所提出的技术将在两个硬件原型中实现：（1）一个RISC-V处理器，具有用于流和交集操作的扩展集扩展;以及（2）一个分布式FPGA加速器，用于以可扩展嵌入为原语的图形模式挖掘。研究成果将在顶级系统和架构会议上发表。该项目将提供几个开源的图形模式挖掘系统，架构模拟器和硬件原型。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

This research project aims to develop high-performance systems and architectures for graph pattern mining, which the key component for various applications, including mining biochemical structures, finding biological conserved subnetworks, finding functional modules, program control-flow analysis, intrusion network analysis, mining communication graphs, social-network analysis, anomaly detection, and mining XML structures. High-performance graph pattern mining enables fundamental scientific research advance. The research is motivated by the need for scaling to large graphs and patterns; the significant gap between the fastest algorithm and general graph pattern mining systems; and the inefficiency in current computer architectures when executing such workloads. The project vertically advances the field by seeking synergies between algorithm, system, architecture, and hardware implementations. The project provides research opportunities to female, minority and undergraduate students to enhance the broader participation of computer science education. In particular, the project involves non-CS major students, introducing them to graph-analytics techniques to solve problems in science and engineering. This research takes a top-down approach, starting from algorithms and developing efficient graph pattern mining systems and architectures. Based on pattern-decomposition algorithms, it develops efficient and general system mechanisms and compiler optimizations with an accurate cost model. To support distributed graph pattern mining with partitioned graphs, it proposes the idea of breaking down pattern-enumeration algorithms to small tasks with a key abstraction, extendable embedding, and builds an efficient execution model to overlap the communication and computation. At the architecture level, the research proposes novel instruction-set extensions and architectural components to support the stream and intersection operations. The proposed techniques will be implemented in two hardware prototypes: (1) a RISC-V processor with an instruction-set extension for stream and intersection operations; and (2) a distributed FPGA accelerator for graph pattern mining with extendable embedding as the primitive. The research outcomes will be published in top system and architecture conferences. The project will deliver several open-source graph pattern mining systems, architecture simulators and hardware prototypes.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.