具備導線推擠能力的高效能多餘貫穿點插入方法

Abstract

隨著製程進入奈米時代，能有效的微影以及得到良好的製造程序變得愈來愈困難。在積體電路實體層設計上導致良率下降的其中一個主要因素為貫穿點(via)的損毀。因此，得到一個良好的控制基制去改善貫穿點的製造良率以及可靠度，是可製造設計(DFM)的一個重要課題。 插入多餘貫穿點是一個被證實有效並且被廣泛推薦來增加貫穿點良率 以及可靠度的方法。在這篇論文，我們發展一個在佈線後能高效能插入多餘貫穿點的演算法來增加良率。我們把插入多餘貫穿點的問題轉換成混合二部碰撞圖形的匹配問題，並提出一個新穎的啟發式最小加權匹配演算法去解決此問題。此方法除了插入多餘貫穿點於存活貫穿點(Alive via)，還運用導線推擠的概念去保護荒廢貫穿點(Dead via)，方法是把荒廢貫穿點鄰近的導線往空置的空間移開使能在其旁加上多餘貫穿點。實際結果證明我們的方法可以獲得一個 高的多餘貫穿點插入率並能有效地執行。

As the process technologies advancing to nanometer epochs, the lithography and manufacture procedures turn out to be more difficult. Via defect is one major source of yield loss during the physical design stage. Therefore, requiring a good control for via failure to improve via yield and reliability is one of the most important issues in design for manufacturability (DFM). Redundant via insertion is a verified efficient and widely recommended method to enhance via yield and reliability. The purpose of this thesis is to develop an efficient method to insert redundant vias in the post-routing stage. We transform the redundant via insertion problem into a mixed bipartite-conflict (MBC) graph matching problem, and present a novel heuristic minimum weighted matching algorithm (HMWM) to solve it. The proposed method, besides inserting redundant vias for alive vias, also protects the dead vias by applying wire pushing capability which shifts wires into the empty space and adds redundant vias next to dead vias. Experimental results show that our method obtains a high redundant via insertion rate and perform effectively.