結合Prüfer編碼的高性能及可擴展的子電路辨識方法

Abstract

子電路辨識是一個在給定電路中辨識出子電路的問題，並且在計算機輔助設計流程中的模擬、驗證及測試扮演重要的角色。由於先前的研究將子電路辨識問題轉換成子圖同構(sub-graph isomorphism)問題，因此在現今的電路中表現的不理想。在本研究中，我們提出一個結合Prüfer編碼的高性能及可擴展的子電路辨識方法，命名為子電路獵手(SubHunter)。我們提出了多種技術包含樹狀結構的建立、分群和拆解以及電路圖的編碼，將子電路辨識問題轉換成多個小的子序列比對問題。在序列比對前將可能比對成功的結果過濾出來，接著利用快速的分支定界在給定的電路中找出所有的子電路。實驗結果顯示SubHunter比先前的研究有更好的效能，同時也能找出所有的子電路。在現今電路越來越大的情況下，SubHunter在時間上的成長也趨近線性，這也顯示了此方法的可擴展性。此外不同於先前的研究，SubHunter也能在同一時間辨識多個子電路並且能在更快的時間內完成。

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. Since the SR problem can be formulated as subgraph isomorphism problem, the performance and scalability of previous works thus work poorly in current designs. In this paper we propose a novel high performance and scalable SR algorithm based on Prüfer encoding named SubHunter. 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 problem. A pre-filtering strategy is applied before matching to keep only possible candidates. Thereafter 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 while detecting all the sub-circuits. We can also achieve near linear runtime growth rate comparing to exponential for SubGemini as the circuit size increase and thus shows the scalability of our algorithm. Compare to previous works, SubHunter also has the ability to recognize several sub-circuits at the same time and can further improve performance.