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

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.