一种集成电路全局布局混合整数规划模型
A Mixed Integer Programming Model for Global Placement of Integrated Circuit
摘要: 本文提出了一种基于混合整数规划的集成电路全局布局模型，全局布局问题是将一些电子元件摆放在电路板指定的区域，使得元件之间没有重叠同时紧凑的排列。与已有的解析布局算法对比，本文用优化模型精确刻画了半周长线长(Half Perimeter Wire Length, HPWL)目标和无重叠(non-overlap)约束可以得到更精确的布局结果，避免了光滑近似的非精确解。数值实验表明，在中等规模的数据集上，本文的模型可以完全满足无重叠约束的同时，半周长线长也是较小的，得到的高质量解可以作为非精确算法的参考解。本文提出的模型在中小规模的布局问题上有较好的效果，可以用在车载芯片或蓝牙芯片设计等实际问题中，具有良好的应用前景。
Abstract: This paper proposes a mixed-integer programming model for global placement of integrated circuit. The global placement problem can be defined as placing electronic components in a designated circuit board, with no overlap and compact arrangement between these components. Compared with existing analytical placement solvers, the model we presented can accurately characterize the Half Perimeter Wire Length (HPWL) objective and the non-overlap constraint, which can obtain more accurate placement results and avoid non-precise solutions based on smooth approximations. Numerical experiments demonstrate that on medium-sized datasets, the proposed model can fully satisfy the non-overlap constraint while achieving a relatively small HPWL, and the obtained high quality solution can serve as a reference for non-precise algorithms. The proposed model performs well on small to medium-sized placement problems and can be applied to practical design problems such as vehicle-mounted chips or Bluetooth chips, with good application prospects.
文章引用：解飞. 一种集成电路全局布局混合整数规划模型[J]. 运筹与模糊学, 2023, 13(4): 2878-2884. https://doi.org/10.12677/ORF.2023.134288

参考文献

[1] 黄志鹏, 李兴权, 朱文兴. 超大规模集成电路布局的优化模型与算法[J]. 运筹学学报, 2021, 25(3): 15-36.
[2] Kahng, A.B., Lienig, J., Markov, I.L. and Hu, J. (2011) VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Dordrecht. [Google Scholar] [CrossRef] 
[3] Chen, T.-C., Jiang, Z.-W., Hsu, T.-C., Chen, H.-C. and Chang, Y.-W. (2008) NTUplace3: An Analytical Placer for Large- Scale Mixed-Size Designs with Preplaced Blocks and Density Constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27, 1228-1240. [Google Scholar] [CrossRef] 
[4] Lu, J., Chen, P., Chang, C.-C., Sha, L., Huang, D.J.-H., Teng, C.-C. and Cheng, C.-K. (2005) EPlace: Electrostatics- Based Placement Using Fast Fourier Transform and Nesterov’s Method. ACM Transactions on Design Automation of Electronic Systems (TODAES), 20, 1-34. [Google Scholar] [CrossRef] 
[5] Lin, Y., Dhar, S., Li, W., Ren, H., Khailany, B. and Pan, D.Z. (2019) DREAMPlace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI Placement. Proceedings of the 56th Annual Design Automation Conference 2019, Las Vegas, 2-6 June 2019, 1-6. [Google Scholar] [CrossRef] 
[6] Guo, Z. and Lin, Y. (2022) Differentiable-Timing-Driven Global Placement. Proceedings of the 59th ACM/IEEE Design Automation Conference, San Francisco, 10-14 July 2022, 1315-1320. [Google Scholar] [CrossRef] 
[7] Chen, J., Chang, Y.-W. and Huang, Y.-C. (2020) Analytical Placement Considering the Electron-Beam Fogging Effect. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 40, 560-573. [Google Scholar] [CrossRef] 
[8] Mirhoseini, A., Goldie, A., Yazgan, M., et al. (2021) A Graph Placement Methodology for Fast Chip Design. Nature, 594, 207-212. [Google Scholar] [CrossRef] [PubMed]
[9] GSRC Floorplan Benchmarks. http://vlsicad.eecs.umich.edu/BK/GSRCbench/
[10] MCNC Floorplan Benchmarks. http://vlsicad.eecs.umich.edu/BK/MCNCbench/
[11] Chan, T., Cong, J. and Sze, K. (2005) Multilevel Generalized Force-Directed Method for Circuit Placement. Proceedings of the 2005 International Symposium on Physical Design, San Francisco, 3-6 April 2005, 185-192. [Google Scholar] [CrossRef] 

为你推荐