Abstract
由於積體電路技巧的突飛猛進，已由 SSI時代，進而發展到 MSI時代，目前已然進入VLSI之紀元。而今一個小小的IC，往往包含了數萬個電晶體，於是乎複雜且高密度的IC設計，已然成為一股不可抗拒的主流。於Uehara及vanCleemput 所提出的Layout Style中，所有的電晶體被擺成並行的兩列，其中一列為P-type的電晶體，而另一列為N-type的電晶體，且其Power Rails 被擺在Cell的最上方及最下方。就高密度的觀點而言，因為Standard Cell 的高度是固定的，所以我們欲減少整個Cell的面積，只有從其寬度著手了！換言之，我們要減少C-ell 裡面Seperation的個數，亦即希望找到最少量的Chain 去涵蓋整個 Schematic。Uehara及vanCleemput 首先對這個問題提出了解法。他們將一個Shematic轉換成兩個Subgraph：及N-side Graph。其中P-side Graph是由Schematic 中的P-type之電晶體所構成；相對地，Schematic 中的N-type之電晶體則組成了N-side Graph。其 Graph造法如下：(1) 每一電晶體中的Source/Drain代表Graph 中的Vertex。(2) 每一電晶體代表Graph 中的Edge，連接著其Source及 Drain。待 Graph建立後，分別在P-side Graph及N-side Graph找尋相對的Euler Path，希望能夠儘量用最少數目的Euler Path來涵蓋兩個Subgrpah，以達到減化Seperation數目的目的，進而減少一個Cell所需之面積。而後有不少人以這樣的Grpah Model 為基礎，提出了各種不同的解決方法，甚至有人將Delay Binding 之技巧應用於此問題上，以期得到更佳的結果。有鑑於此，我們提出另外一種 Graph Model-Bipartite Graph，並發展出一個 Deph-First-Search的演算法，且找到Lower Bound On The No.Of Chains 以期儘速加快演算法之速度，我們的演算法可分成如下兩個步驟：1.Pairing2.Chainaing於Pairing 的處理過程中，將一個P-type電晶體及一個N-type電晶體配成一對，而後再利用此Pairing 之結果建立 Bipartite Graph。Bipartite Graph 中的每一個Edge即代表一個Possibe Abutment，而Chainging 之目的在於Bipartite Graph 中，找到一個為數最多的 Mutually Compatible Edges Set，亦即找到最多的Abutment，換言之Cell的Seperation會是最少。於Depth-First-Search的演算法中，我們亦發現每個Node所需Expand的Edge，並非全部而是只要一個Edge及其Mutually Exclusive Edges即可，若能從 Compatible Edge之數目最多的Edge著手，再加上所找到的 Lower Bound，會使得此演算法儘快地收斂，而找到最佳解。