DocumentCode :
704092
Title :
SubHunter: A high-performance and scalable sub-circuit recognition method with Prüfer-encoding
Author :
Hong-Yan Su ; Chih-Hao Hsu ; Yih-Lang Li
Author_Institution :
Inst. of Comput. Sci. & Eng., Nat. Chiao Tung Univ., Hsinchu, Taiwan
fYear :
2015
fDate :
9-13 March 2015
Firstpage :
1583
Lastpage :
1586
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.
Keywords :
CAD; encoding; graph theory; integrated circuit design; isomorphism; network synthesis; Prüfer-encoding; SubGemini; SubHunter; circuit graph encoding; computer-aided design; prefiltering strategy; subcircuit matching; subcircuit recognition method; subgraph isomorphism problem; subsequence matching problems; tree cutting; tree structure partition; Algorithm design and analysis; Cascading style sheets; Encoding; Partitioning algorithms; Random access memory; Runtime; Vegetation; Prüfer encoding; Sub-circuit recognition; graph isomorphism;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design, Automation & Test in Europe Conference & Exhibition (DATE), 2015
Conference_Location :
Grenoble
Print_ISBN :
978-3-9815-3704-8
Type :
conf
Filename :
7092644
Link To Document :
بازگشت