Optimizing multi-core algorithms for pattern search

Abstract

The suffix array index is a data structure formed by sorting the suffixes of a string into lexicographic order. It is used for string matching, which is perhaps one of those tasks on which computers and servers spend quite a bit of time. Research in this area spans from genetics (finding DNA sequences), to keyword search in billions of web documents, to cyberespionage. The attractiveness is that they are completely “array based” and have some benefits in terms of improving the locality of memory references. In this work we propose and evaluate the performance achieved by a static scheduling algorithm for suffix array query search. We focus on multi-core systems 32- core system. Results show that our proposed algorithm can dramatically reduce the cost of computing string matching.