使用規則導向且考慮障礙物之多層直角史坦納樹的建造

Abstract

隨著超大型積體電路設計的大小增加，繞線的問題也越來越重要。繞線樹建立在繞線器的運作中對於最後的繞線結果影響尤其重大。在我們的論文當中，我們提出了一個單/多層考慮障礙物之直角史坦納樹的建造有效且可以快速的建立多層繞線的方法。 我們介紹了一個最小化總繞線長度的方法，可以稱之為共用邊。在同樣的拓墣結構中，這個方法比只有考慮Ｕ型修正來最小化總繞線長度好[20]。 在多層繞線部分，我們提出一個多層級近似的方法來處理這個問題，比起一次考慮整個問題的方法，可以大量的縮短運算時間。實驗數據顯示，當測試檔的大小增大時，我們的方法依然有很好的效能。

In very/ultra large scale design (VLSI/ULSI), routing is a very challenging work. Especially, the routing tree construction, as an extremely important step for routers, plays a crucial role for the routing results. In this thesis, we have proposed an algorithm to construct a single/multi-layer obstacle-avoiding rectilinear Steiner tree, which can get good solution at single layer and fast yet effective at multi layers. We use a concept called co-edge to minimize the total wirelength. It is better than just considering the U-Shaped refinement [20] under the same topology. In multi-layer, we proposed a hierarchical and heuristic approach to solve this problem. Experimental results have shown that our algorithm is still efficient in larger multi-layer cases, with slightly more wirelength.