超大规模集成电路物理设计中布图规划和线长估计问题是集成电路设计的重要环节，布图规划和线长估计问题是高度复杂的。我们已对其做了比较深入的研究，分析布图规划和线长估计问题的图论性质，给出问题解的构造方法，构造了一个多目标粒子群优化算法框架，继而研究求解布图规划和线长估计问题的有效多目标粒子群优化算法。本课题研究在非曼哈顿结构下带粒子群优化的高效总体布线器的构建，我们深入研究非曼哈顿结构下总体布线问题的相关性质，选取X结构作为非曼哈顿结构开展研究，取得的主要研究成果如下：（1）针对X结构Steiner最小树问题，分析非曼哈顿结构Steiner树性质，重新构造非曼哈顿结构 Steiner 树的编解码方式，提出来一种改进的离散粒子群优化算法用以求解X结构Steiner最小树；（2）定义拥挤度估算函数确定处于拥挤区域的线网和引入最小化线长最小半径的性能驱动布线树模型，构造不同目标和不同约束下的非曼哈顿结构布线树模型，从而构建其相应的粒子群优化算法，继而从适应度函数的构造、算法参数模型调整策略和性能提高策略三个方面来研究算法；（3）针对非曼哈顿结构下层分配问题，通过定义线网关键性评价函数以获得基于启发式策略的初始层分配方案，继而以最小化拥挤度、通孔数和串扰为目标给出对初始方案进一步优化的非曼哈顿结构层分配算法，分析算法的收敛性并检验这些算法的有效性和可行性。本项目的研究成果将为粒子群优化算法的进一步应用打下基础，并进一步提高我国关于超大规模集成电路设计基础理论研究水平。 2100433B