非曼哈顿结构下带粒子群优化的VLSI总体布线算法研究

VLSI总体布线的结果对详细布线的成功与否和芯片的性能影响极大，其本质是典型的NP困难多目标组合优化问题。非曼哈顿结构的引入使物理设计的诸多性能得到提高，但目前研究主要集中在通道布线，缺乏一个该结构下有效完整的总体布线方案。本课题研究在非曼哈顿结构下带粒子群优化的高效总体布线器的构建，其分为三个阶段：（1）构建各线网的非曼哈顿结构Steiner最小树集，定义拥挤度估算函数确定处于拥挤区域的线网，并对其构造拥挤度驱动的非曼哈顿结构Steiner树集；（2）引入能克服线网顺序依赖性的整数线性规划模型，并同时采用优化时延和功耗目标的缓冲器插入技术，构建非曼哈顿结构下基于整数线性规划的总体布线多目标优化模型，给出其相应的多目标粒子群优化算法；（3）通过定义线网关键性评价函数以获得基于启发式策略的初始层分配方案，继而以最小化拥挤度、通孔数和串扰为目标给出对初始方案进一步优化的非曼哈顿结构层分配算法。

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