電晶體層級電路描述之邏輯粹取

Abstract

在電腦輔助電路設計的領域中，如何在一個大型電路中尋找某附屬電路的問題是被廣泛研究的。現今這些問題都是以圖形辨識的方法解決，但這些方法都沒有利用到任何電路的特性，也很有可能會在圖形的轉換過程中喪失了電路的拓撲結構(topological structure)，而導致無法辨識出某些特定的電路，像是輸入點短路的邏輯閘。如果整個電路都需要以較高階的模組表示，這些方法更需要多次的執行才能粹取出每一種邏輯電路。我們利用通道圖分割(channel graph partition)以及電路編碼理論(circuit encoding algorithm)，提出了一種邏輯粹取的方法，只要處理過一次電路，不需任何的前置作業，就可以把整個電路描述由電晶體層級提升到邏輯層級。以標準元件庫(standard cell library)中的基本邏輯閘為範本電路(pattern circuit)的來源，以及離線處理已知的範本電路辨識資訊，更加提升了整個方法的效能及可再利用性。包含組合電路以及循序電路的實驗結果可以證明這個方法在執行時間以及記憶體需求上都與電路大小有近似線性的關係。

The problem of finding subcircuits in a larger circuit arises in many contexts in computer-aided design. This is a problem currently solved by using various heuristics purely based on graph isomorphism. Such techniques, however, cannot utilize any circuit properties and usually lost the topological circuit structure, which led to failure in some cases such as shorting-input circuits. If the whole circuit needs to be represented in higher level models, it even takes numerous runs to extract every kind of subcircuits by these techniques. We present a logic extraction approach based on channel graph partition and modified circuit encoding algorithm. Without any pre-processing, it needs to traverse the input circuit only once, and converts the entire circuit netlist from transistor level to gate level. The reusability and efficiency are further achieved by using the elemental logic gates in standard cell library as the source of pattern circuits, and preparing the priori known pattern circuit information for identification off-line. The experiments on several real circuits containing sequential and combination logics show the near-linear performance in run time and memory usage.