String search in coarse-grained parallel computers

Given a text string T[1, n], the multistring search problem consists of determining which of k pattern strings {X-t [1, m], X-2[1, m],..., X-k[1, m]}, provided on-line, occur in T. We study this problem in the BSP model [27], and then extend our analysis to other coarse-grained parallel computational models. We refer to the relevant and difficult case of long patterns, that is m greater than or equal to p, where p is the number of available processors, and provide an optimal result with respect to both computation and communication times, attaining a constant number of supersteps. We then study single string search (i.e., k = 1), and show how the multistring search algorithm can be employed to speed up the process and balance the communication cost. The proposed solution takes a constant number of supersteps, and achieves optimal communication time if the string to be searched is longer than p(2). Our results are based on the distribution of a proper data structure among the p processors, to reduce and balance the communication cost. We also indicate how short patterns can be efficiently dealt with, through a completely different algorithmic approach.