以改善良率及可靠性為目標之有效率的冗餘接點安插方法

Efficient Approaches to Redundant Via Insertion for Yield and Reliability Improvement

李光曜(Kuang-Yao Lee)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系/博士(2009年)

摘要

In an IC layout, a via provides a connection between two net
segments from adjacent metal layers. Due to various reasons such as cut misalignment, line-end shortening, and voiding effect induced by electromigration and thermal stress, a via may fail partially or completely. As a result, to reduce the yield loss due to via failures is one of the most important issues in design for manufacturability.

A well known and highly recommended method to improve via yield is to add a redundant via adjacent to a single via, enabling a single via failure to be tolerated. Therefore, redundant vias can improve the reliability of a design. Moreover, for each region of a pre-defined size on a via layer, its via density can be defined as the number of vias within it. If too many redundant vias are inserted into a region, and the amount exceeds the maximum via density constraint, the pattern distortion of the vias in that region will become serious and hence the yield/reliability of the design will become worse. Therefore, after inserting redundant vias into a design, the maximum via density rule should be re-verified.

In this dissertation, we investigate several redundant via insertion problems for yield and reliability improvement in a post-routing stage. We first study the classical post-routing redundant via insertion problem. We formulate it as a maximum independent set (MIS) problem and present an efficient graph construction algorithm to model the problem. Moreover, we present an efficient heuristic
and a 0-1 integer linear program (0-1 ILP) based optimal approach to solve this problem. Since redundant vias can be classified into on-track and off-track ones, and on-track ones use less routing resources and have better electrical properties, we also study the problem of redundant via insertion with a preference for on-track redundant vias. We present two heuristic methods to increase the amount of on-track redundant vias. We also present a 0-1 ILP based
approach to optimally solve this problem. Next, we investigate the problem of redundant via insertion with via density consideration and propose a two-stage heuristic and a 0-1 ILP based optimal approach. We also study how to simultaneously consider the via density and the preference for on-track redundant vias and propose several heuristics and a 0-1 ILP based optimal approach. Finally, we study how to utilize a wire bending technique to improve the insertion rate of redundant vias and propose an efficient and effective 0-1 ILP based solution. We also extend the 0-1 ILP approach to consider the via density and/or the preference for on-track redundant vias.

Each of our redundant via insertion approaches mentioned above has been implemented and its robustness is well demonstrated by experiments on real circuits.

關鍵字

冗餘接點 ； 接點密度 ； 零壹整數線性歸劃 ； 實體設計 ； 設計自動化

並列摘要

在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)皆已藉由應用
於實際晶片上所呈現。

並列關鍵字

redundant via ； via density ； 0-1 integer linear program ； physical design ； electronic design automation

參考文獻

[4] Reference Flow 5.0 and Reference Flow 6.0. Taiwan Semiconductor Manufacturing Company (TSMC).

[6] G. A. Allan. Targeted layout modifications for semiconductor yield/reliability enhancement.

IEEE Transactions on Semiconductor Manufacturing, 17(4):573-581, November 2004.

[7] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec., 19(2):322-331, 1990.

[8] S. Brakatsoulas, D. Pfoser, and Y. Theodoridis. Revisiting R-tree construction principles.