总体布线是VLSI物理设计中极为重要的一个环节。非曼哈顿结构的提出为物理设计带来诸多性能的提高，但该结构的引入和多层工艺的普及，使得总体布线问题更为复杂，且目前研究工作只就某些局部目标展开，缺乏一种该结构下有效完整的总体布线方案。正是在这样的背景下，本项目对非曼哈顿结构VLSI总体布线相关问题展开一些研究工作，选取X结构作为非曼哈顿结构的代表，完成的主要工作如下：（1）基于多目标PSO和Elmore时延模型提出了一种构建时延驱动X结构Steiner树的有效算法，从而有助于性能驱动X结构总体布线问题的研究。（2）绕障Steiner最小树的构建是VLSI物理设计中一个极为重要问题，为此，提出一种基于粒子群优化的有效算法用于求解X结构下的绕障Steiner最小树问题。考虑到粒子群优化算法存在收敛速度慢的不足，进一步设计一种四步骤的高效启发式算法用于求解该问题。（3）针对ML-OAXSMT问题，以最小化布线总代价为目标，并同时考虑到通孔数的优化，提出了一种基于PSO算法和惩罚机制的ML-OAXSMT构建算法。为了进一步提高求解多ML-OAXSMT问题的算法质量，基于查找表的思想，提出了一种高效的绕障策略，可以准确获得多层环境下的Steiner点位置，从而构建一棵高质量的ML-OAXSMT。(4) 针对X结构下的总体布线问题，提出一种基于ILP模型、划分策略及PSO等技术的高质量X结构总体布线算法。 本项目进一步扩宽研究思路，针对曼哈顿结构下绕障Steiner树构建问题并且将PSO扩展应用于VLSI电路划分阶段，主要完成以下工作：（1）研究了电压转换速率的计算模型和RSMT-RERR问题中的电压转换速率约束，基于SPCF算法框架提出考虑电压转换速率约束的直角Steiner树构造算法。（2）研究了ML-OARSMT问题的特征，提出了该问题布线图的构造方法。考虑避开障碍和连通相邻层，选择了三种类型候选通孔位置。 （3）电路划分作为VLSI物理设计中的首个关键环节，通过附加考虑时延因素，构造了电路划分的多目标问题模型，引入局部搜索策略以及基于小生境技术的表现型共享粒子评价机制，设计了一个求解多目标电路划分问题的混合DPSO。 2100433B