试误型史坦那树演算法及电子设计自动化的应用Obstacle-Avoiding课件.ppt

1,試誤型史坦那樹演算法及電子設計自動化的應用Obstacle-Avoiding Heuristics for Steiner Tree Problem in EDA,報 告 人：林琮徨指導教授：黃元欣 博士 詹景裕 博士,2,Outline,Introduction Steiner Tree Problem&X ArchitectureHigher Geometry Maze Routers Algorithm(HGMR Algorithm)Lous Steiner Tree AlgorithmLins Steiner Trees(ST)without Obstacles AlgorithmLins 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 Studies,3,Introduction Steiner Tree Problem,Steiner vertex,In Euclidean domain,Given 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.,4,X Architecture,A new interconnect architecture is different 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),5,Steiner Tree Problem on X Architecture,A simple example of Steiner Tree onX architecture,4 Geometry Steiner Minimal Tree,Total Length=7.656,6,Higher Geometry Maze Routers Algorithm,Step 1.Wave Propagation,Step 1.1,Step 1.2,Step 1.3,Step 2.Backtracking,Step 2.1,Step 2.2,Step 2.3,7,Lous Steiner Tree Algorithm,Step1：利用HGMR 演算法求出終端點之間的距離。Step2：利用Prime 的MST演算法，算出連結所有終端點之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)，則演算結束。,8,介紹米字型延伸,(A2),(A1),(A3),(A5),(A4),(A6),9,多點同時進行米字型延伸找出所有可能的Steiner vertex,(B2)點對點,(B1)(點對點),10,Lins Steiner Tree without Obstacles Algorithm,Step1：設定所有終端節點的米字型延伸範圍。Step2：使用座標軸求所有終端節點間最短距離與米字型延伸的重疊點找 所有可能的Steiner vertex Step3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step4：對Map中指定範圍內的米字延伸交叉點Ci,j，進行下列所述：(1)：將此點當作一個終端點，利用MST演算法，算出加入此點後的總樹長。(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)，則演算結束。,11,Lins Steiner Tree without Obstacles Algorithm,建立Improvement Table(IT)。,12,Lins Steiner Tree without Obstacles Algorithm,Improvement Table中，找不到合適的 Steiner vertex(IT值 0)，則演算法結束。,13,Lins ST exist Local Refinement without Obstacles Algorithm,Step1：設定所有終端節點的米字型延伸範圍。Step2：使用座標軸求所有終端節點間最短距離與米字型延伸的重疊點找 所有可能的Steiner vertex Step3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step4：對Map中指定範圍內的米字延伸交叉點Ci,j，進行下列所述：(1)：將此節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此 三點相同值的所有節點，皆以最短路徑相連成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，則放棄此點，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。(3)：若是IT中找不到合適的Steiner vertex(IT值 0)，則演算結束。,14,Local Refinement 示意圖,15,Lins Steiner Tree with Obstacles Algorithm,Step1：利用HGMR演算法求出終端點之間的距離Step2：使用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step3：利用HGMR演算法洪氾求出每個自由節點避開障礙物到達地圖 盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step4：將每個終端點使用米字型延伸後的重疊點找出所有可能的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(IT值 0)，則演算結束。,16,針對地圖最北邊的列座標(0,0)(6,0)之中的所有節點，將上面的所有節點放入HGMR 演算法中的進行洪氾。,wave propagation finish,wave propagation,17,針對地圖最西邊的行座標(0,0)(0,6)與 最北邊的列座標(0,0)(6,0)之中的所有節點，將上面的所有節點放入HGMR演算法中的進行洪氾。,wave propagation finish,wave propagation,18,Lins ST exist Local Refinement with Obstacles Algorithm,Step1：利用HGMR演算法洪氾求出每個自由節點避開障礙物到達地圖 盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step2：將每個終端點使用米字型延伸後的重疊點找出所有可能的Steiner vertex，直到整個地圖做完為止。Step3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。Step4：對Map中的米字延伸交叉點Ci,j，進行Local Refinement：(1)：將此節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此 三點相同值的所有節點，皆以最短路徑相連成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，則放棄此點，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。(3)：若是IT中找不到合適的Steiner vertex(IT值 0)，則演算結束。,19,HGMR、Lous、Lins Algorithm Length Example Compare,Result of Lous(Length=13.8),Result of HGMR(Length=14.6),Result of Lins(Length=13.8),20,Result of HGMR(Length=35.384),Result of Lous(Length=34.142),Result of Lins(Length=34.142),HGMR、Lous、Lins Algorithm Length Example Compare,21,Algorithm Compare Table,Lous SMT Algorithm,O(N2+p3N),O(N2),Jans SMT Algorithm,O(p2N),O(pN),Lins SMT without Obstacles Algorithm,O(p4),Algorithms,Items,Time Complexity,Space Complexity,O(pN+N+p4),O(pN),O(pN),O(N+p2),O(p2),p:#of terminal vertices,N:#of free space,Lins SMT without Obstacles Algorithm exist Local refinement,Lins SMT with Obstacles Algorithm,Lins SMT without Obstacles Algorithm exist Local refinement,O(pN),O(pN),22,Conclusions,Lin的演算法之所以優於Lou，主要是在於Lou的演算法在 找尋Steiner vertex上花費過多的時間 去測試自由空間 上的每一個節點，Lin的演算法收尋Steiner Point僅在特定 縮小範圍內測試少許的米字延伸交叉點，花費較少的時間，在無障礙物空間下只需要，有障礙物也只需要 Lin的演算法存在Local refinement 之下，有效的降低 次方的時間，使得演算法更迅速的建立史坦那樹，不需每 次都使用Prims MST去重建所要測試的Steiner vertex與Z節 點。,O(p3N),O(p2),O(N+p2),O(p),23,Future Studies,Verify our results of algorithmsTo analyze 3D 26-Directional Steiner Tree AlgorithmCombine Steiner tree and single layer routing Algorithm.,