试误型史坦那树演算法及.ppt课件

1、試誤型史坦那樹演算法及電子設計自動化的應用Obstacle-Avoiding Heuristics for Steiner Tree Problem in EDA報 告 人：林琮徨指導教授：黃元欣 博士 詹景裕 博士 1OutlineIntroduction Steiner Tree Problem & X ArchitectureHigher Geometry Maze Routers Algorithm (HGMR Algorithm)Lous Steiner Tree AlgorithmLins Steiner Trees(ST) without Obstacles AlgorithmL

2、ins Steiner Trees exist Local refinement without Obstacles AlgorithmLins Steiner Trees with Obstacles AlgorithmLins Steiner Trees exist Local refinement with Obstacles AlgorithmThe Proposed Algorithm Example CompareThe Proposed Algorithm Compare TableConclusionsFuture Studies2Introduction Steiner Tr

3、ee ProblemSteiner vertexvertices to be interconnectedIn Euclidean domainGiven a set of n vertices on the plane, the Steiner Minimum Tree problem is to find a tree in the plane, of minimum total wire length, which connects the given set of vertices.3X ArchitectureA new interconnect architecture is di

4、fferent from “Manhattan” architecture.X Architecture rotates the primary direction of the interconnect in the fourth and fifth metal layers by 45 degrees.The advantages are discounting 20% routing wires and 30% via in VLSI layout. (Org: x initiative)4Steiner Tree Problem on X ArchitectureA simple ex

5、ample of Steiner Tree onX architecture4 Geometry Steiner Minimal Tree, Total Length = 7.656 5Higher Geometry Maze Routers AlgorithmStep 1. Wave Propagation Step 1.1Step 1.2Step 1.3Step 2. BacktrackingStep 2.1Step 2.2Step 2.36Lous Steiner Tree AlgorithmStep1：利用HGMR 演算法求出終端點之間的距離。Step2：利用Prime 的MST演算法

6、，算出連結所有終端點之MST樹長。Step3：對Map中每一點自由空間Ci,j，進行下列所述：(1) ： 將此點當作一個終端點，利用MST演算法，算出加入此點後的總樹長。(2) ： 將原本的樹長減去之後算出的樹長，紀錄在Ci,j中。Step4：Iteration * Define T : Tree 中的每個點的集合。(1) ：建立Improvement Table (IT)。(2) ：找尋IT中最適合的Steiner vertex，將其加入T後，執行Step2Step4.。(3) ：若是IT中找不到合適的Steiner vertex (IT值 0) ，則演算結束。7介紹米字型延伸(A2)(A1

7、)(A3)(A5)(A4)(A6)8多點同時進行米字型延伸找出所有可能的Steiner vertex(B2) 點對點(B1) (點對點)9Lins Steiner Tree without Obstacles AlgorithmStep1：設定所有終端節點的米字型延伸範圍。 Step2：使用座標軸求所有終端節點間最短距離與米字型延伸的重疊點找 所有可能的Steiner vertex Step3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step4：對Map中指定範圍內的米字延伸交叉點Ci,j，進行下列所述：(1)： 將此點當作一個終端點，利用MST演算法，算出加入此點後的

8、總樹長。(2)： 將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。Step5：Iteration * Define T : Tree 中的每個點的集合。(1) ：建立Improvement Table (IT)。(2) ：找尋IT中最適合的Steiner vertex，將其加入T後，執行Step4。(3) ：若是IT中找不到合適的Steiner vertex(IT值 0) ，則演算結束。 10Lins Steiner Tree without Obstacles Algorithm建立Improvement Table (IT)。11Lins Steiner Tree witho

9、ut Obstacles Algorithm Improvement Table中，找不到合適的 Steiner vertex (IT值 0) ，則演算法結束。 12Lins ST exist Local Refinement without Obstacles AlgorithmStep1：設定所有終端節點的米字型延伸範圍。 Step2：使用座標軸求所有終端節點間最短距離與米字型延伸的重疊點找 所有可能的Steiner vertex Step3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step4：對Map中指定範圍內的米字延伸交叉點Ci,j，進行下列所述：(1)：將此

10、節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此 三點相同值的所有節點，皆以最短路徑相連成tree。(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。(3)：將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。Step5： * Define T : Tree 中的每個點的集合。(1) ：建立Improvement Table (IT)。Iteration(2) ：找尋IT中數值最大Steiner vertex Ci,j (IT值 0)，暫將其加入T，用原本的樹長 減去之後算出的樹長，結果大於0則修改T，刪除IT中的此Ci,j 。結果小於等於0

11、 ，則放棄此點，並且從IT中刪除Ci,j ，直到IT中為正的值都測試完為止。 (3) ：若是IT中找不到合適的Steiner vertex(IT值 0) ，則演算結束。 13Local Refinement 示意圖14Lins Steiner Tree with Obstacles AlgorithmStep1：利用HGMR演算法求出終端點之間的距離Step2：使用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step3：利用HGMR演算法洪氾求出每個自由節點避開障礙物到達地圖 盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step4：將每個終端點使用米字型延伸後的重

12、疊點找出所有可能的Steiner vertex，直到整個地圖做完為止。Step5：對Map中的米字延伸交叉點Ci,j，進行下列所述：(1)： 將此點當作一個終端點，利用Prime MST演算法，算出加入此點後的總樹長。(2)： 將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。Step6：Iteration * Define T : Tree 中的每個點的集合。(1) ：建立Improvement Table (IT)。(2) ：找尋IT中最適合的Steiner vertex，將其加入T後，執行演算法中的Step5 。(3) ：若是IT中找不到合適的Steiner vertex(I

13、T值 0) ，則演算結束。 15針對地圖最北邊的列座標(0,0)(6,0)之中的所有節點，將上面的所有節點放入HGMR 演算法中的進行洪氾。wave propagation finishwave propagation16針對地圖最西邊的行座標(0,0) (0,6)與 最北邊的列座標(0,0)(6,0) 之中的所有節點，將上面的所有節點放入HGMR演算法中的進行洪氾。wave propagation finishwave propagation17Lins ST exist Local Refinement with Obstacles AlgorithmStep1：利用HGMR演算法洪氾求出

14、每個自由節點避開障礙物到達地圖 盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step2：將每個終端點使用米字型延伸後的重疊點找出所有可能的Steiner vertex，直到整個地圖做完為止。Step3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step4：對Map中的米字延伸交叉點Ci,j ，進行Local Refinement：(1)：將此節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此 三點相同值的所有節點，皆以最短路徑相連成tree。(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。(3)：將原本的MST樹長減

15、去之後算出的MST樹長，紀錄在Ci,j中。Step5： * Define T : Tree 中的每個點的集合。(1) ：建立Improvement Table (IT)。Iteration(2) ：找尋IT中數值最大Steiner vertex Ci,j (IT值 0)，暫將其加入T，用原本的樹長 減去之後算出的樹長，結果大於0則修改T，刪除IT中的此Ci,j 。結果小於等於0 ，則放棄此點，並且從IT中刪除Ci,j ，直到IT中為正的值都測試完為止。 (3) ：若是IT中找不到合適的Steiner vertex(IT值 0) ，則演算結束。 18HGMR、Lous、Lins Algorith

16、m Length Example CompareResult of Lous(Length = 13.8)Result of HGMR(Length = 14.6)Result of Lins(Length = 13.8)19Result of HGMR(Length = 35.384)Result of Lous (Length = 34.142)Result of Lins(Length = 34.142)HGMR、Lous、Lins Algorithm Length Example Compare20Algorithm Compare TableLous SMT AlgorithmO(N

17、2 +p3N)O(N2)Jans SMT AlgorithmO(p2N)O(pN)Lins SMT without Obstacles AlgorithmO(p4)AlgorithmsItemsTime ComplexitySpace ComplexityO(pN+N+p4)O(pN)O(pN)O(N+p2)O(p2)p: # of terminal vertices, N: # of free spaceLins SMT without Obstacles Algorithm exist Local refinement Lins SMT with Obstacles AlgorithmLins SMT without Obstacles Algorithm exist Local refinement O(pN)O(pN)21ConclusionsLin的演算法之所以優於Lou，主要是在於Lou的演算法在 找尋Steiner vertex上花費過多的時間 去測試自由空間 上的每一個節點，Lin的演算法收尋Steiner Point僅在特定 縮小範圍內測試少許的米字延伸交叉點，花費較少的時間， 在無障礙物空間下只需要 ，有障礙物也只需要 Lin的