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
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;
Conference_Titel :
Design, Automation & Test in Europe Conference & Exhibition (DATE), 2015
Conference_Location :
Grenoble
Print_ISBN :
978-3-9815-3704-8