For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Programmable Pattern Matching Machine for High Speed Recognition of Regular Sets
Shin'ichi WAKABAYASHI Tohru KIKUNO Noriyoshi YOSHIDA Takashi FUJII
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1984/07/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: VLSI Algorithms
Full Text: PDF(491KB)>>
The great technological progress in very large scale integration (VLSI) of electronic circuits has made it possible to implement a large distributed computing system on a single VLSI chip. Distributed algorithms suited for VLSI implementation are generally called 'VLSI algorithms', and many VLSI algorithms have been devised for solving several kinds of problems. This paper discusses a VLSI algorithm for pattern matching. We propose a new VLSI-oriented pattern matching algorithm in which regular expressions are adopted to represent a pattern. The proposed algorithm will be implemented on a configurable multi-processor system, which can dynamically change its interconnections among the processors according to the external inputs. Thus the pattern may be arbitrarily changed after the chip fabrication. We call such an algorithm the 'programmable' pattern matching machine (PPM for short). The programmability makes it possible for PPM to have wide applications which the previously known algorithms could hardly have. PPM consists of n(n1)/2 processors, where n is the length of a pattern, and can recognize a string of length m in m (independent of n) clock periods. PPM also has preferable properties, such as a regular structure and a simple control mechanism, for VLSI implementation.