我們提出一個在後置階段插入備用邏輯閘並最佳化時效和可繞度的方法，並且是第一個提出討論領結邏輯閘(tie cell)(和備用邏輯閘連接，用來降低靜態功率消耗)的研究。由於現在製程的進步，會有越來越多的錯誤僅能在晶片製造完成之後才能被發現到，在這階段去除錯會需要花費很大的代價。為了處理這個問題，我們會在晶片下線之前先擺置一些沒有功能的備用邏輯閘，等到錯誤產生時，我們僅需改變晶片內的連線關係，就可以達到除錯的效果，不僅省錢又省時，但是放置備用邏輯閘卻會對原本電路的效能有所影響。因此如何去擺置備用邏輯閘在晶片設計流程中有很重要的地位。我們考慮之前一些研究的優缺點，提出一個在後置階段擺置備用邏輯閘和領結邏輯閘的設計流程，讓效能的降低影響達到最低。我們先利用標準邏輯閘的分布和二分匹配的方法決定備用邏輯閘的數量和位置；之後再根據備用邏輯閘的分布和晶片的擁擠程度來決定領結邏輯閘的數量和位置；最後再最佳化其效能。實驗結果顯示，我們的方法確實是有效且有用的。

We introduce in this thesis a timing and routability optimization for insertion of spare cells in the post-placement stage and present the first work for considering tie cells, which may induce routing congestion caused by connecting to spare cells, in this problem. Due to the increasing complexity in modern VLSI designs, more and more errors can be only detected and repaired after a chip is manufactured, which makes post-silicon repair become more important than ever. To perform this process, we have to insert spare cells into a chip before tape-out. If spare cells are placed and fixed in a design, they would become obstacles to standard cells and the performance of a design maybe degraded. Thus, in this thesis, we propose a flow to insert spare cells in the post-placement stage to minimize the influence of the performance induced by allocating of spare cells and insertion of tie cells. We first use a quadrature cuts and weighted bipartite matching algorithm to insert spare cells to proper locations. After the locations of spare cells have been determined, we then place tie cells according to the distribution of spare cells and the congestion in each region. Finally, we further optimize wirelength and routabily of the design. The whole framework can be integrated into a commercial design flow, and experimental results show that our flow is effective and efficient.

[1] IWLS 2005 Benchmarks.
http://iwls.org/iwls2005/benchmarks.html.
[2] OpenCores. http://www.opencores.org.
[3] M. Abramovici, P. Bradley, K. Dwarakanath, P. Levin, G. Memmi, and D. Miller. ”A reconfigurable design-for-debug infrastructure for SoCs,” In Proc. of DAC, pp.7-12, 2006.
[4] C. Bingert, C. D. Gorsuch, O. G. Mercado, A. K. Myers, J. A. Schadt, and B. W. Yeager. US patent 6,600,341: Integrated circuit and associated design method using spare gate islands, 2003.
[5] U. Brenner, et al., ”Almost optimum placement legalization by mini-mum cost flow and dynamic programming,” In Proc. of ISPD, pp.2-9, 2004.
[6] P. Chaisemartin. US patent 6,586,961: Structure and method of repair of integrated circuits, 2003.
[7] K.-H. Chang, I. L. Markov and V. Bertacco. ”Automating post-silicon debugging and repair,” In Proc. of ICCAD, pp.91-98, 2007.
[8] K.-H. Chang, I. L. Markov, and V. Bertacco. ”Reap what you sow: Spare cells for post-silicon metal fix,” In Proc. of ISPD, 2008.
[9] Y.-P. Chen, J.-W. Fang and Y.-W. Chang, ”ECO timing optimization using spare cells.” In Proc. of ICCAD, pp.530-535, 2007
[10] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, ”NTUplace3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE TCAD, Vol.27,
No.7, pp.1228-1240, 2008.
[11] K. Doll, F. Johannes, K. Antreich, ”Iterative placement improvement by network flow methods,” IEEE TCAD, pp.1189-1200, 1994.
[12] R. Goering, ”Cadence CTO: CAD ’foundations’ must change.” EETimes, April 11, 2006. http://www.eetimes.com/showArticle.jhtml?articleID=185300099
[13] Z.-W. Jiang, T.-C. Chen, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, ”NTU- place2: A hybrid placer using partitioning and analytical techniques,” In Proc. ACM Int. Symp. Phys. Des., pp.215V217, 2006,
[14] I. H.-R. Jiang, Hua-Yu Chang, Liang-Gi Chang, and Huang-Bi Hung, ”Matching-based minimum-cost spare cell selection for design
changes,” In Proc. DAC, pp.408-411, 2009.
[15] Zhe-Wei Jiang, Meng-Kai Hsu, Yao-Wen Chang, and Kai-Yuan Chao, ”Spare-cell-aware multilevel analytical placement,” In Proc. DAC, pp.430 - 435, 2009.
[16] D. Josephson. ”The good, the bad, and the ugly of silicon debug,” In Proc. of DAC, pp.3-6, 2006.
[17] U. Lauther, ”A min-cut placement algorithm for general cell assemblies based on a graph representation,” In Proc. of DAC, pp.1-10, 1979.
[18] C.-P. Lu, Chao, M.C.-T, C.-H. Lo, and C.-W. Chang, ”A metal-only-ECO solver for input-slew and output-loading violations,” IEEE TCAD, pp.240-245, 2010
[19] R. L. Payne. US patent 5,959,905: Cell-based integrated circuit design repair using gate array repair cells, 1999.
[20] J. A. Roy, N. Viswanathan, G. J. Nam, C. J. Alpert, and L. Markov. ”CRISP: congestion reduction by iterated spreading during placement,”In Proc. of ICCAD, pp.357-362, 2009.
[21] J. A. Schadt. US patent 6,404,226 B1: Integrated circuit with standard cell logic and spare gates, 2002.
[22] P. Spindler, and F. M. Johannes. ”Fast and accurate routing demand estimation for efficient routability-driven placement,” In Proc. of DATE, pp.1226-1231, 2007.
[23] P. Spindler, U. Schlichtmann, and F. M.Johannes. ”Abacus: fast legalization of standard cell circuits with minimal movement,” In Proc. Of ISPD, pp.47-53, 2008.
[24] C. L. Yee, S. Aji, and S. Rusu. US patent 5,623,420: Method and apparatus to distribute spare cells within a standard cell region of an integrated circuit, 1997.