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

Volume

40

Issue

5

fYear

1991

fDate

5/1/1991 12:00:00 AM

Firstpage

629

Lastpage

639

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;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.88486

Filename

88486