Abstract
論 文 摘 要 傳統的電路切割方法(circuit partitioning)中，其所使用的基本運算(elementary operation)是將分屬於不同分割區域的兩個邏輯單元(logic cell)的位置做對調或者是搬移其中某一個邏輯單元的位置到其他區域中，以達到降低不同分割區域間的連結線路(interconnection)數目的目的。然而這樣的方式有一個很大的缺點，那就是容易陷入局部最佳解(local optimal)之中而無法得到更佳的分割。在這篇論文中，我們提出了一個新的漸進式電路切割改良法(iterative refinementtechnique)。我們所提出的這個漸進式電路切割改良法是應用配對(matching)的方法來達到改善切割效果的目的。不同於傳統的方式一次只能搬移一個或兩個邏輯單元的位置，我們所提出的方法一次能夠搬移數百個、甚至數千個彼此互相獨立之邏輯單元(independent cells)的分割位置，使得這數百千個邏輯單元的位置在一次搬移中得到最佳的分割區域分佈。而所謂的互相獨立的邏輯單元所指的是彼此沒有線路(net)互相連接的那些邏輯單元。依照這個方法我們發展出了一套軟體系統並對於一系列的電路做測試。實驗結果顯示我們所提出的這個方法的確能有效的降低電路切割的成本。