Portal de Periódicos da CAPES

Design and analysis of a parallel VLSI string search algorithm

1989; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-51324-8_38

1611-3349

K. C. Lee, Victor Mak,

Parallel Computing and Optimization Techniques

String searching is one of the basic operations in many areas of non-numeric processing. In this paper, we propose a parallel VLSI string search algorithm called the Data Parallel Pattern Matching (DPPM) algorithm. The DPPM algorithm can efficiently utilize the high degree of integration of VLSI technology to attain very high speed processing through parallelism. The DPPM algorithm serially broadcasts and compares the pattern to a block of data in parallel. Performance of the DPPM has been evaluated both analytically and experimentally. Based on the simulation statistics and timing analysis on the hardware prototype, a search rate of multiple gigabytes per second is achievable using 2 µm CMOS technology.