Parallel algorithms for string matching problem on single and two dimensional reconfigurable pipelined bus systems.

INTRODUCTION

String matching mainly deals with the problem of finding all the occurrences of a string in a given text. String matching had been one of the most extensive problems in computer technologies during the past two decades. Pattern matching is widely implemented in information retrieval, web search engine, DNA sequencing (13), (14), (16), artificial intelligence and several other fields. Two sub-problems for the string matching problem considered, the first is the exact string matching and the second is approximate string matching with k- mismatches. Experimental results of well known sequential algorithm can be found in (6), (9). Since the VLSI (Very Large Scale Integration) technology has been developed rapidly, hardware approaches have also been proposed (5), (12). But most of the algorithms that can be found in the literature multiphase algorithms; they need preprocessing phase in order to retrieve special structures in either the pattern or the reference string. It is then difficult to build special purpose hardware for just string matching tasks. We propose two kinds of parallel algorithms for both string matching problems without any preprocessing phase. First propose on-line solutions; it means that they process the inputs in turn, without knowledge of whole pattern at the beginning of the computation; its elements will be treated one by one. Then we give solutions that require a constant number of steps. Several computational models that have been considered for parallel string matching algorithms the PRAM model, mesh structure (17) and etc. The parallel string matching algorithm is often said to be optimal if its cost is O (nm). The first optimal O (log m) time string matching algorithm was introduced by Galil (3).

The text string of length n and a pattern of length m, Galil presented a optimal constant time complexity parallel algorithm with n processors for the exact string matching problem (3) on a conceptual CRCW PRAM model but this algorithm requires additional space and needs to preprocess the text string. Recently, on a linear systolic array, Park and George proposed an architecture based on data flow for both sub problems (15), solving them in O (n/k + [alpha]) where k is the number of streams and 1[less than or equal to] [alpha] [less than or equal to] m with k*m processors. In this algorithm the approaches were based on the computation of the well-known Hamming distance. The string matching problem solving on the LARPBS model, introduced by Pan and Li in (7), it has known a growing success since the end of two thousands as well as all optical bus based models. Many authors have been discussed for sorting or matrix multiplication or selection (2), (8), (11).The used pipelined optical bus, instead of an electrical one. The pipelined optical bus utilizes optical fibers to transmit information.

Larpbs Model: The linear array with a reconfigurable pipelined bus system (LARPBS) consists of three waveguides. It is presented by Pan and Li in (7). It is based on the ideas of using pipelined bus systems and processor array reconfiguration. This is called the one dimensional parallel processing optical model. In such model, a pipelined optical bus system uses optical waveguides instead of electrical signals to transfer the several messages which can circulate at the same time among processors through the bus in a pipelined fashion. The communication time for the LARPBS model is measured based on the number of bus cycles used. A bus cycle is the end-to-end propagation delay on the bus .The time complexity of an algorithm is determined in terms of time steps, where a single time step comprises one …