感知冗餘繞線之工程修改命令時序及光罩成本最佳化

由於晶片設計複雜度的增加，工程修改命令(ECO)成為一項必要的技術來處理晶片設計後期發現之功能(functional)或時序(timing)的缺陷。在光罩製作後(post-mask)的工程修改命令中利用預留原件(spare cells)修正違反時序的錯誤時，減少光罩重製(respin)的成本變得非常重要。光罩重製的成本和重新繞線(rewiring)所需要改變的金屬層及導通孔(via)光罩的數量成正比關係。在本論文中，我們介紹一個新的問題──工程修改命令時序最佳化下同時考慮再利用冗餘繞線(redundant wires)來減少重新繞線金屬層的數量，並且提出第一個方法來解決問題。首先，在選取預留原件上，我們提出多重物資流(multi-commodity flow)模型藉由考慮冗餘繞線，極小化使用的繞線資源，並利用簡化但不失最佳解的整數線性規畫(integer linear programming)來解決。再者，我們提出一個考慮冗餘繞線再利用的瓦格式無格線繞線器(tile-based gridless router)來完成繞線。我們的演算法藉由反覆的考慮不同金屬層上的冗餘繞線去選取預留原件和繞線來取得需要改變的金屬層和導通孔光罩的最小數量。五個工業界測試資料的實驗結果顯示，我們的演算法在合理的執行時間下，不僅能有效地處理違反時序的錯誤，並且減少光罩重製的成本。

關鍵字

工程修改命令；時序最佳化；冗餘繞線；光罩成本；預留元件

並列摘要

Due to the increasing IC design complexity, engineering change order (ECO) has become a necessary technique to resolve late-found functional and/or timing deficiencies. To fix timing violations using spare cells in post-mask ECO, the reduction of the mask respin cost has become very critical. The mask respin cost is proportional to the number of changed masks of vias and metal layers for rewiring. In this thesis, we introduce a new problem of ECO timing optimization considering redundant wires reuse to reduce the number of layers used for rewiring and present the first work for this problem. First, we present a multi-commodity flow model of the spare-cell selection with used routing resources minimization by considering redundant wires and apply integer linear programming (ILP) to solve the selection problem with ILP reduction without loss of the solution optimality. Then, we present a tile-based gridless router considering redundant wires reuse to complete the routing. Our algorithm iteratively performs spare-cell selection and routing considering redundant wires on each layer to find the minimum number of changed metal layer masks and via masks. Experimental results based on five industry benchmarks show that our algorithm not only effectively resolves timing violations but also reduces the mask respin cost under reasonable run times.

並列關鍵字

Engineering Change Order ； Timing Optimization ； Redundant Wires ； Mask Cost ； Spare Cells

參考文獻

[2] International Technology Roadmap for Semiconductors 2005 Edition.

[3] Solving Constraint Integer Programs. http://scip.zib.de/.

[10] Y.-M. Kuo, Y.-T. Chang, S.-C. Chang and M. Marek-Sadowska, “Spare cells with constant insertion for engineering change,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 28, No. 3,

[11] J.-Y. Li and Y.-L. Li, “An efficient tile-based ECO router with routing graph reduction and enhanced global routing flow,” Proceedings of ACM International Symposium on Physical Design, pp. 7–13, San Francisco, CA, April 2005.

[16] C. Tsai, S. Chen, and W. Feng, “An H-V alternating router,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, No. 8, pp. 976–991, August 1992.

國際替代計量

感知冗餘繞線之工程修改命令時序及光罩成本最佳化

全文下載

主題瀏覽