隨著積體電路製程不斷演進，超大型積體電路中採用混合高度元件設計已經使傳統單一高度標準元件合法化演算法變得過時。相比起較低的元件，高元件提供更大的驅動強度，但是面積和功耗也會增加。因此，現代電路經常包含高度不同的標準單元，以滿足複雜的設計需求。然而，這種趨勢在佈局設計中帶來了重大挑戰，特別是在混合高度元件的佈局合法化方面。另一方面，先進製程開始出現對於相鄰列上的元件之間的垂直鄰接限制。這在過往的研究中很少被考慮，因為在以往的製程中，電源軌道足夠高，可以很好得隔離不同列中的元件。儘管先前有許多對混合高度元件佈局合法化的研究，但它們大多僅能在最小化元件在佈局中的平均總位移的同時去考慮水平方向的元件相鄰限制，而無法考慮相鄰列上的元件之間的垂直鄰接限制。此外，現有的許多方法無法簡單得擴展以應對垂直鄰接限制。為了解決這些問題，本文提出了第一個混合高度元件佈局合法化演算法。該演算法可以有效得處理列與列之間元件垂直鄰接的限制，並保持全局佈局所帶來的電路特性。本篇論文所提出的演算法不僅可以處理目前佈局規範的混合高度元件佈局合法化問題，而且相對實用和靈活，可以應對未來出現的不論是同一列內亦或是列與列之間的元件擺放限制。

Propelled by aggressive technology scaling, the adoption of mixed-cell-height design in Very Large-Scale Integration (VLSI) circuit has made traditional row- based single-row-height cells legalization techniques obsolete. In contrast to lower cells, higher cells offer larger driving strengths while suffering from increase in area and power consumption. As a result, modern circuits frequently incorporate standard cells of varying heights to meet complex design requirements. However, this trend poses a significant challenge in layout design, especially in mixed-cell-height legalization. On the other hand, the vertical abutment constraint among cells on consecutive rows emerges as an advanced design requirement, which has rarely been considered because the power ground rails were sufficiently tall in conventional pro- cess nodes to isolate cells on different rows. Although there have been a number of studies on mixed-cell-height legalization, most of them can only minimize the total cell displacement and may additionally consider horizontal abutment require- ments. In addition, the existing approaches may not be trivially extended to well- tackle the general vertical abutment constraint due to the analytical optimization scheme. To address these issues, this work proposes the first mixed-cell-height le- galization algorithm that addresses the general inter-row cell abutment constraint (vertical abutment constraint) and leverages the optimized cell positions obtained from global placement. The proposed algorithm not only offers a promising solution to the mixed-cell-height legalization problem but is relatively practical and flexi- ble to address any upcoming intra- and inter-row constraints. The experimental results show that the proposed algorithm outperforms previous mixed-cell-height legalization works, even in the absence of the vertical abutment constraint. Upon the application of the vertical abutment constraint, our algorithm offers superior performance and delivers promising results.

[1] Nima Karimpour Darav, Ismail S. Bustany, Andrew Kennings, and Ravi Mamidi, “ICCAD-2017 CAD Contest in Multi-Deck Standard Cell Legalization and Benchmarks,” in IEEE/ACM International Conference on Computer-Aided Design (ICCAD ’17), 2017.
[2] Z. Zhu, J. Chen, W. Zhu and Y. -W. Chang, “Mixed-Cell-Height Legalization Considering Technology and Region Constraints,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD ’20), Dec. 2020.
[3] Chung-Hsien Wu, Wai-Kei Mak, and Chris Chu, “Linear-time Mixed-Cell-Height Legalization for Minimizing Maximum Displacement,” in International Symposium on Physical Design (ISPD ’22), 2022.
[4] Y. Lin, B. Yu, B. Xu and D. Z. Pan, “Triple patterning aware detailed placement toward zero cross-row middle-of-line conflict,” in IEEE/ACM International Conference on Computer-Aided Design (ICCAD ’15), 2015.
[5] J. Chen, Y. -W. Chang and Y. -Y. Wu, “Mixed-Cell-Height Detailed Placement Considering Complex Minimum-Implant-Area Constraints,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD ’20), Oct. 2021.
[6] J. Chen, Z. Lin, Y. Xie, W. Zhu and Y. -W. Chang, “Mixed-Cell-Height Placement With Complex Minimum-Implant-Area Constraints,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD ’21), Nov. 2022.
[7] H. Li, W. -K. Chow, G. Chen, B. Yu and E. F. Y. Young, “Pin-Accessible Legalization for Mixed-Cell-Height Circuits,” in IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems (TCAD ’21), Jan. 2022.
[8] G. Wu and C. Chu, “Detailed Placement Algorithm for VLSI Design With Double-Row Height Standard Cells,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD ’15) , Sept. 2016.
[9] S. A. Dobre, A. B. Kahng and J. Li, “Design Implementation With Noninteger Multiple-Height Cells for Improved Design Quality in Advanced Nodes,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD ’17), April 2018.
[10] Chao-Hung Wang, Yen-Yi Wu, Jianli Chen, Yao-Wen Chang, Sy-Yen Kuo, Wenxing Zhu, and Genghua Fan, “An effective legalization algorithm for mixed- cell-height standard cells,” in 22nd Asia and South Pacific Design Automation Conference (ASP-DAC ’17), 2017.
[11] Jianli Chen, Ziran Zhu, Wenxing Zhu, and Yao-Wen Chang, “Toward optimal legalization for mixed-cell-height circuit designs,” in 54th ACM/EDAC/IEEE Design Automation Conference (DAC ’17), 2017.
[12] Xingquan Li, Jianli Chen, Wenxing Zhu, and Yao-Wen Chang, “Analytical Mixed-Cell-Height Legalization Considering Average and Maximum Movement Minimization,” in International Symposium on Physical Design (ISPD ’19), 2019.
[13] W.-K. Chow, C.-W. Pui, and E. F.Y. Young, “Legalization algorithm for multiple-row height standard cell design,” in 53nd ACM/EDAC/IEEE Design Automation Conference (DAC ’16), 2016.