String matching on IDP: a string matching algorithm for vector processors and its implementation
Yoshinori Mishina, Keiji Kojima · 2002
The paper describes a new string matching algorithm that is suitable for vector processors. The hardware implementation of the algorithm is also presented. The algorithm consists of two parts. In the first part, candidate strings that are similar to pattern strings are extracted from a text string (cutout part). Candidate strings may include noise strings, and these are removed in the second part of the algorithm. Each part is efficiently vectorized using vector instructions of conventional vector processors for numerical computations. Moreover, the cutoff part is implemented as an added instruction of the Integrated Database Processor (IDP). Measurements show that this algorithm using IDP is more than 10 times faster than a scalar program using the Aho-Corasick method.>