Exploiting parallelism in pattern matching
Authors:
Open Access
- 3 January 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Information Systems
- Vol. 9 (1) , 52-74
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Multichip modules: next-generation packagesIEEE Spectrum, 1990
- Perspective on BiCMOS VLSIsIEEE Journal of Solid-State Circuits, 1988
- Optical Techniques and Data/Knowledge Base MachinesComputer, 1987
- ALTEP — A cellular processor for high-speed pattern matchingNew Generation Computing, 1986
- A systolic VLSI matrix for a family of fundamental searching problemsIntegration, 1983
- Operational characteristics of a harware-based pattern matcherACM Transactions on Database Systems, 1983
- The Design of Special-Purpose VLSI ChipsComputer, 1980
- Text Retrieval ComputersComputer, 1979
- A fast string searching algorithmCommunications of the ACM, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977