[EDA] SubHunter: A High-Performance and Scalable Sub-Circuit Recognition Method with Prüfer-Encoding

識別子電路 (sub-circuit recognition, 以下簡稱 SR) 問題是給定一個大電路 (MC) 與一個小電路 (SC) ，希望能在 MC 中找出所有跟 SC 相同的部分。

此問題的應用在於可將原始較大的電路中特定功能的電路予以取代，如此可將原始電路的大小縮小，有利於降低後續電路的分析與驗證的複雜度與所需時間。

因此在 SR 問題中效能是非常重要的考量，同時必須確保演算法的擴展性足以應付電路的複雜度與大小皆有爆炸性成長的趨勢。

SR 問題一般可將其轉化為子圖型同構 (subgraph isomorphism，以下簡稱 SI) 問題，轉換方法如下：

1. 將所有的邏輯閘視為節點 (vertex)
2. 將邏輯閘間的連線轉成邊 (edge)

如此一來原本的電路就變成了一個圖 (graph)，令 MCG 以及 SCG 分別為 MC 與 SC 轉換後而得的圖，若 MC 中有某一部分與 SC 相同，則 MCG 中必有一個子圖 (subgraph) 與 SCG 同構 (isomorphic)。

由於 SI 是已知的 NP-Complete 問題之一，因此如何在演算法效能以及結果的正確性上取得平衡是 SR 問題的重要關鍵。

這篇論文提出的是基於圖型理論 (graph theory) 中的 Prüfer 編碼，可將 MCG 以及 SCG 轉換為字串，並將原始的 SI 問題變成較容易處理的字串比對問題。

藉由已知的電路特性我們可以讓字串比對的過程加速，藉此達到可觀的效率改善以及擴展性。實驗結果跟 SubGemini 比較後可以發現有相當大的改善幅度。

不過因為 SubGemini 是 1993 年的論文，而 SR 問題由於沒有公開的 benchmark，通常也不會 open source，因此在與其他研究的比較上就遇上了困難，同時測試電路的可信度也是一大困擾，因此這個研究如果希望可以繼續改善必須要先克服這兩大問題。


這篇論文發表於 2015 DATE：IEEE Xplore 論文連結