A Framework for the Design and Generation of Spatial MFSA Accelerators: The SPARX Approach

The growing demand for high-throughput pattern matching in fields such as cybersecurity, bioinformatics, and natural language processing has intensified research into automata-based accelerators. Regular expressions, while expressive and versatile, impose significant computational overhead when evaluated over massive data streams. Traditional CPU and GPU solutions, despite vectorization and multi-threading, remain constrained by the sequential execution model of Von Neumann architectures. This thesis addresses these limitations by introducing SPARX, the first complete framework that translates the Multi-RE Finite State Automaton (MFSA) formalism into synthesizable spatial hardware. The work builds on iMFAnt, a software engine that merges multiple regular expressions into a unified automaton, reducing redundancy by identifying shared prefixes, suffixes, and internal sequences. The MFSA model enables simultaneous multi-regex evaluation within a single traversal of the input, achieving compactness and high algorithmic efficiency. While iMFAnt demonstrated remarkable software performance—reducing state counts by 72%, transitions by 39%, and improving throughput up to 6×, its potential for spatial acceleration had not yet been explored. SPARX bridges this gap as a complete framework that translates the MFSA model into spatial hardware. It integrates simulation, validation, hardware resource utilization prediction, and automatic hardware generation into a single flow, mapping merged automata onto reconfigurable logic to combine algorithmic compression with hardware-level concurrency.

Author dc:creator

• Alessandro Aldo Marina (24400601)

• Computer Architecture
• Computer Science
• Electrical and Computer Engineering

Statement dc:rights

• In Copyright
• Open Access after 2031-05-01

DOI dc:identifier

https://doi.org/10.25417/uic.32995673.v1

OAI identifier oai:identifier

oai:figshare.com:article/32995673