混合單元高度的超大型積體電路(VLSI)已經廣泛應用以滿足不同的設計需求。由於各種與製造相關的設計考量，例如佈局相 依效應（layout dependent effects）、汲極對汲極相鄰（drain-to-drain abutment），以及多重圖案上色。相鄰單元之間的放置位置 不同，間距的差異可能會對性能造成影響，其通常被建模為離散 的間距成本。針對混合單元高度設計的離散間距成本感知的詳細放置問題，目前最先進的基於動態規劃（DP）的方法，因其極高的複雜性，只能同時處理少數個單元列。
在本文中，我們提出了一種新穎的DP演算法，可以更有效地解決這個問題。此外，還提出了幾種保持最優性的簡化技術，以便為大型設計推導出全晶片最優解。在兩種可製造性設計考量的實驗表明，所提出的方法在總間距成本、總位移和運行時間方面遠優於現有研究。

Mixed-cell-height VLSI circuits have been popularly adopted to meet different design requirements. Due to various design for manufacturability (DFM)-related considerations, such as layout dependent effects (LDEs), drain-to-drain abutment (DDA), and pattern coloring for multiple patterning, different spacings in terms of placement sites between each pair of adjacent cells may result in different performances, which are usually modeled as discrete spacing costs. To tackle such a discrete and spacing cost-aware detailed placement problem for mixed-cell-height designs, a state-of-the-art dynamic programming (DP)-based approach can only tackle few cell rows simultaneously due to its extremely high complexity. In this paper, we propose a novel DP algorithm that can optimally and much efficiently solve the problem.
In addition, several optimality-preserving reduction techniques are also proposed to enable the possibility of full-chip optimal solution derivation for large-scale designs. Experiments considering two DFM considerations show that the proposed approach greatly outperforms existing studies in terms of the total spacing cost, the total displacement, and runtime.

Bibliography
[1] J. Chen, Z. Zhu, W. Zhu and Y.-W. Chang, “Toward Optimal Legalization for Mixed-Cell-Height Circuit Designs,” Proc. DAC, 2017.
[2] J. Chen, P. Yang, X. Li, W. Zhu and Y.-W. Chang, “Mixed-Cell-Height Placement with Complex Minimum-Implant-Area Constraints,” Proc. ICCAD, 2018.
[3] J. Chen, Z. Zhu, Q. Liu, Y. Zhang, W. Zhu and Y.-W. Chang, “Hamiltonian Path Based Mixed-Cell-Height Legalization for Neighbor Diffusion Effect Mitigation,” Proc. DAC, 2020.
[4] J. Chen, Z. Di, J. Shi, Q. Feng and Q. Wu, “NBLG: A Robust Legalizer for Mixed-Cell-Height Modern Design,” IEEE TCAD, vol. 41, no. 11, pp. 4681– 4693, 2022.
[5] Y.-H. Cheng, D.-W. Huang, W.-K. Mak and T.-C. Wang, “A Practical Detailed Placement Algorithm under Multi-Cell Spacing Constraints,” Proc. ICCAD, 2018.
[6] W.-K. Chow, C.-W. Pui and E. F. Y. Young, “Legalization Algorithm for Multiple-Row Height Standard Cell Design,” Proc. DAC, 2016.
[7] C. Han, K. Han A. B. Kahng, H. Lee, L. Wang, and B. Xu, “Optimal Multi-Row Detailed Placement for Yield and Model-Hardware Correlation Improvements in Sub-10nm VLSI,” Proc. ICCAD, 2017. [8] C. Han, A. B. Kahng, L. Wang, and B. Xu, “Enhanced Optimal Multi-row Detailed Placement for Neighbor Diffusion Effect Mitigation in Sub-10 nm VLSI,” IEEE TCAD, vol. 38, no. 9, pp. 1703–1716, 2019.
[9] S. Heo, A. B. Kahng, M. Kim, L. Wang, and C. Yang, “Detailed Placement for IR Drop Mitigation by Power Staple Insertion in Sub-10nm VLSI,” Proc. DATE, 2019
[10] H. Li, W.-K. Chow, G. Chen, E. F. Y. Young and B. Yu, “Routability-Driven and Fence-Aware Legalization for Mixed-Cell-Height Circuits,” Proc. DAC, 2018.
[11] X. Li, J. Chen, W. Zhu and Y.-W. Chang, “Analytical Mixed-Cell-Height Legalization Considering Average and Maximum Movement Minimization,” Proc. ISPD, 2019.
[12] H. Li, W.-K. Chow, G. Chen, B. Yu and E. F. Y. Young, “Pin-Accessible Legalization for Mixed-Cell-Height Circuits,” IEEE TCAD, vol. 41, no. 1, pp. 143–154, 2022.
[13] Y. Lin, B. Yu, Y. Zou, Z. Li, C. J. Alpert, and D. Z. Pan, “Stitch Aware Detailed Placement for Multiple E-Beam Lithography,” Proc. ASP-DAC, 2016.
[14] 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,” IEEE TCAD, vol. 37, no. 6, pp. 1237–1250, 2018.
[15] Y.-W. Tseng and Y.-W. Chang, “Mixed-Cell-Height Placement Considering Drain-to-Drain Abutment,” Proc. ICCAD, 2018.
[16] C.-H. Wang, Y.-Y. Wu, J. Chen, Y.-W. Chang, S.-Y. Kuo, W. Zhu and G. Fan, “An Effective Legalization Algorithm for Mixed-Cell-Height Standard Cells,” Proc. ASP-DAC, 2017.
[17] G. Wu and C. Chu, “Detailed Placement Algorithm for VLSI Design With Double-Row Height Standard Cells,” IEEE TCAD, vol. 35, no. 9, pp. 1569– 1573, 2016.
[18] Y.-Y. Wu and Y.-W. Chang, “Mixed-Cell-Height Detailed Placement Considering Complex Minimum-Implant-Area Constraints,” Proc. ICCAD, 2017.
[19] H. Yang, K. Fung, Y. Zhao, Y. Lin and B. Yu, “Mixed-Cell-Height Legalization on CPU-GPU Heterogeneous Systems,” Proc. DATE, 2022.
[20] T.-C. Yu, S.-Y. Fang, H.-S. Chiu, K.-S. Hu, P. H.-Y. Tai, C.-F. C. Shen, and H. Sheng, “Pin Accessibility Prediction and Optimization with Deep Learning-based Pin Pattern Recognition,” Proc. DAC, 2019.
[21] Z. Zhu, X. Li, Y. Chen, J. Chen, W. Zhu and Y.-W. Chang, “Mixed-Cell-Height Legalization Considering Technology and Region Constraints,” Proc. ICCAD, 2018.
[22] ICCAD-2017 CAD Contest in Multi-Deck Standard-Cell Legalization, http://iccad-contest.org/2017/index.html
[23] Cadence Innovus Implementation System. https://www.cadence.com/zh TW/ home/tools/digital-design-and-signoff/soc-implementation-and-floorplanning/innovus-implementation-system.html
[24] OpenDP: Open-Source Detailed Placement Engine. https://openroad.readthedocs. io/en/latest/main/src/dpl/README.html