A tree-matching chip

作     者：Krishna, V Ranganathan, N Ejnioui, A 

作者机构：Univ S Florida Dept CS&E Tampa FL 33620 USA 

出 版 物：《IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS》 (IEEE Trans Very Large Scale Integr VLSI Syst)

年 卷 期：1999年第7卷第2期

页      面：277-280页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：object recognition parallel algorithms systolic tree matching VLSI 

摘      要：Tree matching is an important problem used for three-dimensional object recognition in image understanding and vision systems. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree, In this paper, we describe the design and implementation of a very large scale integration (VLSI) chip for tree pattern matching. The architecture is based on an iterative algorithm that is mapped to a systolic array computational model and takes O(t(n + a)) time to process a subject of size n using n processors where a is the length of the largest substring in the pattern and t is the number of substrings in the pattern. The variables and nonvariables of the pattern tree are processed separately, which simplifies the hardware in each processing element, The proposed partitioning strategy is independent of the problem size and allows larger strings to be processed based on the array size, A prototype CMOS VLSI chip has been designed using the Cadence design tools and the simulation results indicate that it will operate at 33.3 MHz.