隨著近代積體電路的製程不斷演進，導線的阻抗的影響以及其造成的訊號延遲的影響也顯著的提高。為了解決這個問題，一種新的灌孔構造──「階梯式灌孔」(Via Ladder)被提出。然而，在繞線階段前的階梯式灌孔擺置程序的低落成功率儼然成為了立即性的問題。在這篇論文中，我們透過實驗探討了階梯式灌孔擺置失敗的成因，並用嵌入到實際製程的標準元件庫(Standard Cell Library)的測資來驗證我們所觀察到的成因。實驗結果顯示階梯式灌孔擺置失敗的原因大致可以歸咎於以下：繞線軌道(Track)的對齊與否、其結構是否與電源電路交疊、其結構是否與其他階梯式灌孔交疊或超出邊界。為此，我們提出了一個細節佈局(Detailed Placement)流程，在流程當中考慮了所有需要擺置階梯式灌孔的標準元件，以期達到擺置成功率的最大化。在我們提出的演算法當中，我們首先為標準元件濾除掉了沒有達到擺置條件的位置，並且將所有需要擺置階梯式灌孔的標準元件移動到符合條件的位置。接下來，我們分別透過兩次的標準元件合法化機制(Legalization)來消除所有標準元件之間的重疊情形。該合法化機制是延伸自基於動態規劃的單行內細節佈局演算法。最後，我們透過標準元件的廣域移動來緩解太過擁擠導致合法化失敗的標準元件行。實驗結果顯示，在嵌入到實際製程的標準元件庫的測資當中，我們所提出的演算法可以達到平均97%的擺置成功率。

With the feature size shrinking down to 7 nm and beyond, the impact of wire resistance is significantly growing, and the circuit delay incurred by the metal wires is noticeable raising. To address this issue, a new technique called via ladder (or via pillar) insertion is presented. However, the poor success rate of via ladder insertion process before the routing stage immediately becomes a significant problem. In this thesis, we explore the causes of via ladder insertion failures by experiments on the benchmarks which are embedded in a real industrial cell library. The experiments show that the reasons for the low success rate may be attributed to the track alignment issue, power & ground stripe overlapping, and insufficient margin area. Therefore, we further propose a detailed placement flow which is aware of via ladder to maximize the success rate on via ladder insertion. In the proposed algorithm, we first filter out all of the infeasible solutions, and then move the via ladder-inserted cells to their eligible positions. Next, we adopted two-stage legalization method with high flexibility on cell order based on an extension to the dynamic programming-based detailed placement algorithm. Finally, we improve congested rows with a global movement process. Experiment results show that our algorithm increases the insertion rate by 54 to 58 percent, and achieves over 99% insertion rate in average on modified ISPD 2015 benchmarks.

[1] I. S. Bustany, D. Chinnery, J. R. Shinnerl, and V. Yutsis, "ISPD 2015 Bench-
marks with Fence Regions and Routing Blockages for Detailed-Routing-Driven
Placement", in Proc. ISPD, pp 157-164, 2015.
[2] W. -K. Chow, J. Kuang, X. He, W. Cai, and E. F. Y. Young, "Cell density-
driven detailed placement with displacement constrain", in Proc. ISPD, pp
3-10, 2014.
[3] Y. Du, and M. D. F. Wong, "Optimization of standard cell based detailed
placement for 16 nm FinFET process", in Proc. DATE, pp. 357, 2014.
[4] T. -Y. Ho, and S. -H. Liu, "Fast legalization for standard cell placement with simultaneous wirelength and displacement minimization", in Proc. International
Conference on VLSI and System-on-Chip, pp. 291-311, 2010.
[5] Y. Lin, B. Yu, and D. Z. Pan, "Detailed placement in advanced technology
nodes: A survey", in Proc. ICSICT, 2016.
[6] L. -C. Lu, "Physical Design Challenges and Innovations to Meet Power, Speed,
and Area Scaling Trend", in Proc. ISPD, pp. 63, 2017.
[7] T. Lin, and C. Chu, TPL-Aware Displacement-driven Detailed Placement
Renement with Coloring Constraints ", in Proc. ISPD, pp. 75-80, 2015.
[8] Y. Lin, B. Yu, X. Xu, J. -R. Gao, N. Viswanathan, W.-H. Liu, Z. Li,
C. J. Alpert, and D. Z. Pan, "MrDP: Multiple-row detailed placement of
heterogeneous-sized cells for advanced nodes", in Proc. ICCAD, 2016.
[9] W. -K. Mak, W. -S. Kuo, S -H Zhang, S. -I. Lei, and C. Chu, \Minimum
Implant Area-Aware Placement and Threshold Voltage Renement", in Proc.
TCAD, pp. 1103-1112, 2017.
[10] M. Pan, N. Viswanathan, and C. Chu, "An ecient and eective detailed place-
ment algorithm", in Proc. ICCAD, 2005.
[11] T. Taghavi, Z. Li, C. Alpert, G. -J. Nam, A. Huber, and S. Ramji, "New
placement prediction and mitigation techniques for local routing congestion ",
in Proc. ICCAD, 2010.
[12] G. Wu, and C. Chu, "Detailed Placement Algorithm for VLSI Design With
Double-Row Height Standard Cells", in Proc. TCAD, pp. 1569-1573, 2015.
[13] Y. -Y. Wu, and Y. -W. Chang, "Mixed-cell-height detailed placement consid-
ering complex minimum-implant-area constraints", in Proc. ICCAD, 2017.
[14] B. Yu, X. Xu, J. -R. Gao, and D. Z. Pan, "Methodology for standard cell
compliance and detailed placement for triple patterning lithography", in Proc.
ICCAD, 2013.