On the design and automatic generation of MFSA-based accelerators using SPARX framework

Regular expressions (regexes) are widely used in workloads evaluating thousands of patterns over high-throughput input streams, such as deep packet inspection. Although software regex-matching engines can achieve high levels of optimization, thread-level parallelism and memory hierarchy constraints ultimately limit their performance. Traditionally, compilers translate each regex in a dataset into a separate FSA. Even when expressions share common state-transition subsequences, independent compilation prevents their reuse and forces redundant instantiations, increasing the overall automaton size. To address this inefficiency, researchers introduced the MFSA as a novel automaton family that merges multiple regexes into a unified structure, reduces states by 79% and transitions by 39%, and achieves a geometric mean throughput improvement of 5.99× over standard Nondeterministic and Deterministic Finite Automata (NFA/DFA) families in software. However, while NFA/DFA models already benefit from dedicated hardware accelerators that exploit spatial parallelism, which is better suited for automata-based computation, no hardware engine currently supports the MFSA. As a result, MFSA remains confined to software despite its algorithmic advantages. This thesis presents SPARX, a framework enabling MFSA execution on FPGA through an automated flow that translates regex datasets into synthesizable hardware. A novel MFSA-tailored State Transition Element is introduced as a modular primitive that maps each MFSA state into a dedicated hardware unit, and a complete spatial architecture is built upon it to realize native MFSA execution on FPGA. Across widely used benchmarks, the SPARX accelerator achieves a geometric mean speedup of 777.8× and an average energy reduction of 168.5× compared to the reference MFSA software engine on a multicore CPU. Compared to prior FPGA accelerators implementing classical NFA/DFA models, the SPARX accelerator delivers an average throughput improvement of 1.62× and an average LUT-normalized throughput gain of 3.13×.

Le espressioni regolari (regex) sono ampiamente utilizzate in applicazioni in cui migliaia di pattern devono essere valutati su flussi di dati ad alto throughput, come nella deep packet inspection. Sebbene le implementazioni software per il riconoscimento delle regex possano essere fortemente ottimizzate, le loro prestazioni rimangono limitate dal parallelismo a livello di thread e dai vincoli imposti dalla gerarchia di memoria. Tradizionalmente, i compilatori traducono separatamente ogni regex di un dataset in un automa a stati finiti. Anche quando più espressioni condividono sottosequenze comuni di stati e transizioni, la compilazione indipendente ne impedisce il riutilizzo e porta alla creazione di strutture ridondanti, aumentando la dimensione complessiva degli automi. Per superare questa inefficienza è stato introdotto il Multi-RE Finite State Automaton (MFSA), una nuova famiglia di automi che fonde più regex in una struttura unificata, riducendo il numero di stati del 79% e il numero di transizioni del 39%, e ottenendo un miglioramento medio geometrico del throughput pari a 5.99× rispetto alle famiglie classiche NFA e DFA in ambito software. Tuttavia, mentre NFA e DFA dispongono già di acceleratori hardware dedicati che sfruttano il parallelismo spaziale, nessun acceleratore hardware supporta attualmente l’MFSA, che rimane quindi confinato all’esecuzione software nonostante i suoi vantaggi algoritmici. Questa tesi presenta SPARX, un framework che consente l’esecuzione dell’MFSA su FPGA attraverso un flusso automatico che traduce dataset di regex in circuiti hardware sintetizzabili. Il framework introduce un elemento modulare denominato State Transition Element, che realizza in hardware ciascuno stato dell’MFSA, e definisce un’architettura spaziale completa costruita a partire da tale elemento. Su benchmark ampiamente utilizzati, SPARX ottiene uno speedup medio geometrico di 777.8× e una riduzione media del consumo energetico pari a 168.5× rispetto all’implementazione software di riferimento dell’MFSA eseguita su CPU multicore. Rispetto ai precedenti acceleratori FPGA basati su modelli classici NFA e DFA, SPARX aumenta il throughput di 1.62× e il throughput normalizzato per LUT di 3.13×.