A tree matching chip

Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree m...

Full description

Saved in:
Bibliographic Details
Main Authors: Krishna, V., Ejnioui, A., Ranganathan, N.
Format: Conference Proceeding
Language:English
Subjects:
Computational modeling
Concurrent computing
Logic
Object recognition
Optimizing compilers
Parallel algorithms
Partitioning algorithms
Pattern matching
Systolic arrays
Terminology
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 285
container_issue
container_start_page 280
container_title
container_volume
creator Krishna, V.
Ejnioui, A.
Ranganathan, N.
description Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Recently, two linear systolic array algorithms have been proposed by the authors. In this paper, we propose an improved approach wherein the the systolic algorithm is based on a linear array of fixed size independent of the problem size and larger strings are partitioned and processed based on the array size. Also, the architecture is simplified by moving the logic for processing variables in each PE to a single PE attached at the end. The systolic algorithm and architecture have been verified through simulation using the Cadence design tools.
doi_str_mv 10.1109/ICVD.1996.489611
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_489611</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>489611</ieee_id><sourcerecordid>489611</sourcerecordid><originalsourceid>FETCH-LOGICAL-i104t-7975c16a40a1abeceb134c63d18db10570f96b88ab6f865a34c1de45233eaf3</originalsourceid><addsrcrecordid>eNotj0tLw1AQRgcfYFrduRBX-QOJM_cxd-6yxFeh4EJxW-5NJhqxUpJs_PcW6uY7iwMHPoAbwpoI4926eb-vKUaunUQmOoHCWMGKo7GnsEAh4WCM-DMoCNlWkTlcwGKavhBRPIYCrlflPKqWuzS3n8PPR3nY_SWc9-l70qt_LuH18eGtea42L0_rZrWpBkI3VyEG3xInh4lS1lYzWdey7Ui6TOgD9pGzSMrcC_t0kNSp88ZaTb1dwu2xOqjqdj8OuzT-bo9X7B9jPzke</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>A tree matching chip</title><source>IEEE Xplore All Conference Series</source><creator>Krishna, V. ; Ejnioui, A. ; Ranganathan, N.</creator><creatorcontrib>Krishna, V. ; Ejnioui, A. ; Ranganathan, N.</creatorcontrib><description>Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Recently, two linear systolic array algorithms have been proposed by the authors. In this paper, we propose an improved approach wherein the the systolic algorithm is based on a linear array of fixed size independent of the problem size and larger strings are partitioned and processed based on the array size. Also, the architecture is simplified by moving the logic for processing variables in each PE to a single PE attached at the end. The systolic algorithm and architecture have been verified through simulation using the Cadence design tools.</description><identifier>ISSN: 1063-9667</identifier><identifier>ISBN: 0818672285</identifier><identifier>ISBN: 9780818672286</identifier><identifier>EISSN: 2380-6923</identifier><identifier>DOI: 10.1109/ICVD.1996.489611</identifier><language>eng</language><publisher>IEEE</publisher><subject>Computational modeling ; Concurrent computing ; Logic ; Object recognition ; Optimizing compilers ; Parallel algorithms ; Partitioning algorithms ; Pattern matching ; Systolic arrays ; Terminology</subject><ispartof>Proceedings of 9th International Conference on VLSI Design, 1996, p.280-285</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/489611$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2057,4049,4050,27924,54554,54919,54931</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/489611$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Krishna, V.</creatorcontrib><creatorcontrib>Ejnioui, A.</creatorcontrib><creatorcontrib>Ranganathan, N.</creatorcontrib><title>A tree matching chip</title><title>Proceedings of 9th International Conference on VLSI Design</title><addtitle>ICVD</addtitle><description>Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Recently, two linear systolic array algorithms have been proposed by the authors. In this paper, we propose an improved approach wherein the the systolic algorithm is based on a linear array of fixed size independent of the problem size and larger strings are partitioned and processed based on the array size. Also, the architecture is simplified by moving the logic for processing variables in each PE to a single PE attached at the end. The systolic algorithm and architecture have been verified through simulation using the Cadence design tools.</description><subject>Computational modeling</subject><subject>Concurrent computing</subject><subject>Logic</subject><subject>Object recognition</subject><subject>Optimizing compilers</subject><subject>Parallel algorithms</subject><subject>Partitioning algorithms</subject><subject>Pattern matching</subject><subject>Systolic arrays</subject><subject>Terminology</subject><issn>1063-9667</issn><issn>2380-6923</issn><isbn>0818672285</isbn><isbn>9780818672286</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>1996</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj0tLw1AQRgcfYFrduRBX-QOJM_cxd-6yxFeh4EJxW-5NJhqxUpJs_PcW6uY7iwMHPoAbwpoI4926eb-vKUaunUQmOoHCWMGKo7GnsEAh4WCM-DMoCNlWkTlcwGKavhBRPIYCrlflPKqWuzS3n8PPR3nY_SWc9-l70qt_LuH18eGtea42L0_rZrWpBkI3VyEG3xInh4lS1lYzWdey7Ui6TOgD9pGzSMrcC_t0kNSp88ZaTb1dwu2xOqjqdj8OuzT-bo9X7B9jPzke</recordid><startdate>1996</startdate><enddate>1996</enddate><creator>Krishna, V.</creator><creator>Ejnioui, A.</creator><creator>Ranganathan, N.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>1996</creationdate><title>A tree matching chip</title><author>Krishna, V. ; Ejnioui, A. ; Ranganathan, N.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i104t-7975c16a40a1abeceb134c63d18db10570f96b88ab6f865a34c1de45233eaf3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>1996</creationdate><topic>Computational modeling</topic><topic>Concurrent computing</topic><topic>Logic</topic><topic>Object recognition</topic><topic>Optimizing compilers</topic><topic>Parallel algorithms</topic><topic>Partitioning algorithms</topic><topic>Pattern matching</topic><topic>Systolic arrays</topic><topic>Terminology</topic><toplevel>online_resources</toplevel><creatorcontrib>Krishna, V.</creatorcontrib><creatorcontrib>Ejnioui, A.</creatorcontrib><creatorcontrib>Ranganathan, N.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Xplore</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Krishna, V.</au><au>Ejnioui, A.</au><au>Ranganathan, N.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>A tree matching chip</atitle><btitle>Proceedings of 9th International Conference on VLSI Design</btitle><stitle>ICVD</stitle><date>1996</date><risdate>1996</risdate><spage>280</spage><epage>285</epage><pages>280-285</pages><issn>1063-9667</issn><eissn>2380-6923</eissn><isbn>0818672285</isbn><isbn>9780818672286</isbn><abstract>Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Recently, two linear systolic array algorithms have been proposed by the authors. In this paper, we propose an improved approach wherein the the systolic algorithm is based on a linear array of fixed size independent of the problem size and larger strings are partitioned and processed based on the array size. Also, the architecture is simplified by moving the logic for processing variables in each PE to a single PE attached at the end. The systolic algorithm and architecture have been verified through simulation using the Cadence design tools.</abstract><pub>IEEE</pub><doi>10.1109/ICVD.1996.489611</doi><tpages>6</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1063-9667
ispartof Proceedings of 9th International Conference on VLSI Design, 1996, p.280-285
issn 1063-9667
2380-6923
language eng
recordid cdi_ieee_primary_489611
source IEEE Xplore All Conference Series
subjects Computational modeling
Concurrent computing
Logic
Object recognition
Optimizing compilers
Parallel algorithms
Partitioning algorithms
Pattern matching
Systolic arrays
Terminology
title A tree matching chip
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T06%3A33%3A43IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=A%20tree%20matching%20chip&rft.btitle=Proceedings%20of%209th%20International%20Conference%20on%20VLSI%20Design&rft.au=Krishna,%20V.&rft.date=1996&rft.spage=280&rft.epage=285&rft.pages=280-285&rft.issn=1063-9667&rft.eissn=2380-6923&rft.isbn=0818672285&rft.isbn_list=9780818672286&rft_id=info:doi/10.1109/ICVD.1996.489611&rft_dat=%3Cieee_CHZPO%3E489611%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i104t-7975c16a40a1abeceb134c63d18db10570f96b88ab6f865a34c1de45233eaf3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=489611&rfr_iscdi=true