SubHunter: A High-Performance and Scalable Sub-Circuit Recognition Method with Prufer-Encoding
檔案
本條目沒有附加檔案。
日期
2015
類型
系所
期刊名稱
2015 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION (DATE)
卷期與頁次
頁 1583–1586
ISSN
1530-1591
ISBN
978-3-9815-3704-8
語言
英文
摘要
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.
所屬典藏
會議論文引用此條目
Su, H.-Y., Hsu, C.-H., & Li, Y.-L. (2015). SubHunter: A High-Performance and Scalable Sub-Circuit Recognition Method with Prufer-Encoding. 2015 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION (DATE), 1583–1586. https://ir.lib.nycu.edu.tw/handle/11536/134693
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/134693