An Exact Algorithm for Placement Optimization in Circuit Design

Binqi Zhang , Lu Zhen , Gilbert Laporte

Engineering ›› 2025, Vol. 52 ›› Issue (9) : 278 -296.

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

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

AI Summary AI Mindmap
PDF (2374KB)

349

Accesses

0

Citation

Detail

Sections
Recommended

AI思维导图

/