隨著超大型積體電路（VLSI）製程的演進，天線效應（antenna effect）降低製造良率（manufacturing yield）的現象越來越明顯。在實體設計（physical design）階段，如何避免天線效應的影響，已經成為十分重要的課題。由於修改部分電路布局（layout）的動作較為容易且有效率，因此使用跳線插入（jumper insertion）作為避免天線效應的方法較常被選擇使用。現今使用跳線插入必須考慮到金屬層數（metal layer）、電荷分享（charge sharing）、製造時符合天線規則（antenna rule）與跳線終止層數（jumper end layer），但是目前尚未有一套完整的方法可同時處理以上四點議題。本論文提出，首先利用金屬移除（metal removing）的方式，將繞線樹（routing tree）拆解成數個子繞線樹，並找尋需要插入跳線的子繞線樹及其跳線終止層數。再使用網路流（network flow）的概念對閘極氧化層分組，並利用整數線性規劃（integer linear programming）模型找尋最少鑽孔（via）數量的跳線插入以完成分組的動作，即拆解成更小的子繞線樹。遞迴執行上述兩個方法，直至所有子繞線樹均被完全拆解為止。實驗結果顯示，我們提出的方法可使用最少數量的鑽孔，避免繞線樹的天線效應，且保證繞線樹不會在製造階段有違反天線效應的情況。With the evolution of VLSI process, the manufacturing yield loss caused by the antenna effect is more and more obvious. As a result, avoiding the antenna effect is an important issue in physical design.Since modifying some parts of a circuit layout is simpler and more effective, jumper insertion is a general approach to avoid antenna effect. Using jumper insertion should consider metal layer, charge sharing, jumper end layers, and maintaining antenna rule during manufacturing in modern designs. However, there is no jumper insertion algorithm completely consider the four issues.This study first proposes a metal removing method to separate a routing tree into sub-trees, to find sub-trees violating antenna rule, and to decide the jumper end layer for these sub-trees. Then, the network flow method is considered for vertex grouping to solve antenna problems. Moreover, using integer linear programming to separate an antenna violating sub-tree into antenna free sub-trees with minimal via usage for jumper insertion. Above two methods are used recursively until all sub-trees do not exist. Experimental results show that the proposed jumper insertion algorithm can use minimal number of vias to avoid antenna effect on routing trees with guaranteeing that the antenna rule is obeyed on the routing tree during manufacturing.
