SHF: Medium: Efficient and Scalable Pattern Matching via Hardware-Software Co-Design

SHF：中：通过软硬件协同设计实现高效且可扩展的模式匹配

• 批准号: 2313062
• 负责人: Kaiyuan Yang
• 金额: $ 120万
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-01 至 2027-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2313062&HistoricalAwards=false
• 关键词: SHF; Medium; Efficient; Scalable; Pattern

In today's computing landscape, analyzing complex unstructured data streams from physical, biological, chemical, and other systems is becoming increasingly common. However, as the amount of data being processed continues to grow, energy consumption has become a major bottleneck. This is especially true for small, battery-powered, and resource-constrained devices, but also for large data centers where energy usage can lead to high monetary costs and carbon dioxide emissions. To address these challenges, our project aims to design a holistic computing platform that is both ultra-efficient and widely applicable. This platform will help alleviate the scarcity of computing and energy resources for real-time data-driven applications such as network security, bioinformatics, and data mining.The project focuses on creating a holistically designed computing system for detecting rich patterns over data streams, which is a key computational task for the analysis of unstructured data. The patterns are described using high-level formal specification languages based on extended regular expressions. For efficient pattern matching, the formal specifications are translated into a novel type of nondeterministic finite-state automata augmented with registers. These automata are co-designed with a non-von Neumann hardware architecture that leverages content-addressable memories and efficient hardware implementations of low-level computational primitives. A holistic co-design strategy is followed for the automata model, hardware, and software, resulting in a complete system prototype, including a fabricated chip and a complete software toolchain for compiling patterns and deploying them on the chip for execution. Moreover, the project develops high-quality benchmarks for pattern-matching applications and explores new applications of the pattern-matching hardware in pathogen identification and long-read mapping of human genomic data. The project will also train graduate students.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.

在当今的计算环境中，分析来自物理、生物、化学和其他系统的复杂非结构化数据流正变得越来越普遍。然而，随着处理的数据量持续增长，能源消耗已成为一个主要瓶颈。对于电池供电和资源受限的小型设备尤其如此，但对于能源使用可能导致高货币成本和二氧化碳排放的大型数据中心也是如此。为了应对这些挑战，我们的项目旨在设计一个既超高效又广泛适用的整体计算平台。该平台将有助于缓解网络安全、生物信息学和数据挖掘等实时数据驱动应用程序计算和能源资源的稀缺性。该项目专注于创建一个整体设计的计算系统，用于检测数据流中的丰富模式，这是非结构化数据分析的关键计算任务。使用基于扩展正则表达式的高级形式规范语言来描述模式。为了实现高效的模式匹配，将形式化规范转化为一种新型的带有寄存器的非确定有限状态自动机。这些自动机与非von Neumann硬件体系结构共同设计，该体系结构利用内容可寻址存储器和低级计算原语的高效硬件实现。对自动机模型、硬件和软件遵循整体协同设计策略，从而产生完整的系统原型，包括制造的芯片和用于编译图案并将其部署在芯片上以供执行的完整软件工具链。此外，该项目还为模式匹配应用程序开发了高质量的基准，并探索了模式匹配硬件在病原体识别和人类基因组数据的长读图谱中的新应用。该项目还将培养研究生。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。