<p>The placement problem in Very Large-Scale Integration (VLSI) circuits is a critical step in chip design. Its primary goal is to optimize the wirelength of circuit components within a confined area while adhering to nonoverlapping constraints. Most analytical placement models rely on smooth approximations, thereby sacrificing the accuracy of wirelength estimation. To mitigate these inaccuracies, this paper introduces a novel approach that directly optimizes the original nonsmooth wirelength and proposes an innovative penalty model tailored for the global placement problem. Specifically, we transform the nonoverlapping constraints into rectified linear penalty functions, allowing for a more precise formulation of the problem. Notably, we recast the resultant optimization problem into a form analogous to training deep neural network with Rectified Linear Units (ReLU). Leveraging automatic differentiation techniques from deep learning, we efficiently compute the subgradient of the objective function. This facilitates the application of stochastic subgradient methods to solve the model. To enhance the algorithm’s performance, several advanced techniques are further introduced, leading to significant improvements in both efficiency and solution quality. Numerical experiments were conducted on Gigascale Systems Research Center (GSRC) benchmark and International Symposium on Physical Design 2005 (ISPD2005) benchmark circuits. The results demonstrate that our proposed model and algorithm achieve significant reductions in wirelength while effectively eliminating overlaps. This highlights the potential of our approach as a transformative advancement for VLSI placement. Furthermore, we establish a rigorous convergence proof for the proposed stochastic subgradient method. To the best of our knowledge, it constitutes the first such result for the ReLU-type nonsmooth and nonconvex optimization problems.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An efficient stochastic subgradient method for the global placement problem in very large-scale integration circuits

  • Yi-Shuang Yue,
  • Yu-Hong Dai,
  • Haijun Yu

摘要

The placement problem in Very Large-Scale Integration (VLSI) circuits is a critical step in chip design. Its primary goal is to optimize the wirelength of circuit components within a confined area while adhering to nonoverlapping constraints. Most analytical placement models rely on smooth approximations, thereby sacrificing the accuracy of wirelength estimation. To mitigate these inaccuracies, this paper introduces a novel approach that directly optimizes the original nonsmooth wirelength and proposes an innovative penalty model tailored for the global placement problem. Specifically, we transform the nonoverlapping constraints into rectified linear penalty functions, allowing for a more precise formulation of the problem. Notably, we recast the resultant optimization problem into a form analogous to training deep neural network with Rectified Linear Units (ReLU). Leveraging automatic differentiation techniques from deep learning, we efficiently compute the subgradient of the objective function. This facilitates the application of stochastic subgradient methods to solve the model. To enhance the algorithm’s performance, several advanced techniques are further introduced, leading to significant improvements in both efficiency and solution quality. Numerical experiments were conducted on Gigascale Systems Research Center (GSRC) benchmark and International Symposium on Physical Design 2005 (ISPD2005) benchmark circuits. The results demonstrate that our proposed model and algorithm achieve significant reductions in wirelength while effectively eliminating overlaps. This highlights the potential of our approach as a transformative advancement for VLSI placement. Furthermore, we establish a rigorous convergence proof for the proposed stochastic subgradient method. To the best of our knowledge, it constitutes the first such result for the ReLU-type nonsmooth and nonconvex optimization problems.