A Nonconvex Nonsmooth PADM for the VLSI Placement Problem

doi:10.1007/s42967-025-00502-5

Communications on Applied Mathematics and Computation ›› 2026, Vol. 8 ›› Issue (4): 1307-1323.doi: 10.1007/s42967-025-00502-5

A Nonconvex Nonsmooth PADM for the VLSI Placement Problem

Bo He¹, Liang Chen², Yu-Hong Dai², Zheng Peng¹

1. The School of Mathematics and Computational Science, Xiangtan University, Xiangtan, 411100, Hunan, China;
2. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China

收稿日期:2024-12-20 修回日期:2025-04-29 接受日期:2025-05-03 出版日期:2026-08-20 发布日期:2026-09-17
通讯作者: Zheng Peng, Email: pzheng@xtu.edu.cn E-mail:pzheng@xtu.edu.cn
基金资助:
This work is supported in part by the National Key R&D Program of China (No. 2021YFA1003600), the Hunan Provincial Innovation Foundation for Postgraduates, China (No. CX20220635), the National Natural Science Foundation of China (Nos. 92473208, 12331011), the Innovative Research Group Project of Natural Science Foundation of Hunan Province of China (No. 2024JJ1008), and the Strategic Priority Research Program of Chinese Academy of Sciences (No. XDA27010101).

A Nonconvex Nonsmooth PADM for the VLSI Placement Problem

Bo He¹, Liang Chen², Yu-Hong Dai², Zheng Peng¹

1. The School of Mathematics and Computational Science, Xiangtan University, Xiangtan, 411100, Hunan, China;
2. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China

Received:2024-12-20 Revised:2025-04-29 Accepted:2025-05-03 Online:2026-08-20 Published:2026-09-17
Supported by:
This work is supported in part by the National Key R&D Program of China (No. 2021YFA1003600), the Hunan Provincial Innovation Foundation for Postgraduates, China (No. CX20220635), the National Natural Science Foundation of China (Nos. 92473208, 12331011), the Innovative Research Group Project of Natural Science Foundation of Hunan Province of China (No. 2024JJ1008), and the Strategic Priority Research Program of Chinese Academy of Sciences (No. XDA27010101).

摘要/Abstract

摘要： The very large scale integration (VLSI) placement problem aims to position electronic cells within a circuit region, optimizing objectives such as wire length and ensuring no cell overlaps. Analytical methods frame the placement problem as a constrained optimization problem and solve its smoothed or relaxed version using optimization methods. In this paper, we shall solve the placement problem without employing any smoothing or relaxation technique. We propose an efficient, smoothing-free analytical method for solving the VLSI placement problem. The basic idea is to utilize the nonsmooth proximal alternating direction method (PADM) to deal with the difficulties associated with the nonsmoothness and constraint complexity of the VLSI placement problem. The global convergence of the method is established. Numerical experiments are conducted on the GSRC circuits, which demonstrate the usefulness of the method.

关键词: Global placement, Analytical method, Half perimeter wire length

Abstract: The very large scale integration (VLSI) placement problem aims to position electronic cells within a circuit region, optimizing objectives such as wire length and ensuring no cell overlaps. Analytical methods frame the placement problem as a constrained optimization problem and solve its smoothed or relaxed version using optimization methods. In this paper, we shall solve the placement problem without employing any smoothing or relaxation technique. We propose an efficient, smoothing-free analytical method for solving the VLSI placement problem. The basic idea is to utilize the nonsmooth proximal alternating direction method (PADM) to deal with the difficulties associated with the nonsmoothness and constraint complexity of the VLSI placement problem. The global convergence of the method is established. Numerical experiments are conducted on the GSRC circuits, which demonstrate the usefulness of the method.

Key words: Global placement, Analytical method, Half perimeter wire length

Bo He, Liang Chen, Yu-Hong Dai, Zheng Peng. A Nonconvex Nonsmooth PADM for the VLSI Placement Problem[J]. Communications on Applied Mathematics and Computation, 2026, 8(4): 1307-1323.

[1] Abbasifard, M.R., Ghahremani, B., Naderi, H.: A survey on nearest neighbor search methods. International Journal of Computer Applications 95, 39-52 (2014)
[2] Adya, S.N., Chaturvedi, S., Roy, J.A., Papa, D.A., Markov, I.L.: Unification of partitioning, placement and floorplanning. In: International Conference on Computer Aided Design, pp. 550-557. IEEE/ACM, San Jose, CA (2004)
[3] Agnihotri, A.R., Madden, P.H.: Fast analytic placement using minimum cost flow. In: Asia South Pacific Design Automation Conference, pp. 128-134. IEEE/ACM, Yokohama, Japan (2007)
[4] Agnihotri, A.R., Ono, S., Madden, P.H.: Recursive bisection placement: Feng shui 5.0 implementation details. In: International Symposium on Physical Design, pp. 230-232. ACM, San Francisco, CA (2005)
[5] Babaie-Kafaki, S.: A survey on the Dai-Liao family of nonlinear conjugate gradient methods. RAIRO-Operations Research 57(1), 43-58 (2023)
[6] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning 3(1), 1-122 (2011)
[7] Brenner, U., Struzyna, M., Vygen, J.: BonnPlace: placement of leading-edge chips by advanced combinatorial algorithms. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(9), 1607-1620 (2008)
[8] Chan, T.F., Cong, J., Kong, T., Shinnerl, J.R.: Multilevel optimization for large-scale circuit placement. In: IEEE/ACM International Conference on Computer Aided Design. ICCAD-2000. IEEE/ACM Digest of Technical Papers (Cat. No.00CH37140), pp. 171-176. IEEE/ACM, San Jose, CA (2000)
[9] Chan, T.F., Cong, J., Shinnerl, J.R., Sze, K., Xie, M.: mPL6: enhanced multilevel mixed-size placement. In: International Symposium on Physical Design, pp. 212-214. ACM, San Jose, CA (2006)
[10] Chen, J.L., Yang, L., Peng, Z., Zhu, W.X., Chang, Y.-W.: Novel proximal group ADMM for placement considering fogging and proximity effects. In: International Conference on Computer-Aided Design, San pp.1-7. IEEE/ACM, San Diego, CA (2018)
[11] Chen, T.-C., Hsu, T.-C., Jiang, Z.-W., Chang, Y.-W.: NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs. In: International Symposium on Physical Design, pp. 236-238. ACM, San Francisco, CA (2005)
[12] Chen, T.-C., Jiang, Z.-W., Hsu, T.-C., Chen, H.-C., Chang, Y.-W.: NTUplace3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(7), 1228-1240 (2008)
[13] Dai, Y.-H.: Nonlinear conjugate gradient methods. Wiley Encyclopedia of Operations Research and Management Science (2010). https://doi.org/10.1002/9780470400531.eorms0183
[14] GSRC Benchmarks. http://vlsicad.eecs.umich.edu/BK/GSRCbench/HARD/
[15] Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pacific Journal of Optimization 2(1), 35-58 (2006)
[16] Hsu, M.-K., Balabanov, V., Chang, Y.-W.: TSV-aware analytical placement for 3-D IC designs based on a novel weighted-average wirelength model. IEEE Trans. Comput. Aided Des. of Integr. Circuits Syst. 32(4), 497-509 (2013)
[17] Hu, B., Zeng, Y., Marek-Sadowska, M.: mFAR: fixed-points-addition-based VLSI placement algorithm. In: International Symposium on Physical Design, pp. 239-241. ACM, San Francisco, CA (2005)
[18] Jian, J.B., Liu, P.J., Jiang, X.Z.: A partially symmetric regularized alternating direction method of multipliers for nonconvex multi-block optimization. Acta Math. Sinica (Chin. Ser.) 64(6), 1005-1026 (2021)
[19] Kahng, A.B., Wang, Q.: Implementation and extensibility of an analytic placer. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 24(5), 18-25 (2004)
[20] Kahng, A.B., Wang, Q.: A faster implementation of APlace. In: International Symposium on Physical Design, pp. 218-220. ACM, San Jose, CA (2006)
[21] Kleinhans, J.M., Sigl, G., Johannes, F.M., Antreich, K.J.: GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 10(3), 356-365 (1991)
[22] Liu, P.J., Jian, J.B., Ma, G.D.: A Bregman-style partially symmetric alternating direction method of multipliers for nonconvex multi-block optimization. Acta Math. Appl. Sin. Engl. Ser. 39(2), 354-380 (2023)
[23] Liu, P.J., Jian, J.B., Shao, H., Wang, X.Q., Xu, J.W., Wu, X.Y.: A Bregman-style improved ADMM and its linearized version in the nonconvex setting: convergence and rate analyses. Journal of the Operations Research Society of China 12, 298-340 (2024)
[24] Liu, P.J., Li, L.H., Shao, H., Liu, M.X., Fan, J.X.: An inertial-type CG projection method with restart for pseudo-monotone costs with application to traffic assignment. Networks and Spatial Economics 25, 147-172 (2025)
[25] Liu, P.J., Shao, H., Wang, Y., Wu, X.Y.: A three-term CGPM-based algorithm without Lipschitz continuity for constrained nonlinear monotone equations with applications. Appl. Numer. Math. 175, 98-107 (2022)
[26] Liu, P.J., Yuan, Z., Zhuo, Y., Shao, H.: Two efficient spectral hybrid CG methods based on memoryless BFGS direction and Dai-Liao conjugacy condition. Optimization Methods and Software 39(6), 1445-1463 (2024)
[27] Lu, J., Chow, W.-K., Sham, C.-W., Young, E.F.: A dual-MST approach for clock network synthesis. In: Asia and South Pacific Design Automation Conference, pp. 467-473. IEEE, Yokohama, Japan (2010)
[28] Lu, J.W.: Fundamental Research on Electronic Design Automation in VLSI Design: Routability. Master Thesis. The Hong Kong Polytechnic University, Hong Kong, China (2010)
[29] Lu, J.W., Chen, P.W., Chang, C.-C., Sha, L., Huang, D.J.-H., Teng, C.-C., Cheng, C.-K.: ePlace: electrostatics-based placement using fast Fourier transform and Nesterov’s method. ACM Transactions on Design Automation of Electronic Systems 20(2), 1-34 (2015)
[30] Luo, T., Pan, D.Z.: DPlace2.0: a stable and efficient analytical placement based on diffusion. In: Asia South Pacific Design Automation Conference, pp. 346-351. IEEE/ACM, Seoul, Korea (South) (2008)
[31] Nam, G.-J., Reda, S., Alpert, C.J., Villarrubia, P.G., Kahng, A.B.: A fast hierarchical quadratic placement algorithm. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(4), 678-691 (2006)
[32] Peng, Z., Chen, J.L., Zhu, W.X.: A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints. J. Global Optim. 62(4), 711-728 (2015)
[33] Sechen, C., Sangiovanni Vincentelli, A.: The TimberWolf placement and routing package. Journal of Solid-State Circuits 20(2), 510-522 (1985)
[34] Shao, H., Guo, H., Wu, X.Y., Liu, P.J.: Two families of self-adjusting spectral hybrid DL conjugate gradient methods and applications in image denoising. Appl. Math. Model. 118, 393-411 (2023)
[35] Spindler, P., Schlichtmann, U., Johannes, F.M.: Kraftwerk2 — a fast force-directed quadratic placement approach using an accurate net model. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(8), 1398-1411 (2008)
[36] Taghavi, T., Yang, X.J., Choi, B.-K.: Dragon2005: large-scale mixed-size placement tool. In: International Symposium on Physical Design, pp. 245-247. ACM, San Francisco, CA (2005)
[37] Viswanathan, N., Nam, G.-J., Alpert, C.J., Villarrubia, P., Ren, H.X., Chu, C.: RQL: global placement via relaxed quadratic spreading and linearization. In: Design Automation Conference, pp. 453-458. IEEE/ACM, San Diego, CA (2007)
[38] Viswanathan, N., Pan, M., Chu, C.: FastPlace 3.0: a fast multilevel quadratic placement algorithm with placement congestion control. In: Asia South Pacific Design Automation Conference, pp. 135-140. IEEE/ACM, Yokohama, Japan (2007)
[39] Vorwerk, K., Kennings, A., Vannelli, A.: Engineering details of a stable force-directed placer. In: International Conference on Computer-Aided Design, pp. 573-580. IEEE/ACM, San Jose, CA (2004)
[40] Xiao, Y.-H., Song, H.-N.: An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems. Journal of Mathematical Imaging and Vision 44(2), 114-127 (2012)
[41] Xiao, Y.-H., Zhu, H., Wu, S.-Y.: Primal and dual alternating direction algorithms for l_1-l_1-norm minimization problems in compressive sensing. Comput. Optim. Appl. 54, 441-459 (2013)
[42] Yao, B., Chen, H.Y., Cheng, C.-K., Chou, N.-C., Liu, L.-T., Suaris, P.: Unified quadratic programming approach for mixed mode placement. In: International Symposium on Physical Design, pp. 193-199. ACM, San Francisco, CA (2005)
[43] Zhu, Z.R., Chen, J.L., Peng, Z., Zhu, W.X., Chang, Y.-W.: Generalized augmented Lagrangian and its applications to VLSI global placement. In: Design Automation Conference, pp. 1-6. ACM/ESDA/IEEE, San Francisco, CA (2018)

A Nonconvex Nonsmooth PADM for the VLSI Placement Problem

A Nonconvex Nonsmooth PADM for the VLSI Placement Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 0

编辑推荐

Metrics

本文评价