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)   Vol.E67   No.7   pp.363-370
Publication Date: 1984/07/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: VLSI Algorithms

Full Text: PDF(491KB)>>
Buy this Article

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.