一個可減少危險區域的後置通道繞線處理器

A Postprocessing Channel Router for Critical Region Minimization

隨著積體電路中線路之間的距離越來越小且整個電路的運算速度也越來越快，因此交感雜訊（crosstalk noises）和瑕疵點（spot defects）的問題亦日趨重要。交感雜訊是由於相鄰線路間相互電容及電感作用之結果。其可增長訊號延遲時間亦能導致不預期之邏輯轉變。另一方面，在積體電路製造過程中，若額外多餘物質之附著或部份製造物質之脫落，相鄰線路間便會產生瑕疵點，此時恐將導致線路之間短路或斷路。在積體電路的設計和製造過程中，交感雜訊和瑕疵點將會大大降低晶片效能和產量。因此對超大型積體電路實體設計（physical design）後段之詳細繞線（detailed routing）階段而言，如何減少相鄰線路之間易產生交感雜訊和不良瑕疵點的危險區域（critical regions）已成為一相當重要的課題。 本論文中我們將考慮解決通道繞線（channel routing）危險區域最小化的問題。由於直接設計一具有最少危險區域的通道繞線演算法之問題複雜度相當高，因此取而代之的是去改進現存通道繞線演算法的結果以減少危險區域。所提出的後置繞線處理器採用軌道重新排列（trackpermutation）和佈局層重新指定（layer assignment）兩階段以改進繞線結果。在軌道重新排列階段，我們採用一個以圖形為主的啟發式演算法將所有繞線軌道重新排列。至於佈局層重新指定方面，我們針對繞線線段建立有權重的平面圖，並求其具有最大權重之獨立集（maximumweighted independent set），以解決繞線線段佈局層重新指定問題。 最後，我們以一些例子來測試評估所提出之能減少危險區域之後置通道繞線處理器，實驗結果證實所提方法確實能有效減少危險區域的數量。