考慮多層繞線與障礙物迴避之直角史坦那樹建構法

Abstract

已知散佈在各繞線層上的接點(pin)和障礙物(obstacle)的座標，我們的目的是找出一棵迴避障礙物之直角史坦那樹去連接所有的接點，而可以利用額外的點(即史坦那點)及via，但是禁止穿越過障礙物，使得繞線總長與via的總合花費最少。符合這些條件的樹，即所謂考慮多層繞線與障礙物迴避之直角史坦那樹。 本篇論文定義了一個典型流程，根據此流程我們提出了以construction-by-correction為概念的演算法：第一步驟建立Delaunay triangulation圖，連接所有的接點；第二步驟對所建立的Delaunay triangulation圖進行障礙物加權的最小生成樹的建構；接著第三步驟將樹直角化且利用三維U型線段修正總線長。 本篇論文的特點在於：1.第一步驟不作完整圖，因為其時間複雜度為O(n2)。本篇論文利用Delaunay triangulation當作一開始的連接圖，其時間複雜度為O(nlgn)。此外，我們只對所有接點作圖，並加入額外的edge在DT中，使得結果更好。2.第三步驟提出了新的U型線段修正方法並擴展到層與層之間的立體U型線段修正。特別的是，我們是對所有可能的立體U型線段作完整的分類，此處可以得到最佳解。我們在多層繞線的實驗結果，當單顆via以5單位線長計算時，平均總線長比前人少了1.99%。且在單層繞線的實驗結果平均也和目前最好的結果不相上下。

Given a set of pins and a set of obstacles on multiple routing layers, a multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) is a tree of minimal total wirelength that connects these pins, possibly through some extra points (called Steiner points) and/or vias, and bypasses all obstacles. In this thesis, we define a typical flow and propose a construction-by-correction based algorithm. First of all, an initial connection graph is constructed over all pins based on Delaunay triangulation. Secondly, an obstacle-weighted minimum spanning tree is grown up over the initial connection graph. Finally the tree edges are rectilinearized and the total wirelength is further reduced by three-dimensional U-shape refinement. Our algorithm has two features. One is that we perform Delaunay triangulation instead of using a complete graph in the first step. In addition, we only consider pins into Delaunay triangulation thus completing it in only O(nlgn) time; we add some extra edges into Delaunay triangulation that possibly contribute to a better minimum spanning tree. The other is that we present optimal three-dimensional U-shape refinement to further reduce the total wirelength. Experimental results show that as one via costs five-unit wirelength, our results in ML-OARSMT outperforms previous work by 1.99%. On the other hand, our results in SL-OARSMT are as good as the best results in literature so far.