A Nonconvex Nonsmooth PADM for the VLSI Placement Problem

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.

Keywords

Global placement / Analytical method / Half perimeter wire length / 65K05 / 90C46

References

[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] BoydS, ParikhN, ChuE, PeleatoB, EcksteinJ. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 2011, 3(1): 1-122

[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] HagerWW, ZhangH. A survey of nonlinear conjugate gradient methods. Pacific Journal of Optimization, 2006, 2(1): 35-58

[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] JianJB, LiuPJ, JiangXZ. A partially symmetric regularized alternating direction method of multipliers for nonconvex multi-block optimization. Acta Math. Sinica (Chin. Ser.), 2021, 64(6): 1005-1026

[19] KahngAB, WangQ. Implementation and extensibility of an analytic placer. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2004, 24(5): 18-25

[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] KleinhansJM, SiglG, JohannesFM, AntreichKJ. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1991, 10(3): 356-365

[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] LuJW, ChenPW, ChangC-C, ShaL, HuangDJ-H, TengC-C, ChengC-K. ePlace: electrostatics-based placement using fast Fourier transform and Nesterov’s method. ACM Transactions on Design Automation of Electronic Systems, 2015, 20(2): 1-34

[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] NamG-J, RedaS, AlpertCJ, VillarrubiaPG, KahngAB. A fast hierarchical quadratic placement algorithm. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2006, 25(4): 678-691

[32] PengZ, ChenJL, ZhuWX. A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints. J. Global Optim., 2015, 62(4): 711-728

[33] SechenC, Sangiovanni VincentelliA. The TimberWolf placement and routing package. Journal of Solid-State Circuits, 1985, 20(2): 510-522

[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] XiaoY-H, SongH-N. An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems. Journal of Mathematical Imaging and Vision, 2012, 44(2): 114-127

[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)

Funding

National Key R&D Program of China(2021YFA1003600)

Hunan Provincial Innovation Foundation for Postgraduates(CX20220635)

Natural Science Foundation of China(92473208)

Innovative Research Group Project of Natural Science Foundation of Hunan Province of China(2024JJ1008)

RIGHTS & PERMISSIONS

Shanghai University

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.