Parallel template matching on a restricted addressing mode
Satoshi Fujita, Masafumi Yamashita, T. Ae · 2002
Discusses the limitation on the speedup of the template matching by an ideal parallel processing scheme. The authors treat it through the following simplified pattern matching problem, i.e., on an ideal parallel processing scheme with significantly large number of processing elements and the interconnection, identify the position of a template in a text as fast as possible. Assuming a single instruction constraint on the scheme, the matching operation takes O(log/sup 2/n/loglogn) time, while without the constraint, it takes O(logn) time where n is the size of the template.>