论文标题：An Exact Algorithm for Placement Optimization in Circuit Design

期刊：Engineering

DOI：https://doi.org/10.1016/j.eng.2025.03.020

微信链接：点击此处阅读微信文章

近日，上海大学镇璐科研团队在中国工程院院刊《Engineering》发表题为 “An Exact Algorithm for Placement Optimization in Circuit Design” 的研究性文章。该研究聚焦芯片电路设计布局优化难题，提出了一种混合整数线性规划（MILP）模型和基于 Benders 分解（BD）的精确算法，为芯片设计企业提供了更高效、低成本的布局方案。

在信息化时代，芯片技术是智能产品发展的核心驱动力。随着后摩尔定律时代的到来，芯片设计面临着在有限物理尺寸内优化性能、功耗与成本的挑战。布局优化作为芯片设计自动化的关键环节，其质量直接影响后续设计任务。然而，现代电路设计转向混合元器件高度（MCH）配置后，布局优化难度显著增加，传统方法难以满足需求。

此次研究中，团队深入分析了芯片布局问题，将其描述为在给定区域内合法放置元器件并最小化布线总长度的问题。研究人员通过预处理布局问题中的非线性部分，构建了 MILP 模型。该模型综合考虑了元器件不重叠、电源轨道对齐和最小植入面积等布局约束，以降低企业合法化布局成本为目标进行优化。同时，针对模型求解难题，团队基于 Benders 分解设计并实现了精确算法。该算法将复杂问题分解为主问题（MP）和子问题（SP），通过迭代求解这两个小模型，有效提高了求解效率。

图1. 模型预处理的操作。

为验证算法性能，研究团队进行了大量数值实验。实验采用 “2014 年国际物理设计研讨会（ISPD）详细布线驱动布局” 竞赛的真实数据，设置了各种规模的实例组，并与 CPLEX 进行对比分析。结果显示，对于小规模实例，BD 算法计算的最小布局成本与 CPLEX 相同；随着实例规模增加，BD 算法在求解速度上优势明显，能够在更短时间内给出布局解。此外，研究还进行了敏感性分析，考察了芯片区域纵横比、不同高度元器件数量比、元器件总数和 bin 总数等参数对布局成本的影响，为芯片设计企业提供了有价值的设计见解。

该研究成果具有重要的实际应用价值。通过优化布局，芯片设计企业能够在满足客户需求的同时，有效降低成本，提高芯片区域利用率，增强产品竞争力。不过，作者团队指出，本研究提出的模型仅使用了部分已发布的现代设计技术，未来有望结合更多前沿技术进一步优化。这一研究为芯片电路设计布局优化开辟了新路径，有望推动整个半导体行业的发展。

文章信息：

An Exact Algorithm for Placement Optimization in Circuit Design

芯片电路设计布局优化的精确算法

作者：

张滨琪, 镇璐*, Gilbert Laporte

引用：

Binqi Zhang, Lu Zhen, Gilbert Laporte, An Exact Algorithm for Placement Optimization in Circuit Design, Engineering, 2025.

开放获取论文：

https://doi.org/10.1016/j.eng.2025.03.020

更多内容

平台供应链中的物流工程管理——基于物流服务战略选择视角的综述

Engineering工程管理论文合集（2024）

Engineering工程管理论文合集（2023）

海运数据驱动建模：应对不确定性，优化全球物流

Engineering征稿启事：人工智能赋能工程科技