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

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

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.