布局是超大规模集成电路(VLSI)物理设计的关键环节之一，布局问题的NP难度使得其快速有效的算法设计成为当前VLSI物理设计领域的一个巨大挑战。本项目用申请者发现的更精确地近似半周线长的l_1模线长作为目标函数，通过热传导模拟单元扩散来刻画单元互不重叠的约束，并建立VLSI全局布局新模型。该模型中的热传导方程可以求出显式解，避免了VLSI布局的泊松方程方法中的偏微分方程数值解问题，提高了计算效率和布局的准确性。为高效求解该全局布局模型，本项目从集成电路的稀疏性和线搜索的步长等方面改进非凸非光滑优化的对角束方法，使得相应的布局算法无需多极框架即可处理百万个单元的VSLI布局问题。进一步，本项目把上述布局算法作为引擎，解决可布通性布局和包含可移动宏单元的布局问题，同时研究各算法的并行化。本项目的研究成果将提出VLSI布局的新模型和快速有效的新算法，且将获得处理规模达千万门级的VLSI布局工具。

Placement is a critical step in VLSI (Very Large Scale Integration) physical design. Designing efficient and effective algorithms for the placement problem is a great challenge in modern VLSI physical design, due to the NP-hardness of the problem. In this project, we will use the l_1-norm wirelength function as the objective function, and use heat conduction for mimicking the diffusion of cells in placement to model non-overlapping constraints among cells, and finally build a new mathematical model for VLSI global placement. In the model, the l_1-norm wirelength function was developed by us and can approximate more exactly the half-perimeter wirelength function. However, the heat conduction equation has not been used previously in VLSI placement, and the equation for VLSI placement has an explicit solution, which is a new finding and can be used directly for optimization. This property prevents numerical solution of the equation, and can improve efficiency and accuracy of placement algorithms. This is different from the Poisson equation method for VLSI placement, where numerical solution of the Poisson equation is needed. ..For efficiently and effectively solving the VLSI global placement optimization model, we will improve the diagonal bundle method in nonconvex and nonsmooth optimization, according to the sparsity of VLSI circuits. The objective of this improvement is that, the placement algorithm can solve the VLSI placement problem with millions of cells directly without using the multilevel scheme. Furthermore, using the placement algorithm developed in this project as an engine, we will solve the routability driven placement problem and the placement problem with movable macro cells, and study parallelization of the obtained placement algorithms. The outcomes of this project will be not only the new mathematical models and new efficient and effective algorithms for VLSI placement, but also the VLSI placement tools which can tackle the placement problems with tens of millions of cells.