試誤型史坦那樹演算法及.ppt課件

1、試誤型史坦那樹演算法及電子設(shè)計(jì)自動化的應(yīng)用Obstacle-Avoiding Heuristics for Steiner Tree Problem in EDA報(bào) 告 人：林琮徨指導(dǎo)教授：黃元欣 博士 詹景裕 博士 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 演算法求出終端點(diǎn)之間的距離。Step2：利用Prime 的MST演算法

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

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

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

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

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

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

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

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

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

15、去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5： * Define T : Tree 中的每個(gè)點(diǎn)的集合。(1) ：建立Improvement Table (IT)。Iteration(2) ：找尋IT中數(shù)值最大Steiner vertex Ci,j (IT值 0)，暫將其加入T，用原本的樹長 減去之後算出的樹長，結(jié)果大於0則修改T，刪除IT中的此Ci,j 。結(jié)果小於等於0 ，則放棄此點(diǎn)，並且從IT中刪除Ci,j ，直到IT中為正的值都測試完為止。 (3) ：若是IT中找不到合適的Steiner vertex(IT值 0) ，則演算結(jié)束。 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的演算法之所以優(yōu)於Lou，主要是在於Lou的演算法在 找尋Steiner vertex上花費(fèi)過多的時(shí)間 去測試自由空間 上的每一個(gè)節(jié)點(diǎn)，Lin的演算法收尋Steiner Point僅在特定 縮小範(fàn)圍內(nèi)測試少許的米字延伸交叉點(diǎn)，花費(fèi)較少的時(shí)間， 在無障礙物空間下只需要 ，有障礙物也只需要 Lin的