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

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

研究成果: Conference contribution同行評審

1 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Proceedings of the 2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015
發行者Institute of Electrical and Electronics Engineers Inc.
頁面1583-1586
頁數4
ISBN(電子)9783981537048
DOIs
出版狀態Published - 22 4月 2015
事件2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015 - Grenoble, France
持續時間: 9 3月 201513 3月 2015

出版系列

名字Proceedings -Design, Automation and Test in Europe, DATE
2015-April
ISSN(列印)1530-1591

Conference

Conference2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015
國家/地區France
城市Grenoble
期間9/03/1513/03/15

指紋

深入研究「SubHunter: A high-performance and scalable sub-circuit recognition method with Prüfer-encoding」主題。共同形成了獨特的指紋。

引用此