A bit-parallel algorithm for searching multiple patterns with various lengths

• We present an extension of a bit-parallel algorithm for fast string search.
• The algorithm maximizes the stability of search throughput for multiple patterns of different lengths.
• Bit and data parallelism are exploited via AVX2 and OpenMP, respectively.
• Rapid identification of matching patterns is realized by a data padding scheme that regularizes control flow.
• Stable search throughput is achieved for arbitrary text and patterns that fit into a word.

In this paper, we present an Advanced Vector Extensions (AVX) accelerated method for a bit-parallel algorithm that realizes fast string search for maximizing stable search throughput. An advantage of our method is that it accelerates string search by regularizing both control flow and data structures. This regularization facilitates the exploitation of the latest vector instruction set to achieve efficient parallel search of multiple patterns of different lengths. We use AVX instructions to increase search throughput per CPU core and employ OpenMP directives to realize data-parallel search of strings. As a result, we found that our data structure doubled search throughput as compared with a previous bit-parallel approach that used a data structure for patterns of the same length. We also found that our method achieved stable search throughput for arbitrary data if the pattern size is large, but small enough to fit into a word. Some experimental results are provided to understand the advantage and disadvantage of our method with a comparison to Aho–Corasick based methods. We believe that our method is useful for large genome texts with many partial matches.