1、1試誤型史坦那樹演算法及試誤型史坦那樹演算法及電子設計自動化的應用電子設計自動化的應用Obstacle-Avoiding Heuristics for Steiner Tree Problem in EDA報 告 人：林琮徨指導教授：黃元欣 博士 詹景裕 博士 2OutlinenIntroduction Steiner Tree Problem&X ArchitecturenHigher Geometry Maze Routers Algorithm(HGMR Algorithm)nLous Steiner Tree AlgorithmnLins Steiner Trees(ST)withou
2、t Obstacles AlgorithmnLins Steiner Trees exist Local refinement without Obstacles AlgorithmnLins Steiner Trees with Obstacles AlgorithmnLins Steiner Trees exist Local refinement with Obstacles AlgorithmnThe Proposed Algorithm Example ComparenThe Proposed Algorithm Compare TablenConclusionsnFuture St
3、udies3Introduction Steiner Tree ProblemSteiner vertexvertices to be interconnectedIn Euclidean domainnGiven 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.4X ArchitecturenA new int
4、erconnect architecture is different from“Manhattan”architecture.nX Architecture rotates the primary direction of the interconnect in the fourth and fifth metal layers by 45 degrees.nThe advantages are discounting 20%routing wires and 30%via in VLSI layout.(Org:x initiative)5Steiner Tree Problem on X
5、 ArchitectureA simple example of Steiner Tree onX architecture4 Geometry Steiner Minimal Tree,Total Length=7.656 St ei ner St ei ner Vert exVert ex6Higher Geometry Maze Routers AlgorithmnStep 1.Wave Propagation Step 1.1Step 1.2Step 1.3nStep 2.BacktrackingStep 2.1Step 2.2Step 2.37Lous Steiner Tree Al
6、gorithmnStep1：利用HGMR 演算法求出終端點之間的距離。nStep2：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。nStep3：對Map中每一點自由空間Ci,j，進行下列所述：n(1)：將此點當作一個終端點，利用MST演算法，算出加入此點後的總樹長。n(2)：將原本的樹長減去之後算出的樹長，紀錄在Ci,j中。nStep4：Iteration *Define T:Tree 中的每個點的集合。n(1)：建立Improvement Table(IT)。n(2)：找尋IT中最適合的Steiner vertex，將其加入T後，執行Step2Step4.。n(3)：若是I
7、T中找不到合適的Steiner vertex(IT值 0)，則演算結束。8介紹米字型延伸(A2)(A1)(A3)(A5)(A4)(A6)1.01.01.01.01.01.01.01.01.41.41.41.41.41.41.41.42.82.82.82.82.82.82.02.02.02.02.02.02.02.0S S2.82.84.24.23.03.04.24.24.24.24.24.23.03.03.03.03.03.01.01.01.01.01.01.01.01.01.41.41.41.41.41.41.41.4S S1.01.01.01.01.01.01.01.01.41.41.41
8、.41.41.41.41.4S S1.01.01.01.01.01.01.01.01.41.41.41.41.41.41.41.42.82.82.82.82.82.82.82.82.02.02.02.02.02.02.02.0S S1.01.01.01.01.01.01.01.01.41.41.41.41.41.41.41.42.82.82.82.82.82.82.02.02.02.02.02.02.02.0S S2.82.81.01.01.01.01.01.01.01.01.41.41.41.41.41.41.41.42.82.82.82.82.82.82.02.02.02.02.02.02
9、.02.0S S2.82.84.24.23.03.04.24.24.24.24.24.23.03.03.03.03.03.09多點同時進行米字型延伸找出所有可能的Steiner vertex(B2)點對點點對點(B1)(點對點點對點)Z2Z2Z1Z1Z2Z2Z1Z110Lins Steiner Tree without Obstacles AlgorithmnStep1：設定所有終端節點的米字型延伸範圍。nStep2：使用座標軸求所有終端節點間最短距離與米字型延伸的重疊點找 所有可能的Steiner vertex nStep3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。n
10、Step4：對Map中指定範圍內的米字延伸交叉點Ci,j，進行下列所述：n(1)：將此點當作一個終端點，利用MST演算法，算出加入此點後的總樹長。n(2)：將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。nStep5：Iteration *Define T:Tree 中的每個點的集合。n(1)：建立Improvement Table(IT)。n(2)：找尋IT中最適合的Steiner vertex，將其加入T後，執行Step4。n(3)：若是IT中找不到合適的Steiner vertex(IT值 0)，則演算結束。11Lins Steiner Tree without Obsta
11、cles Algorithm建立Improvement Table(IT)。0 0-1.0-1.00.40.44.44.41.01.00.60.60.60.60 05.85.8Z1Z1Z2Z2Z3Z3-0.8-0.812Lins Steiner Tree without Obstacles Algorithm Improvement Table中，找不到合適的 Steiner vertex(IT值 0)，則演算法結束。-1.4-1.4-2.2-2.20 04.44.41 10 00 0-0.8-0.8-1.8-1.85.85.8Z1Z1Z2Z2Z3Z3Z4Z413Lins ST exist L
12、ocal Refinement without Obstacles AlgorithmnStep1：設定所有終端節點的米字型延伸範圍。nStep2：使用座標軸求所有終端節點間最短距離與米字型延伸的重疊點找 所有可能的Steiner vertex nStep3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。nStep4：對Map中指定範圍內的米字延伸交叉點Ci,j，進行下列所述：n(1)：將此節點當作一個終端點，找出距離此點線段長最小的三個終端點，並將此 三點相同值的所有節點，皆以最短路徑相連成tree。n(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此M
13、ST。n(3)：將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。nStep5：*Define T:Tree 中的每個點的集合。n(1)：建立Improvement Table(IT)。nIterationn(2)：找尋IT中數值最大Steiner vertex Ci,j(IT值 0)，暫將其加入T，用原本的樹長 減去之後算出的樹長，結果大於0則修改T，刪除IT中的此Ci,j。結果小於等於0 ，則放棄此點，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。n(3)：若是IT中找不到合適的Steiner vertex(IT值 0)，則演算結束。14Local Refineme
14、nt 示意圖Z2Z2Z1Z1Z3Z3Z4Z4Z5Z5Z6Z6Z7Z715Lins Steiner Tree with Obstacles AlgorithmnStep1：利用HGMR演算法求出終端點之間的距離nStep2：使用Prime 的MST演算法，算出連結所有終端點之MST樹長。nStep3：利用HGMR演算法洪氾求出每個自由節點避開障礙物到達地圖 盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。nStep4：將每個終端點使用米字型延伸後的重疊點找出所有可能的Steiner vertex，直到整個地圖做完為止。nStep5：對Map中的米字延伸交叉點Ci,j，進行下列所述：n(
15、1)：將此點當作一個終端點，利用Prime MST演算法，算出加入此點後的總樹長。n(2)：將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。nStep6：Iteration *Define T:Tree 中的每個點的集合。n(1)：建立Improvement Table(IT)。n(2)：找尋IT中最適合的Steiner vertex，將其加入T後，執行演算法中的Step5。n(3)：若是IT中找不到合適的Steiner vertex(IT值 0)，則演算結束。16針對地圖最北邊的列座標(0,0)(6,0)之中的所有節點，將上面的所有節點放入HGMR 演算法中的進行洪氾。wave
16、 propagation finish00 00 00 00 00 00 001.0.03.0.04.0.05.0.06.0.02.0.01.01.06.46.40 02.02.00 01.01.02.02.06.06.03.03.05.05.00 01.01.02.02.03.03.04.04.04.04.05.05.06.06.00 01.01.03.43.44.44.45.45.46.46.40 01.01.02.02.06.06.05.05.04.04.03.03.00 01.01.02.02.05.45.46.46.4wave propagationI IJ J0 01 12 23
17、34 45 56 66 65 54 43 32 21 10 017針對地圖最西邊的行座標(0,0)(0,6)與 最北邊的列座標(0,0)(6,0)之中的所有節點，將上面的所有節點放入HGMR演算法中的進行洪氾。wave propagation finish000000000000000000000000001.01.03.42.43.44.41.01.01.01.01.01.01.02.02.02.02.02.02.02.03.03.03.03.04.04.04.05.05.06.0wave propagationI IJ J0 01 12 23 34 45 56 66 65 54 43 32
18、 21 10 018Lins ST exist Local Refinement with Obstacles AlgorithmnStep1：利用HGMR演算法洪氾求出每個自由節點避開障礙物到達地圖 盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。nStep2：將每個終端點使用米字型延伸後的重疊點找出所有可能的Steiner vertex，直到整個地圖做完為止。nStep3：利用Prime 的MST演算法，算出連結所有終端點之MST樹長。nStep4：對Map中的米字延伸交叉點Ci,j，進行Local Refinement：n(1)：將此節點當作一個終端點，找出距離此點線段長最小的
19、三個終端點，並將此 三點相同值的所有節點，皆以最短路徑相連成tree。n(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。n(3)：將原本的MST樹長減去之後算出的MST樹長，紀錄在Ci,j中。nStep5：*Define T:Tree 中的每個點的集合。n(1)：建立Improvement Table(IT)。nIterationn(2)：找尋IT中數值最大Steiner vertex Ci,j(IT值 0)，暫將其加入T，用原本的樹長 減去之後算出的樹長，結果大於0則修改T，刪除IT中的此Ci,j。結果小於等於0 ，則放棄此點，並且從IT中刪除Ci,j，直到IT
20、中為正的值都測試完為止。n(3)：若是IT中找不到合適的Steiner vertex(IT值 0)，則演算結束。19HGMR、Lous、Lins Algorithm Length Example CompareZ1Z1Z3Z3Z2Z2Z5Z5Z4Z4Z6Z6Z1Z1Z3Z3Z2Z2Z5Z5Z4Z4Result of Lous(Length=13.8)Result of HGMR(Length=14.6)Z1Z1Z3Z3Z2Z2Z5Z5Z4Z4Z6Z6Result of Lins(Length=13.8)20Result of HGMR(Length=35.384)Result of Lous(
21、Length=34.142)Result of Lins(Length=34.142)HGMR、Lous、Lins Algorithm Length Example Compare21Algorithm Compare TableLous SMT AlgorithmO(N2+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
22、 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)22ConclusionsnLin的演算法之所以優於Lou，主要是在於Lou的演算法在 找尋Steiner vertex上花費過多過多的時間 去測試自由空間 上的每一個節點每一個節點，Lin的演算法收尋S
23、teiner Point僅在特定 縮小範圍內測試少許的米字延伸交叉點測試少許的米字延伸交叉點，花費較少的時間，在無障礙物空間下只需要 ，有障礙物也只需要 nLin的演算法存在Local refinement 之下，有效的降低 次方的時間，使得演算法更迅速的建立史坦那樹，不需每 次都使用Prims MST去重建所要測試的Steiner vertex與Z節 點。O(p3N)O(p2)O(N+p2)O(p)23Future StudiesnVerify our results of algorithmsnTo analyze 3D 26-Directional Steiner Tree AlgorithmnCombine Steiner tree and single layer routing Algorithm.
