2017/12/10 by Alessandro Cinti, Filippo Maria Bianchi, Cinti, Alessandro +5
Computer Science · #Algorithms and Data Compression #Distributed #FOS: Computer and information sciences #Network Packet Processing and Optimization #Parallel #Software Testing and Debugging Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1712.03560
openalex publication_date 2017/12/10 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
Accelerating inexact string matching procedures is of utmost importance when\ndealing with practical applications where huge amount of data must be processed\nin real time, as usual in bioinformatics or cybersecurity. Inexact matching\nprocedures can yield multiple shadow hits, which must be filtered, according to\nsome criterion, to obtain a concise and meaningful list of occurrences. The\nfiltering procedures are often computationally demanding and are performed\noffline in a post-processing phase. This paper introduces a novel algorithm for\nOnline Approximate String Matching (OASM) able to filter shadow hits on the\nfly, according to general purpose priority rules that greedily assign\npriorities to overlapping hits. An FPGA hardware implementation of OASM is\nproposed and compared with a serial software version. Even when implemented on\nentry level FPGAs, the proposed procedure can reach a high degree of\nparallelism and superior performance in time compared to the software\nimplementation, while keeping low the usage of logic elements. This makes the\ndeveloped architecture very competitive in terms of both performance and cost\nof the overall computing system.\n