Optimizing Multi-Core Algorithms for Pattern Search

GIL COSTA, GRACIELA VERÓNICA; OCHOA, CÉSAR; PRINTISTA, ALICIA MARCELA

Mar del Plata

Workshop; XVIII Congreso Argentino de Ciencias de la Computación; 2013

CAECE

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.