基于热传导方程的超大规模集成电路布局模型及快速算法研究

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.

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

布局是超大规模集成电路物理设计自动化的关键环节之一，其NP难度使得快速有效的算法设计成为当前该领域的一个巨大挑战。针对此问题，本项目研究了基于热传导方程的单元散开方法，构造了热传导方程的解析解并设计了相应的布局算法，研究成果获ICCAD’18最佳论文奖提名，所设计的布局工具已被列入IEEE集成电路设计自动化参考设计流程，且被命名为FZUplace；研究了2.5D FPGA布局问题，基于3D泊松方程的解析解和邻近点交替方向法设计了布局算法。与当前最好的工作相比，在可比的计算时间内我们的方法显著减少了SLL长度；研究了考虑雾化效应和邻近效应的布局问题，所设计的布局算法不仅显著降低了雾化效应和邻近效应，而且运行时间得到了加速；研究了考虑最小植入区域约束的集成电路布局问题，提出的算法同时考虑了Vdd / Vss约束，MIA约束，单元位移量和总线长。实验结果表明，我们的算法比当前最先进的工作减少8.5%的总线长；提出了求解全局布局问题的广义增广拉格朗日方法，该方法有望用于解决其他带非线性约束的非线性优化问题。..多倍行高集成电路单元目前已得到广泛应用。针对多倍行高集成电路单元的布局合法化问题，提出了第一个基于解析方法的布局合法化算法，获得了DAC’17最佳论文奖，系54年来中国大陆机构首次获此奖项；基于此引擎，组队参加了ICCAD’17的EDA竞赛并获第一名，这是该赛事有史以来中国大陆首次获冠军；同时，研究了集成电路布局中带技术和区域约束的混合高度单元合法化问题，与最先进的工作相比，所设计的算法在较快的运行时间内达到了最小的单元平均移动量和最大移动量，并且明显减少了技术约束违反。..此外，本项目研究了集成电路制造设计中的版图三重分解问题，提出了离散松弛理论和算法框架。与之前最好的工作相比，我们的方法得到更好的结果，且在离散松弛理论保证下，可以衡量解的质量；在此基础上，本项目还研究了混合电子束和三重图样光刻技术版图分解问题，和多重图样光刻与定向自组装技术下额外通孔插入和引导模板分配问题等。