Title :
The tree-match chip
Author :
Smith, David R. ; Lin, Jing C.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
fDate :
5/1/1991 12:00:00 AM
Abstract :
A chip organization is proposed for the classical tree-pattern-matching problem. It is based on an algorithm which uses a combination of a content-addressed memory, shift registers, and one-bit-wide stacks. All tree pattern matches are found simultaneously in one scan of the subject stream. The chip could be operated as a coprocessor to speed up functional language processing implementations. Multiple chips can be cascaded to increase capacity, similar to the way in which memory chips are utilized. An example chip has been laid out in CMOS technology in a 40-pin standard frame. Comparisons to previous algorithms are discussed
Keywords :
CMOS integrated circuits; VLSI; circuit layout CAD; parallel algorithms; satellite computers; 40-pin standard frame; CMOS technology; chip organization; content-addressed memory; coprocessor; functional language processing; multiple chip cascading; one-bit-wide stacks; shift registers; subject stream scan; tree-match chip; tree-pattern-matching; Acceleration; CMOS technology; Computer science; Coprocessors; Hardware; Logic; Pattern matching; Pressing; Shift registers; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on
