Bit-Parallel Approximate Pattern Matching on the Xeon Phi Coprocessor

Bit-parallel pattern matching encodes calculated values in bit arrays. This approach gains its efficiency by performing multiple updates within a machine word. An important parameter is therefore the machine word size (e.g. 32 or 64 bits). With the increasing length of vector registers, the efficient mapping of bit-parallel pattern matching algorithms onto modern high performance computing architectures is becoming increasingly important. In this paper, we investigate an efficient implementation of the Wu-Manber approximate pattern matching algorithm on the Intel Xeon Phi coprocessor. This architecture features a 512-bit long vector processing unit (VPU) as well as a large number of processing cores. We present two mappings of the Wu-Manber algorithm based on auto-vectorization and intrinsics, respectively. Our evaluation shows that the intrinsic approach yields higher performance and gains a speedup of around two orders-of-magnitude compared to a serial CPU version. The source code is available at http://xbitpar.sourceforge.net/.