Demystifying DFA performance: an in-depth evaluation and modelling prediction of DFA compression algorithms

Finite State Automata (FSAs) are an alternative representation of equivalent power to Regular Expressions (REs) commonly employed to analyze patterns against data effectively. There are two families of FSA: Non-Deterministic Finite State Automata (NFAs) and Deterministic Finite State Automata (DFAs). Between the NFA and the DFA representations, the former achieves a smaller memory footprint thanks to its non-determinism at the cost of slower execution times and higher bandwidth requirements. The latter guarantees attractive performance with the drawback of an exponential state blow-up. For this reason, numerous works aim to compress DFAs to reduce their memory footprint, requiring changes in the processing algorithms to implement the novel representations. However, these works need a thorough evaluation of these compact representations when executing the pattern-matching step. Therefore, this Thesis proposes a novel framework to systematically analyze two classes of the most effective DFA-compression algorithms and characterize their impact on the pattern-matching execution step beyond the originally targeted scenarios. Firstly, this Thesis evaluates static metrics such as state and transition compression and the time required to generate the compact representations. Then, it thoroughly assesses dynamic metrics, i.e., memory footprint, execution time, and energy requirements during the pattern-matching process. Finally, it analyzes the factors influencing the algorithm’s performance from both a benchmark composition and hardware perspective. The first aspect focuses on developing a predictive model that, based on key metrics such as DFA topology and execution time, can forecast algorithm performance. The second aspect investigates hardware constraints by analyzing the impact of CPU frequency, memory bandwidth, and computational limitations using the Roofline model. This comprehensive analysis provides a deeper understanding of performance bottlenecks in DFA execution, offering valuable insights for optimization. With this in-depth evaluation, this Thesis clarifies the tradeoff between memory compression, execution impact, and energy requirements of DFA-based compression algorithms in a modern context, supporting the design of ad-hoc pattern-matching engines and future development in the field.

Gli Automi a Stati Finiti (FSA) costituiscono una rappresentazione equivalente alle Espressioni Regolari (RE) che vengono spesso usate per l’analisi di pattern all’interno di dati. Esistono due famiglie di FSA: Non-deterministici (NFA) e deterministici (DFA), dove i primi garantiscono una minore occupazione di memoria attraverso la loro struttura non deterministica a fronte di tempi di esecuzione maggiori, mentre i secondi assicurano tempi di esecuzioni lineari, ma pagando un aumento esponenziale dell’occupazione in memoria. Alla luce di ciò, esistono numerosi lavori di ricerca che hanno esplorato come comprimere i DFA per ridurne l’occupazione di memoria, definendo di conseguenza nuove rappresentazioni. Tuttavia, appare necessaria un’analisi approfondita del comportamento di tali rappresentazioni nel processo esecutivo di pattern matching. In questa Tesi viene proposto un framework per la valutazione sistematica di algoritmi basati su DFA analizzando due famiglie di algoritmi di compressione concentrandosi sull’impatto che la riduzione dell’occupazione in memoria ha in diversi scenari applicativi. Viene proposta una valutazione di metriche statiche come la riduzione del numero degli stati e delle transizioni, ma anche il tempo richiesto per comprimere il DFA, questa analisi viene poi completata da una serie di misurazioni dinamiche come il tempo di esecuzione, l’occupazioni in memoria e l’energia richiesta durante la fase di esecuzione. Infine, viene presentato uno studio sui fattori che influenzano o limitano le prestazioni di questi algoritmi. L’analisi si concentra su due aspetti principali: da un lato, lo sviluppo di un modello predittivo capace di stimare il comportamento di un algoritmo in termini di tempi di esecuzione, riduzione delle transizioni e consumo energetico, attraverso lo studio della topologia degli automi e della composizione dei benchmark; dall’altro, l’utilizzo del Roofline Model per valutare l’impatto della frequenza del processore, della banda di memoria e della potenza di calcolo disponibile. Questa analisi approfondita fornisce una profilazione completa delle prestazioni degli algoritmi mettendo in luce il tradeoff tra riduzione dell’occupazione in memoria e tempi di esecuzione in un contesto moderno al fine di supportare lo sviluppo di motori di esecuzione e algoritmi futuri.