Nonlinear-Programming Based Algorithms for Constrained Circuit Placement

本研究探讨了在严格的时间限制下大规模集成电路放置的新型、高效和高度优化的解决方案。本项目的重点是研究应用最近发展的数值算法的可行性，如大规模粒子模拟的快速多极方法和非线性规划的内点法来解决大规模受限电路放置问题。本项目研究的关键要素包括：(i)在数学规划公式中直接处理时间和非重叠约束；（ii）问题的分层模型，允许对非光滑和离散约束进行光滑逼近；（iii）快速多极展开，以加速对约束及其衍生物的评估；（iv）基于kkt的线性方程组的快速数值解，用于计算优化中的搜索方向。

This research investigates new, efficient, and highly optimized solutions to large-scale IC placement under tight timing constraints. The focus of this project is to investigate the feasibility of applying recentlydeveloped numerical algorithms, such as the fast multipole method for large-scale particle simulation and the interior-point method for non-linear programming to solving the large-scale constrained circuitplacement problem. Key elements of studies in this project include (i) direct handling of timing and non-overlapping constraints in a mathematical programming formulation; (ii) an hierarchical model of the problem allowing smooth approximations to non-smooth and discrete constraints; (iii) fast multipole expansions to accelerate evaluation of the constraints and their derivatives; (iv) fast numerical solution to KKT-based systems of linear equations used to calculate search directions in the optimization.