SubHunter: A high-performance and scalable sub-circuit recognition method with Prüfer-encoding

Hong Yan Su, Chih Hao Hsu, Yih-Lang Li

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Sub-circuit recognition (SR) is a problem of recognizing sub-circuits within a given circuit and is a fundamental component in simulation, verification and testing of computer-aided design. The SR problem can be formulated as subgraph isomorphism problem. Performance of previous works is not scalable as the complexities of modern designs increase. In this paper we propose a novel Prüfer-encoding based SR algorithm that performs scalable and high-performance sub-circuit matching. Several techniques including tree structure partition, tree cutting and circuit graph encoding are proposed herein to decompose the SR problem into several small sub-sequence matching problems. A pre-filtering strategy is applied before matching to remove the sub-circuits that are not likely to be matched. A fast branch and bound approach is developed to identify all the sub-circuits within the given circuit. Experimental results show that SubHunter can achieve better performance than SubGemini and detect all the sub-circuits as well. As the circuit size increases, we can also achieve near linear runtime growth that outperforms the exponential growth for SubGemini, showing the scalability of the proposed algorithm.

Original languageEnglish
Title of host publicationProceedings of the 2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1583-1586
Number of pages4
ISBN (Electronic)9783981537048
DOIs
StatePublished - 22 Apr 2015
Event2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015 - Grenoble, France
Duration: 9 Mar 201513 Mar 2015

Publication series

NameProceedings -Design, Automation and Test in Europe, DATE
Volume2015-April
ISSN (Print)1530-1591

Conference

Conference2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015
CountryFrance
CityGrenoble
Period9/03/1513/03/15

Keywords

  • graph isomorphism
  • Prüfer encoding
  • Sub-circuit recognition

Fingerprint Dive into the research topics of 'SubHunter: A high-performance and scalable sub-circuit recognition method with Prüfer-encoding'. Together they form a unique fingerprint.

Cite this