Reconfigurable low-latency real-time matching engines

Description

Techniques such as Cryptography, GPS or DNA alignment have in common the need to search in a sequence for a particular match. The speed of those matching engines can be limited by the number of queries or variations of a single reference. That is particularly the case for a DNA analysis supported by big data bases and looking for possible mutations. String matching algorithms, required for network instruction detection systems, are a basic example where processing speed, parallelism and throughput are mandatory. Deterministic and non-deterministic algorithms are generally required, in particular, when the target length varies. Memory requirements and scalability can also affect the capability of parallel processing. The size of the automaton in charge of the matching engine can grow exponentially depending on the number of transitions witch will also affect the processing speed. In this context, the objective of this thesis is to provide algorithms and architectures combined to provide a low-latency real-time matching engine, processing in parallel multiple queries of variable length with limited memory resources and reduced power consumption. The first contribution will be the evaluation of existing algorithms to process multiple keywords simultaneously in terms of throughput, memory requirements and power consumption when executed on single-core, multicore and GPU architectures. The second contribution will be the proposal of a matching engine algorithm capable to increase the throughput, parallel processing and memory requirements. The thirst contribution will be the proposal of a matching engine architecture, it will be a hardware IP dealing with multiple queries in parallel to be offered as an IP component for future generation SoC (System on Chip) platforms. The last contribution will be to consider to automate the generation of the hardware matching engine based on the keywords set and queries.