Alveare : a novel mixed hardware-software framework for efficient execution of regular expressions

Nowadays, the data produced by users are increasing impressively and, if correctly manipulated, they contain helpful information. Hence, it becomes paramount to analyze them to find specific patterns in the analyzed data, taking related actions when there is a correspondence. A particular field is genomic that requires finding patterns in the analyzed Deoxyribonucleic Acid (DNA). Similarly, in computer security, it is necessary to find attack patterns and malware signatures, potentially avoiding attacks in real-time. Likewise, given input keywords, search engines retrieve web documents for final users. In computer science, Regular Expressions (REs) allow fast and straightforward patterns description. However, the current software systems rely on general engines that are not optimized for a specific set of tasks, such as the REs one. Instead, hardware-centric solutions, especially Field- Programmable Gate Array (FPGA)-based, are gaining remarkable interest thanks to their specialization prospectives. However, in the specific case of REs, current hardware accelerators efficiently support only specific patterns or well-defined scenarios. For these reasons, this thesis proposes a novel mixed hardware- software framework, called Alveare, for efficient execution of REs, both from a time and energy point of view. The presented approach is composed of the software part, which, thanks to the compiler, can translate REs into Alveare executable instructions. Moreover, the architecture executes the bi- nary code using advanced hardware techniques tailored for REs to boost the computation. Alveare also embeds a run-time manager component that handles the hardware-software communication. The architecture relies on FPGAs which allow fast prototyping and run-time adaptability with remarkable execution times and low energy consumption results.

Al giorno d’oggi, i dati prodotti dagli utenti stanno aumentando in modo impressionante e se manipolati correttamente, contengono informazioni utili. Diventa cosi fondamentale analizzarli per trovare un pattern specifico ed intraprendere azioni correlate. Un campo particolare è quello genomico che, che in applicazioni tipiche richiede la ricerca di pattern nei Deoxyribonucleic Acid (DNA) analizzati. Allo stesso modo, nella sicurezza informatica, è necessario trovare pattern di attacco e firme di malware, cosi da potenzialmente evitare attacchi in tempo reale. Allo stesso modo, date le parole chiave di input, i motori di ricerca recuperano documenti web e li mostrano agli utenti finali. In informatica, le Regular Expression (RE) consentono un veloce e una semplice descrizione dei pattern. Tuttavia, gli attuali sistemi software si basano su motori generali che non sono ottimizzati per molti domini applicativi specifici come quello delle RE. Invece, soluzioni incentrate sull’hard- ware, specialmente quelle basati su Field-Programmable Gate Array (FPGA), stanno riscuotendo notevole interesse grazie alle loro prospettive di specializzazione. Tuttavia, nel caso specifico delle RE, gli attuali acceleratori hardware supportare in modo efficiente solo pattern specifici o ben definiti scenari. Per questi motivi, questa tesi propone un nuovo hardware-software framework, denominato Alveare, per l’esecuzione efficiente delle RE, sia dal punto di vista temporale che energetico. L’approccio presentato è composto dalla parte software, che, grazie al compilatore, può tradurre le RE in istruzioni eseguibili da Alveare. Inoltre, l’architettura esegue il codice binario utilizzando tecniche hardware avanzate su misura per le RE potenziando il calcolo. Alveare incorpora anche un run-time manager che gestisce la comunicazione hardware-software. L’architettura si basa su FPGA che consente una prototipazione rapida e una adattabilità a run- time con tempi di esecuzione notevoli e risultati a basso consumo energetico. Per questi motivi, questa tesi propone un nuovo framework hardware misto al software per l’esecuzione efficiente delle RE, sia dal punto di vista ti tempo di esecuzione che energetico.