Portal de Periódicos da CAPES

Exploiting parallelism in pattern matching

1991; Association for Computing Machinery; Volume: 9; Issue: 1 Linguagem: Inglês

10.1145/103731.103734

1558-1152

Victor Mak, Kuo Chu Lee, Ophir Frieder,

Parallel Computing and Optimization Techniques

We propose a document-searching architecture based on high-speed hardware pattern matching to increase the throughput of an information retrieval system. We also propose a new parallel VLSI pattern-matching algorithm called the Data Parallel Pattern Matching (DPPM) algorithm, which serially broadcasts and compares the pattern to a block of data in parallel. The DPPM algorithm utilizes the high degree of integration of VLSI technology to attain very high-speed processing through parallelism. Performance of the DPPM has been evaluated both analytically and by simulation. Based on the simulation statistics and timing analysis on the hardware design, a search rate of multiple gigabytes per second is achievable using 2-μm CMOS technology. The potential performance of the proposed document-searching architecture is also analyzed using the simulation statistics of the DPPM algorithm.