考慮障礙物限制下之以效能為導向的繞線樹建構

最小反演幾何樹（Steiner minimal tree）在超大型積體電路電腦輔助設計上是一個非常重要的問題。傳統的最小反演幾何樹是在繞線平面上增加連接點的方式來減少連線的長度。隨著超大型積體電路技術的進步，在建立繞線樹時，許多條件限制必需被考慮進去。舉例來說，已經完成的線路和電源網路都被視為障礙物，而且高速超大型積體電路設計的趨勢也讓以效能為導向的繞線更加普遍。為了應付這種趨勢，我們實作了在以下條件限制下最小反演幾何樹：給定一組接腳和障礙物在一個繞線平面上，我們要建構一個有最小連線長度同時沒有任何接腳和線路和障礙物重疊的反演幾何樹。我們推導了一個移動反演幾何點的演算法來將那些和障礙物重疊的反演幾何點移動到可實行的位置，同時使用了生成圖反演幾何樹演算法來處理考慮障礙物的最小反演幾何樹問題。我們同時加入了限制半徑的最小反演幾何樹演算法來考慮時序條件限制的問題。根據實驗結果，我們能在一個有100 個障礙物的繞線平面上，9 秒內建構一個有5000 個接腳的最小反演幾何樹。考慮障礙物的最小反演幾何樹比未考慮障礙物的反演幾何樹僅僅差了2.1%的總線長。我們也可以在最長路徑延遲和總線長方面做一個取捨。實驗結果可以看出我們的方法是非常有效的。

關鍵字

繞線樹；反演幾何樹；障礙物

並列摘要

The optimization of Steiner minimal trees (SMT’s) is a very important problem in computer-aided design of VLSI circuits. Given a graph, the classical SMT problem is to construct a tree of the graph with the minimal total wirelength to reduce interconnect capacitance, cost of metal wiring, etc. by utilizing any additional vertices in the wiring plane. With the advances of VLSI technology, many constraints for the wiring need to be considered during the tree construction. For example, prerouted nets and a dense power mesh incur significant routing blockages, and the trend of high-speed VLSI designs makes performance-driven routing more popular. To cope with the trends, we work on the constrained SMT problems as follows: Given a set of pins and obstacles in the routing plane, our objective is to construct a Steiner minimal tree with minimal wirelength so that no pins and edges are in the obstacles. We develop a Steiner point moving algorithm to relocate all violated points (the points inside the obstacle) into their best feasible positions and then apply Zhou’s spanning graph based Steiner minimal tree algorithm to handlethe obstacle-aware Steiner minimal tree problem. We also extend the algorithm to consider timing constraints by finding the bounded radius Steiner minimal tree. Experimental results show that we can construct the obstacle-aware Steiner minimal tree (OASMT) with 5000 pins and 100 obstacles within 9 seconds. The OASMT’s average quality is decreased only 2.1% of that obtained by the Steiner minimal tree construction without obstacles consideration. With the longest path constraint, we can make trade-off with total wirelength. The experimental show that our method is very efficient.

並列關鍵字

Routing-tree ； Obstacle ； Steiner tree

參考文獻

[1] S.B.Akers, “A Modification of Lee’s Path Connection Algorithm,” IEEE Trans.

[2] S. Arora, “Polynomial-time approximation schemes for Euclidean tsp and other

[3] M. Borah, R. M Owens, and M. J Irwin, “An edge-based heuristic for steiner routing,”

IEEE Trans. Computer Aided Design, 1994.

[4] Chris S. Coulston, “Constructing Exact Octagonal Steiner Minimal Tree”,Proc. of

國際替代計量

考慮障礙物限制下之以效能為導向的繞線樹建構

全文下載

主題瀏覽