Abstract
在IC 設計中，接點(via)所扮演的功能為替相鄰兩層的金屬線段提供訊號通 路。然而，由於在晶片生產過程中的接點失準(cut misalignment)、金屬線之線 端點內縮(line-end shortening)及因電致遷移(electro-migration)或熱應力 (thermal stress)效應所造成之空孔(void)缺陷等因素，可能造成部分或整個接 點毀損。因此，如何降低因接點毀損所造成的良率下降則為可製造性導向之設計 方法(design for manufacturability)中重要議題之一。 加入一冗餘接點(redundant via)到各個接點旁為一廣為人知且較為推薦的 方法。對於每個被加入冗餘接點的接點處，由於同時存在兩個接點，當單一個接 點損毀時並不會對晶片的功能性造成影響；也因此晶片的良率及可靠度可望獲得 提升。此外，對於每個接點層(via layer)上的區域(region)，其接點密度(via density)可被定義為其所包含的接點個數。若過多的接點被安插到某區域中，而 違反了最大接點密度限制，則接點形狀扭曲(pattern distortion)的現象將變得 更為嚴重，反而造成晶片良率及可靠度下降。因此在進行冗餘接點安插後，接點 密度必須被再次驗證。 在這篇論文中我們研究許多以改善良率及可靠度為目標之後繞線階段 (post-routing)冗餘接點安插問題。最初，我們研究傳統的後繞線階段冗餘接點 安插問題。我們將其轉換為一最大獨立子集(maximum independent set)問題， 並提出一有效率的圖形建構演算法。此外，我們更提出一有效率的啟發式方法 (heuristic)及一個以零壹整數線性規劃(0-1 integer linear program)為基礎 的方法來解決此問題。因為冗餘接點可被分類為在軌冗餘接點(on-track redundant via)及離軌冗餘接點(off-track redundant via)，且在軌冗餘接點 具備較佳的電氣特性，我們亦研究一個具在軌接點偏好的冗餘接點安插問題。我 們提出兩個啟發式方法來增加所安插的在軌冗餘接點數量並提出一個以零壹整 數線性規劃為基礎的最佳化方法。接著我們研究具接點密度考量之後繞線階段冗 餘接點安插問題。我們亦研究如何同時考量在軌接點偏好及接點密度並提出許多 啟發式方法及一個以零壹整數線性規劃為基礎的最佳化方法。最後，我們研究如 何利用線段彎曲(wire bending)技術來增進冗餘接點安插率並提出一個快速又有 效的以零壹整數線性規劃為基礎的最佳化方法。我們亦擴充此方法使其能考慮在 軌接點偏好及/或接點密度。 上述所提出的每個方法都已被實作且其強健性(robustness)皆已藉由應用 於實際晶片上所呈現。