An Exact Algorithm for Placement Optimization in Circuit Design

Binqi Zhang; Lu Zhen; Gilbert Laporte

doi:10.1016/j.eng.2025.03.020

Engineering ›› 2025, Vol. 52 ›› Issue (9) :278 -296. DOI: 10.1016/j.eng.2025.03.020

Research

Article

An Exact Algorithm for Placement Optimization in Circuit Design

Author information +

History +

PDF (2374KB)

Abstract

Placement optimization is a crucial phase in chip design, involving the strategic arrangement of cells within a limited region to enhance space utilization and reduce wirelength. Chip design enterprises need to optimize the placement according to design rules to meet customer demands. While mixed-cell-height circuits are widely used in modern chip design, few studies have simultaneously considered the non-overlapping cells, rails alignment, and minimum implantation area constraints in the placement optimization problems. Hence, this study involves preprocessing the non-linear parts and developing a mixed-integer linear programming model to reduce the cost of legalizing chip placements for businesses. Furthermore, this study designs and implements an exact algorithm based on Benders decomposition, utilizing dual theory to obtain an optimal cut and iteratively solve for the coordinates of cells. Numerical experiments across various scales validate the performance of the algorithm. Through a detailed analysis of the shape of the chip region division, the proportion of different types of cells, the total number of cells and bins, and their impact on the placement, we derive some potentially useful design insights that can benefit chip design enterprises.

Keywords

Packing / Placement optimization / Chip design / Linear programming / Benders decomposition

Cite this article

Download citation ▾

Binqi Zhang, Lu Zhen, Gilbert Laporte. An Exact Algorithm for Placement Optimization in Circuit Design. Engineering, 2025, 52(9): 278-296 DOI:10.1016/j.eng.2025.03.020

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Anderson J, Kayraklioglu E, Imani H, Shen C, Miscuglio M, Sorger V, et al. Virtualizing a post-Moore’s Law analog mesh processor: the case of a photonic PDE accelerator. ACM Trans Embed Comput Syst 2023; 22(2):38.

[2]	Wang J, Wong A, Lam E. Standard cell layout with regular contact placement. IEEE Trans Semicond Manuf 2004; 17(3):375-83.

[3]	Zhu Z, Chen J, Peng Z, Zhu W, Chang Y. Generalized augmented lagrangian and its applications to VLSI global placement. In:Proceedings of the 55th ACM/ ESDA/IEEE Design Automation Conference; 2018 Jun 24-28; San Francisco, CA, USA. New York City: IEEE Press; 2018. p. 1-6.

[4]	Wang C, Wu Y, Chen J, Chang Y, Kuo S, Zhu W, et al. An effective legalization algorithm for mixed-cell-height standard cells. In:Proceedings of the 2017 22nd Asia and South Pacific Design Automation Conference;2017 Jan 16-17; Tokyo, Japan. New York City: IEEE; 2017. p. 450-5.

[5]	Zhu Z, Huang Z, Yang P, Zhu W, Chen J, Zhou H. Mixed-cell-height legalization considering complex minimum width constraints and half-row fragmentation effect. Integr VLSI J 2020; 71:1-10.

[6]	Wu G, Chu C. Detailed placement algorithm for VLSI design with double-row height standard cells. IEEE Trans Comput Aided Des Integrated Circ Syst 2016; 35(9):1569-73.

[7]	Chow J, Pui W, Young F. Legalization algorithm for multiple-row height standard cell design. In:Proceedings of the 53rd Annual Design Automation Conference;2016 Jun 5-9; Austin, TX, USA. New York City: IEEE; 2016. p. 1-6.

[8]	Spindler P, Schlichtmann U, Johannes F. Abacus:fast legalization of standard cell circuits with minimal movement. In:Proceedings of the 2008 ACM international symposium on physical design; 2008 Apr 13-16; Portland, OR, USA. New York City: Association for Computing Machinery (ACM); 2008. p. 47-53.

[9]	Lin Y, Yu B, Xu X, Gao J, Viswannathan N, Liu W, et al. MrDP: multiple-row detailed placement of heterogeneous-sized cells for advanced nodes. IEEE Trans Comput Aided Des Integrated Circ Syst 2018; 37(6):1237-50.

[10]	Chen J, Lin Z, Xie Y, Zhu W, Chang Y. Mixed-cell-height placement with complex minimum-implant-area constraints. IEEE Trans Comput Aided Des Integrated Circ Syst 2022; 41(11):4639-52.

[11]	Breuer M. A class of min-cut placement algorithms. In:Proceedings of the 14th Design Automation Conference; 1977 Jun 20-22; New Orleans, LA, USA. New York City: Association for Computing Machinery (ACM); 1977. p. 284-90.

[12]	Wang M, Yang X, Sarrafzadeh M. DRAGON2000:standard-cell placement tool for large industry circuits. In:Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design; 2000 Nov 5-9; San Jose, CA, USA. New York City: IEEE; 2000. p. 260-3.

[13]	Agnihotri A, Ono S, Madden P. Recursive bisection placement:feng shui 5.0 implementation details. In:Proceedings of the 2005 International Symposium on Physical Design; 2005 Apr 3-6; San Francisco, CA, USA. New York City: Association for Computing Machinery (ACM); 2005. p. 230-2.

[14]	Viswanathan N, Alpert C, Sze C, Li Z, Wei Y. The DAC 2012 routability-driven placement contest and benchmark suite. In:Proceedings of the 2012 49th ACM/ EDAC/IEEE Automation Conference; 2012 Jun 3-7; San Francisco, CA, USA. New York City: Association for Computing Machinery (ACM); 2012. p. 774-82.

[15]

Yutsis V, Bustany I, Chinnery D, Shinnerl J, Liu W. ISPD 2014 benchmarks with sub-45nm technology rules for detailed-routing-driven placement. In:Proceedings of the 2014 on International Symposium on Physical Design; 2014 Mar 30-Apr 2; Petaluma, CA, USA. New York City: Association for Computing Machinery (ACM); 2014. p. 161-8.

[16]

Kim M, Hu J, Li J, Viswanathan N. ICCAD- 2015 CAD contest in incremental timing-driven placement and benchmark suite. In:Proceedings of the 2015 IEEE/ACM International Conference on Computer-Aided Design; 2015 Nov 2-6; San Francisco, CA, USA. New York City: Association for Computing Machinery (ACM); 2015. p. 921-6.

[17]	Hao R, Cai Y, Zhou Q. Intelligent and kernelized placement: a survey. Integr VLSI J 2022; 86:44-50.

[18]	Lu J, Chen P, Chang C, Lu S, Huang D, Teng C, et al. ePlace: electrostatics-based placement using fast Fourier transform and Nesterov’s method. ACM Trans Des Autom Electron Syst 2015; 20(2):1-34.

[19]	Lin Y, Jiang Z, Gu J, Li W, Dhar S, Ren H, et al. Dreamplace: deep learning toolkit-enabled GPU acceleration for modern VLSI placement. IEEE Trans Comput Aided Des Integrated Circ Syst 2021; 40(4):748-61.

[20]

Yue S, Songhori E, Jiang J, Boyd T, Goldie A, Mirhoseini A, et al. Scalability and generalization of circuit training for chip floorplanning. In:Proceedings of the ISPD 2022: International Symposium on Physical Design;2022 Mar 27-30; Seoul, South Korea. New York City: Association for Computing Machinery (ACM); 2022. p. 65-70.

[21]	Silva E, Melega G, Akartunali K, de Araujo S. Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost. Eur J Oper Res 2023; 304(2):443-60.

[22]	Pierini L, Poldi K. Optimization of the cutting process integrated to the lot sizing in multi-plant paper production industries. Comput Oper Res 2023; 153:106157.

[23]	Coutinho J, Reis M, Neves D, Bernardo F. Robust optimization and data-driven modeling of tissue paper packing considering cargo deformation. Comput Ind Eng 2023; 175:108898.

[24]	Cai S, Deng J, Lee L, Chew E, Li H. Heuristics for the two-dimensional irregular bin packing problem with limited rotations. Comput Oper Res 2023; 160:106398.

[25]	Martinovic J, Selch M. Mathematical models and approximate solution approaches for the stochastic bin packing problem. Comput Oper Res 2021; 135:105439.

[26]	Delorme M, Iori M, Martello S. Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur J Oper Res 2016; 255(1):1-20.

[27]	Serairi M, Haouari M. A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem. Oper Res 2018; 52 (2):391-414.

[28]	Queiroz T, Hokama P, Schouery R, Miyazawa F. Two-dimensional disjunctively constrained knapsack problem: heuristic and exact approaches. Comput Ind Eng 2017; 105:313-28.

[29]	Tseng K, Chang Y, Liu C. Minimum-implant-area-aware detailed placement with spacing constraints. In:Proceedings of the 2016 ACM/EDAC/IEEE Design Automation Conference;2016 Jun 5-9; Austin, TX, USA. New York City: Association for Computing Machinery (ACM); 2016. p. 1-6.

[30]	Farghadan A, Mohammadzadeh N. Quantum circuit physical design flow for 2D nearest-neighbor architectures: quantum circuit design flow. Int J Circuit Theory Appl 2017; 45(7):989-1000.

[31]	Li W, Lin Y, Li M, Dhar S, Pan D. UTPlaceF 2.0: a high-performance clock-aware FPGA placement engine. ACM Trans Des Autom Electron Syst 2018; 23(4):1-23.

[32]	Chen J, Chang Y, Wu Y. Mixed-cell-height detailed placement considering complex minimum-implant-area constraints. IEEE Trans Comput Aided Des Integrated Circ Syst 2021; 40(10):2128-41.

[33]	Lu J, Zhuang H, Chen P, Chang H, Chang C, Wong Y, et al. EPlace-MS: electrostatics-based placement for mixed-size circuits. IEEE Trans Comput Aided Des Integrated Circ Syst 2015; 34(5):685-98.

[34]	Lin Z, Xie Y, Zou P, Wang S, Yu J, Chen J. An incremental placement flow for advanced FPGAs with timing awareness. IEEE Trans Comput Aided Des Integrated Circ Syst 2022; 41(9):3092-103.

[35]	Belieres S, Hewitt M, Jozefowiez N, Semet F. Meta partial benders decomposition for the logistics service network design problem. Eur J Oper Res 2022; 300(2):473-89.

[36]	Zhang Q, Wang SA, Zhen L. Yard truck retrofitting and deployment for hazardous material transportation in green ports. Ann Oper Res 2022; 17:103322.

[37]	Adulyasak Y, Cordeau J, Jans R. Benders decomposition for production routing under demand uncertainty. Oper Res 2015; 63(4):851-67.

[38]	International Symposium on Physical Design (ISPD). ISPD 2014 detailed routing-driven placement contest [Internet]. Petaluma: International Symposium on Physical Design 2014; 2014 Mar 16 [cited 2025 Mar 3]. Available from: https://www.ispd.cc/contests/14/ispd2014_contest.html