《一个可减少危险区域的后置通道绕线处理器》由会员分享，可在线阅读，更多相关《一个可减少危险区域的后置通道绕线处理器（6页珍藏版）》请在金锄头文库上搜索。
1、科學與工程技術期刊科學與工程技術期刊第一卷第一卷第二期第二期民國九十四年民國九十四年Journal of Science and Engineering Technology, Vol. 1, No. 2, pp. 23-28 (2005)23一個可減少危險區域的後置通道繞線處理器一個可減少危險區域的後置通道繞線處理器程仲勝大葉大學電機工程學系彰化縣大村鄉山腳路 112 號摘摘要要隨著積體電路中線路之間的距離越來越小且整個電路的運算速度也越來越快，因此交感雜訊（crosstalk noises）和瑕疵點（spot defects）的問題亦日趨重要。交感雜訊是由於相鄰線路間相互電容及電感作用之結
2、果。其可增長訊號延遲時間亦能導致不預期之邏輯轉變。另一方面，在積體電路製造過程中，若額外多餘物質之附著或部份製造物質之脫落，相鄰線路間便會產生瑕疵點，此時恐將導致線路之間短路或斷路。在積體電路的設計和製造過程中，交感雜訊和瑕疵點將會大大降低晶片效能和產量。因此對超大型積體電路實體設計（physical design）後段之詳細繞線（detailed routing）階段而言，如何減少相鄰線路之間易產生交感雜訊和不良瑕疵點的危險區域（critical regions）已成為一相當重要的課題。本論文中我們將考慮解決通道繞線（channel routing）危險區域最小化的問題。由於直接設計一具有最
3、少危險區域的通道繞線演算法之問題複雜度相當高，因此取而代之的是去改進現存通道繞線演算法的結果以減少危險區域。所提出的後置繞線處理器採用軌道重新排列（trackpermutation）和佈局層重新指定（layer assignment）兩階段以改進繞線結果。在軌道重新排列階段，我們採用一個以圖形為主的啟發式演算法將所有繞線軌道重新排列。至於佈局層重新指定方面，我們針對繞線線段建立有權重的平面圖，並求其具有最大權重之獨立集（maximumweighted independent set） ，以解決繞線線段佈局層重新指定問題。最後，我們以一些例子來測試評估所提出之能減少危險區域之後置通道繞線處理器，
4、實驗結果證實所提方法確實能有效減少危險區域的數量。關鍵詞關鍵詞：交感雜訊，瑕疵點，危險區域，積體電路實體設計，通道繞線APostprocessing Channel Router for Critical RegionMinimizationJONG-SHENGCHERNGDepartment of Electrical Engineering, Da-Yeh University112 Shan-Jiau Rd., Da-Tsuen, Changhua, TaiwanABSTRACTAs interconnection wire spacing becomes smaller and the
5、 circuit operating frequency runshigher, the problems of crosstalk noises and spot defects become very crucial.Since crosstalks are a科學與工程技術期刊科學與工程技術期刊第一卷第一卷第二期第二期民國九十四年民國九十四年24result of mutual capacitances and inductances between neighboring wires, they can cause increaseddelays or inadvertent logi
6、c transitions.Spot defects are caused by extra or missing material duringthe manufacturing process.They may cause a short or an open circuit between neighboring wires.During integrated circuit design and manufacturing, crosstalks and spot defects will greatly reduce theperformance and the yield of c
7、hips.Consequently, reduction of the critical regions betweeninterconnection wires resulting from crosstalks and spot defects becomes an important considerationin the detailed routing phase of VLSI physical design.In this paper, the critical region minimization problem for channel routing is consider
8、ed.Dueto the high complexity of directly developing a critical region minimum channel routing algorithm, apostprocessor to improve the results of existing routing algorithms by minimizing critical regions isproposed instead.In this postprocessor, two phases, namely track permutation and layer assign
9、ment,are considered.In the track permutation phase, a graph-based heuristic is proposed for permutingthe routing tracks.As for the layer assignment phase, some weighted planar graphs can be derivedfrom the routing segments; then, the maximum weighted independent set for each can be found so asto obt
10、ain a critical region minimization layer assignment solution.The proposed postprocessor was evaluated with some channel routing examples.Theexperimental results showed that the number of critical regions between adjacent wires for eachexample is minimized.Key Words: crosstalk noises, spot defects, c
11、ritical regions, VLSI physical design, channel routing一一、簡介簡介隨著超大型積體電路設計及製造技術的進步 ， 電路元件間放置的距離日漸縮短 ， 再者隨著線路及電晶體交換延遲時間的縮短，因而導致快速的訊號轉換，所有上述因素都會增加線路元件間的耦合電容 。 然而耦合電容的增加不僅會導致較長的訊號傳輸時間，並且由於交感雜訊（crosstalk noises）的影響而產生訊號傳輸的不一致性 ， 進而導致整個系統運作發生錯誤。另一方面，由於電路元件及線路擺放距離日漸縮短 ， 相鄰線路及元件間較易由於額外多餘物質之附著或部份製造物質之脫落 ， 而產生
12、導致線路之間短路或斷路之瑕疵點（spot defects） 。在積體電路的設計和製造過程中，交感雜訊和瑕疵點將會大大地提高測試成本及降低系統效能和產量 2，因此如何減少線路元件間易產生交感雜訊和不良瑕疵點的危險區域（critical regions）已成為一個相當重要的研究課題。基本上發展一具有最少危險區域的繞線演算法比一般傳統繞線演算法更加困難 ， 這是因為具有最少危險區域的演算法除了必須決定每一個別的繞線位置以外 ， 同時亦需考慮線段間的相對位置 ， 以避免產生過大的交感雜訊以及過多的不良瑕疵點。一般而言， 具有此類效能驅動繞線問題可分為兩類繞線模式來解決。第一種是使用無格線繞線（grid
13、less routing）模式， 藉由調整格線空間大小以降低交感雜訊及減少不良瑕疵點的數目，達到具有最少危險區域的效果。如在文獻3,10 中，作者利用無格線繞線模式來降低交感雜訊，但其並未具體考慮瑕疵點的問題。第二種為使用有格線繞線（gridded routing）模式，此種模式中的每一繞線線段必須放置在固定寬度的格線內，無法調整格線空間大小，因此必須在繞線時考慮線段間的相對位置以減少危險區域。 目前此類有格線繞線模式的作法只分別應用於減少交感雜訊或減少易形成不良瑕疵點的危險區域， 而並未同時考慮降低兩者所形成的危險區域數目。單純降低交感雜訊的作法，已應用在平面繞線 4,5，通道繞線 1,6,
14、8,11 及四面通道繞線7。而在文獻 9 中，亦只單純減少易產生瑕疵點的危險區域而完全忽略交感雜訊所造成的影響。本論文中， 我們將處理同時減少交感雜訊及瑕疵點所形成危險區域的有格線通道繞線（channel routing）問題。由於在繞線階段時以全區域性的角度來考慮危險區域最少化問題是一件耗時且相當困難的問題， 因此我們的作法並不會直接尋求一個啟發式的繞線演算法， 而是去修改一個現存有格線繞線演算法的結果以減少危險區域的數目。 此種作法的好處之一是能善加利用現存繞線演算法的優點， 並將問題的程仲勝程仲勝：一個可減少危險區域的後置通道繞線處理器一個可減少危險區域的後置通道繞線處理器25複雜度降低
15、。在此論文中，我們將提出一個後置通道繞線處理器，它首先接受一有格線初始繞線結果，然後重新排列軌道的順序，接著再重新指定目前繞線線段的位置，以減少網列（nets）間危險區域的數目。本論文往後章節組織如下：第二節為欲解決問題之描述 。 第三節詳細介紹我們提出來解決危險區域問題之後置通道繞線演算法。第四節為實驗結果，實驗內容顯示我們提出的通道繞線器確實可減少繞線連線組間危險區域的數目 。 最後第五節為結論。二二、問題描述問題描述繞線是 VLSI 實體設計不可或缺的一環，而有格線通道繞線問題（gridded channel routing problem）則為詳細繞線的一種特殊型態問題 。 它最主要的
16、目的是在滿足一些限制條件下將位於通道上下兩邊的接腳（pin）集合在格子化通道繞線區域內相互連接而使得通道高度達到最小，如圖 1 所示。但隨著通道中連接線間相互距離越來越小，使得容易產生交感雜訊和瑕疵點的危險區域越來越多 （如圖 1 灰色區域所示） ，進而影響繞線品質。因此我們的目標為發展一可得到最少危險區域的繞線演算法。在著手進行繞線演算法設計之前 ， 必須先分析與評估任兩線段之間交感雜訊的大小以及其間產生瑕疵點的機率 。 首先我們將評估交感雜訊的大小 ， 交感雜訊為相鄰連接線間寄生耦合現象而導致的電磁干擾現象 2。一般而言，相鄰兩連接線間交感雜訊值的大小與其耦合平行長度成正比 ， 而與其距離成反比 2。然而由於兩平行線段間的耦合電容會隨著其間距離的增加而快速遞減，因此為了簡化問題起見，在本論文中我們可合理的假設交感雜訊只存在於格子化繞線區域之相鄰列（row）或相鄰行（column）間，如圖 1 方形灰色區域所示。1014223435top boundary pinchannel heightchannel length bottom bound
