Abstract
佈局合成 (Layout Synthesis) 是本篇論文所要探討的主題，而任意邏輯(RandomLogic)之佈局則是主要研究的對象，其包含了演算法、佈局型態(Layout Style)及兩個佈局系統。二個系統中，一為Theda.P ，是針對基本元件(Leaf Cell) 而設計的，另一個為Theda.M ，則是針對任意邏輯模組(Random Logic Module) 而開發的。佈局合成所要解決的相關問題中，電晶體串連(Transistor Chaining) 是一個最基本的問題。相鄰的電晶體串連的愈多，不但使繞線(Routing) 問題簡化，也可以使佈局面積變小。針對此問題，我們發展出一個最佳化的電晶體串連演算法，其基本精神源自圖學理論(Graph Theory)的應用，概言之，我們利用Bipartite Graph 來表示此問題，並利用Depth-First Search來找尋最大的一組Compatible Edges。再者，為了縮短找尋的時間，我們推導出一個理論下限(Theoretical Lower Bound)，用以刪除重複或者非最佳的解。Theda.P 是一個基本元件自動佈局系統。我們設計了一個新的佈局型態，其主要動機是為了善用第二層金屬線(Second Metal)於基本元件的佈局中。由於製程技術不斷的推陳進步，已有多層金屬線(Multi-Metal) 可用於佈局中；但大部份佈局的相關研究，乃至於佈局工程師(Layout Engineer) 都一直採用Uehara及van Cleemput於1981年所發表的佈局型態或其變型。在此傳統型態的應用下，非但局限了第二層金屬線於基本元件佈局中的使用，亦使得佈局自動化一直無法達到實用的階段。Theda.P 以新的佈局型態為骨幹，採用上述的最佳電晶體串連演算法，解決電晶體排列(Placement) 問題，Left Edge Algorithm 則用來完成細部繞線 (DetailedRouting)的部份。由實驗結果，Theda.P 所產生的佈局面積約為傳統型態的百分之八十。Theda.P 可為含有數十個電晶體的基本元件自動產生佈局，而Theda.M 則為含有數百至數千電晶體的任意邏輯模組產生佈局。因為一個任意邏輯模組含有電晶體的數目已至千百，所以Theda.M 所產生的佈局不再是單一列，而是多列的(Multi-Row)；也因此，佈局的困難度倍增，以致Theda.P 中所採用的演算法已不再適用。Theda.M 的佈局型態是Theda.P 中的衍生。至於演算法方面，我們希望在電晶體排列時，能夠同時考慮繞線密度(Wiring Density)及電晶體串連(Transistor Abutm-ent)。繞線密度影響到一個佈局的高度，而電晶體串連數目則與佈局的寬度有關；因此唯有兩者同時考量，方能產生最佳的佈局。動態串連 (Dynamic Chaining) 採用參數控制的技巧，將以上兩個因素同時列入評估。繞線方面，我們將所有的連線(Net) 分成兩類：局部的 (Local) 及整體的 (Global)。利用這樣的分類得以解決Feedthrough 的問題，且簡化了局部連線的繞線問題。於細部繞線時，我們先將部份的局部連線用以填滿繞線區域(Channel) 中凹凸不平處，而後將剩下的連線交由Greedy Router 去完成所有的連接。由實驗結果，Theda.M 所產生的佈局較以標準元件(Standard Cell) 的方式所產生的佈局為佳。