资源描述
*,*,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,試誤型史坦那樹演算法及電子設計自動化的應用,Obstacle-Avoiding Heuristics for Steiner Tree Problem in EDA,報 告 人：林琮徨,指導教授：黃元欣 博士,詹景裕 博士,1,Outline,Introduction Steiner Tree Problem & X Architecture,Higher Geometry Maze Routers Algorithm (HGMR Algorithm),Lous Steiner Tree Algorithm,Lins Steiner Trees(ST) without Obstacles Algorithm,Lins Steiner Trees exist Local refinement without Obstacles Algorithm,Lins Steiner Trees with Obstacles Algorithm,Lins Steiner Trees exist Local refinement with Obstacles Algorithm,The Proposed Algorithm Example Compare,The Proposed Algorithm Compare Table,Conclusions,Future Studies,2,Introduction,Steiner Tree Problem,Steiner vertex,vertices to be interconnected,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.,3,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),4,Steiner Tree Problem on X Architecture,A simple example of Steiner Tree onX architecture,4 Geometry Steiner Minimal Tree, Total Length = 7.656,5,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,6,Lous Steiner Tree Algorithm,Step1：,利用,HGMR,演算法求出終端點之間的距離。,Step2：,利用,Prime,的,MST,演算法，算出連結所有終端點之,MST,樹長。,Step3：,對,Map,中,每一點自由空間,C,i,j,，,進行下列所述：,(1) ：,將此點當作一個終端點，利用,MST,演算法，算出加入此點後的總樹長。,(2) ： 將原本的樹長減去之後算出的樹長，紀錄在,C,i,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),(A3),(,A5),(,A4),(A6),8,多點同時進行米字型延伸找出所有可能的,Steiner vertex,(,B2),點對點,(,B1),(點對點),9,Lins Steiner Tree without,Obstacles,Algorithm,Step1：,設定所有終端節點的米字型延伸範圍。,Step2：,使用座標軸,求所有終端節點間最短距離與米字型延伸的重疊點找,所有可能的,Steiner vertex,Step3：,利用,Prime,的,MST,演算法，算出連結所有終端點之,MST,樹長。,Step4：,對,Map,中,指定範圍,內,的米字延伸交叉點,C,i,j,，,進行下列所述：,(1)：,將此點當作一個終端點，利用,MST,演算法，算出加入此點後的總樹長。,(2)： 將原本的,MST,樹長減去之後算出的,MST,樹長，紀錄在,C,i,j,中。,Step5：Iteration,*,Define,T : Tree,中的每個點的集合。,(1) ：,建立,Improvement Table (IT)。,(2) ：,找尋,IT,中最適合的,Steiner vertex，,將其加入,T,後，執行,Step4。,(3) ：,若是,IT,中找不到合適的,Steiner vertex(IT,值 0) ，則演算結束。,10,Lins Steiner Tree without,Obstacles,Algorithm,建立,Improvement Table (IT)。,11,Lins Steiner Tree without,Obstacles,Algorithm,Improvement Table,中，找不到合適的,Steiner vertex (IT,值 0),，則演算法結束。,12,Lins ST exist Local Refinement without,Obstacles,Algorithm,Step1：,設定所有終端節點的米字型延伸範圍。,Step2：,使用座標軸,求所有終端節點間最短距離與米字型延伸的重疊點找,所有可能的,Steiner vertex,Step3：,利用,Prime,的,MST,演算法，算出連結所有終端點之,MST,樹長。,Step4：,對,Map,中,指定範圍,內,的米字延伸交叉點,C,i,j,，,進行下列所述：,(1)：,將此節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此,三點相同值的所有節點，皆以最短路徑相連成,tree。,(2)：將此,tree,加入目前的,MST，,刪除迴圈中最長的邊長，儲存修改此,MST,。,(3)：將原本的,MST,樹長減去之後算出的,MST,樹長，紀錄在,C,i,j,中。,Step5：,*,Define,T : Tree,中的每個點的集合。,(1) ：,建立,Improvement Table (IT)。,Iteration,(2) ：找尋,IT,中數值最大,Steiner vertex,C,i,j,(IT,值 0)，暫將其加入,T，,用原本的樹長,減去之後算出的樹長，結果大於0則修改,T，,刪除,IT,中的此,C,i,j,。,結果小於等於0,，則放棄此點，並且從,IT,中刪除,C,i,j,，直到,IT,中為正的值都測試完為止。,(3) ：若是,IT,中找不到合適的,Steiner vertex(IT,值 0) ，則演算結束。,13,Local Refinement,示意圖,14,Lins Steiner Tree with,Obstacles,Algorithm,Step1：,利用,HGMR,演算法求出終端點之間的距離,Step2：,使用,Prime,的,MST,演算法，算出連結所有終端點之,MST,樹長。,Step3：,利用,HGMR,演算法洪氾求出每個自由節點避開障礙物到達地圖,盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。,Step4：,將每個終端點使用,米字型延伸後的重疊點找出所有可能的,Steiner,vertex,，直到整個地圖做完為止。,Step5：,對,Map,中的米字延伸交叉點,C,i,j,，,進行下列所述：,(1)：,將此點當作一個終端點，利用,Prime MST,演算法，算出加入此點後的總樹長。,(2)： 將原本的,MST,樹長減去之後算出的,MST,樹長，紀錄在,C,i,j,中。,Step6：Iteration,* Define,T : Tree,中的每個點的集合。,(1) ：,建立,Improvement Table (IT)。,(2) ：,找尋,IT,中最適合的,Steiner vertex，,將其加入,T,後，執行演算法中的,Step5 。,(3) ：,若是,IT,中找不到合適的,Steiner vertex(IT,值 0) ，則演算結束。,15,針對地圖最北邊的列座標(0,0)(,6,0,),之中的所有節點，,將上面的所有節點放入,HGMR,演算法中的進行洪氾。,wave propagation finish,wave propagation,16,針對地圖最西邊的行座標(0,0) (0,6,),與,最北邊的列座標(0,0)(,6,0),之中的所有節點，,將上面的所有節點放入,HGMR,演算法中的進行洪氾。,wave propagation finish,wave propagation,17,Lins ST exist Local Refinement with,Obstacles,Algorithm,Step1：,利用,HGMR,演算法洪氾求出每個自由節點避開障礙物到達地圖,盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。,Step2：,將每個終端點使用,米字型延伸後的重疊點找出所有可能的,Steiner,vertex,，直到整個地圖做完為止。,Step3：,利用,Prime,的,MST,演算法，算出連結所有終端點之,MST,樹長。,Step4：,對,Map,中的米字延伸交叉點,C,i,j,，,進行,Local Refinement,：,(1)：,將此節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此,三點相同值的所有節點，皆以最短路徑相連成,tree。,(2)：將此,tree,加入目前的,MST，,刪除迴圈中最長的邊長，儲存修改此,MST,。,(3)：將原本的,MST,樹長減去之後算出的,MST,樹長，紀錄在,C,i,j,中。,Step5：,*,Define,T : Tree,中的每個點的集合。,(1) ：,建立,Improvement Table (IT)。,Iteration,(2) ：找尋,IT,中數值最大,Steiner vertex,C,i,j,(IT,值 0)，暫將其加入,T，,用原本的樹長,減去之後算出的樹長，結果大於0則修改,T，,刪除,IT,中的此,C,i,j,。,結果小於等於0,，則放棄此點，並且從,IT,中刪除,C,i,j,，直到,IT,中為正的值都測試完為止。,(3) ：若是,IT,中找不到合適的,Steiner vertex(IT,值 0) ，則演算結束。,18,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,),19,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,20,Algorithm Compare Table,Lous SMT Algorithm,O,(,N,2,+,p,3,N,),O,(,N,2,),Jans SMT Algorithm,O,(,p,2,N,),O,(,pN,),Lins SMT without Obstacles Algorithm,O,(,p,4,),Algorithms,Items,Time,Complexity,Space,Complexity,O,(,pN,+N,+,p,4,),O,(,pN,),O,(,pN,),O,(,N+p,2,),O,(,p,2,),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,),21,Conclusions,Lin,的演算法之所以優於,Lou，,主要是在於,Lou,的演算法在,找尋,Steiner vertex,上花費,過多,的時間 去測試自由空間,上的,每一個節點,，Lin,的演算法收尋,Steiner Point,僅在特定,縮小範圍內,測試少許的米字延伸交叉點,，花費較少的時間，,在無障礙物空間下只需要,，,有障礙物也只需要,Lin,的演算法存在,Local refinement,之下，有效的降低,次方的時間，使得演算法更迅速的建立史坦那樹,，,不需每,次都使用,Prims,MST,去重建所要測試的,Steiner vertex,與,Z,節,點。,O(p,3,N,),O,(,p,2,),O(N+p,2,),O,(,p,),22,Future Studies,Verify our results of algorithms,To analyze 3D 26-Directional Steiner Tree Algorithm,Combine Steiner tree and single layer routing Algorithm.,23,
展开阅读全文