標題: SubHunter: A High-Performance and Scalable Sub-Circuit Recognition Method with Prufer-Encoding
作者: Su, Hong-Yan
Hsu, Chih-Hao
Li, Yih-Lang
資訊工程學系
Department of Computer Science
關鍵字: Sub-circuit recognition;graph isomorphism;Prufer encoding
公開日期: 2015
摘要: 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 Prufer-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.
URI: http://hdl.handle.net/11536/134693
ISBN: 978-3-9815-3704-8
ISSN: 1530-1591
期刊: 2015 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION (DATE)
起始頁: 1583
結束頁: 1586
Appears in Collections:Conferences Paper