考慮可繞性、效能、與可靠度的超大型積體電路擺置

VLSI Placement Considering Routability, Performance, and Reliability

江哲維(Zhe-Wei Jiang)

指導教授 ： 張耀文

國立臺灣大學/電機資訊學院/電子工程學研究所/博士(2009年)

https://doi.org/10.6342/NTU.2009.00911

摘要

擺置是實體設計中最重要的步驟之一，並且已經被研究了數十年。雖然擺置是傳統的設計自動化問題，現代設計的挑戰已經大幅改變了擺置問題。因此，在擺置的過程中，通常需要去考慮各種不同的目標。例如，大多數傳統的擺置演算法通常集中注意力在線長最佳化上，因而忽略了實際上的設計問題，如可繞性與效能。此外，為了減低晶片重新設計的成本與解決由製造過程所產生的可靠度問題，在擺置過程完成之後，會需要在晶片上的空白處置入數種額外的元件（如多餘單元與天線二極體）。假如我們能在擺置過程中考慮這些元件，將能夠減少在為這些元件尋找合適位置時的困難。

在這份論文當中，我們提出了數個演算法在產生超大型積體電路擺置的同時，考慮可繞性、效能、與可靠度。這份論文是由一個考慮可靠度的分析式擺置演算法所開始。我們提出了一個新方向/技術，叫作連線重疊移除，來解決基本的可繞性問題。之後，我們將正確的時序目標加入分析式擺置演算法，並且提出了考慮時序的分析式擺置演算法來在擺置過程中對電路時序作最佳化。除了可繞性與時序問題之外，晶片製造過程也對擺置產生了額外的設計困難。因此，為了要修正由晶片製造過程所產生的設計失誤，我們提出了考慮多餘單元的分析式擺置演算法以及一個多階層的多餘單元嵌入演算法以產生高品質的多餘單元分佈。為了減少由製造過程所產生的天線效應所造成的可靠度下降，我們提出了一個考慮二極體的分析式擺置演算法，以降低在之後的設計過程中所面臨的二極體置入的困難。我們更提出了一個同時嵌入二極體/跳線的演算法來解決天線效應修正的問題。

關鍵字

實體設計 ； 擺置 ； 可繞性 ； 可製造性 ； 可靠度效能

並列摘要

Placement is a major step in physical design that has been studied for several decades. Although it is a classical problem, modern design challenges have reshaped this problem. As a result, it is usually desired to consider various objectives during the placement process. For example, most existing placement algorithms focus on wirelength optimization and ignore the real design issues, such as routability and performance. Furthermore, to reduce the re-spin cost induced by post-silicon debugging and solve the reliability issues for the manufacturing process, several types of extra components (e.g., spare cells and antenna diodes) must be inserted into whitespace after the placement is done. If we can consider these components during the placement process, it will then reduce the difficulties of finding available positions for these components.

In this dissertation, we propose several novel algorithms for VLSI placement generation to consider routability, performance, and reliability. This dissertation starts from a routability-driven analytical placement with a new direction/technique, called net overlapping removal, to solve the essential routability issue. Then the timing-driven analytical placement, which models the exact timing objective into the analytical formulation, is proposed to optimize the circuit timing during the placement optimization process. Despite of the routability and timing issues, the manufacturing process may also introduce additional design difficulties. Therefore, to fix the design failure caused by the manufacturing process, we propose a spare-cell-aware analytical placement and a multilevel spare cell insertion to generate a better distribution of spare cells. To reduce the reliability degradation caused by the antenna effect during manufacturing, we propose a diode-aware analytical placement to reduce the difficulties faced by the later stage for diode insertion. We further propose a simultaneous diode/jumper insertion algorithm to solve the antenna fixing problem.

並列關鍵字

Physical Design ； Placement ； Routability ； Manufacturability ； Reliability ； Performance

參考文獻

[2] ISPD 2005 Placement Contest. http://www.sigda.org/ispd2005/contest.htm.

[3] ISPD 2006 Placement Contest. http://www.sigda.org/ispd2006/contest.html.

[12] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice-Hall, 1993.

[16] U. Brenner and M. Struzyna. Faster and better global placement by a new transportation algorithm. In Proceedings of ACM/IEEE Design Automation Conference, pages 591–596, Anaheim, CA, June 2005.

[17] U. Brenner, M. Struzyna, and J. Vygen. Bonnplace: Placement of leading-edge chips by advanced combinatorial algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(9):1607–1620, Sept. 2008.